Design and Analysis of Algorithms
Design and Analysis of Algorithms
Design and Analysis of Algorithms
01-01
Introduction to
Design and Analysis of Algorithms
Introduction to Course
Imran Ihsan
Assistant Professor, Department of Computer Science
Air University, Islamabad, Pakistan
www.imranihsan.com
Automate this
2 million speech patterns
identify a caller's personality style
direct the caller with a compatible
customer support representative
2
Algorithms that Changed the Future
1. Search Engine Indexing
– Finding Needles in the World’s Biggest Haystack
2. PageRank
– The Technology That Launched Google
3. Public-key Cryptography
– Sending Secrets on a Postcard
4. Error-Correcting Codes
– Mistakes That Fix Themselves
5. Pattern recognition
– Learning from Experience
6. Data Compression
– Something for Nothing
7. Database
– The Quest for Consistency
8. Digital Signatures
– Who Really Wrote This Software?
3
Google Maps
Algorithms
An algorithm is a set of instructions that state how a task is to be
performed.
A Knitting Pattern
6
Algorithm
7
Data Structures
The frameworks we use to maintain the data that are
processed by the algorithms.
Inside data structures, we use algorithms to manipulate
the data efficiently.
8
Abstract Data Types
higher level patterns for organizing data structures
patterns for reading data from the structure, for removing data, and for
adding new data.
9
Abstract Data Types
think of this sketch of a 'graph' as an abstract data type
10
Data Structure
2D matrix implementing the graph
11
Algorithms: three questions
12
What is the point?
1. Your programs must be correct
not just bug-free code,
but implementing an algorithm that does what it is supposed to do.
14
Programming, Coding…
15
... and a fourth question
How do we implement that?
16
Course objective
17
Course Policy
• Class Participation
• Assignment
Key Features • Quiz
• Exam
18
Grading scheme
30%
Assignments
50%
Passing Marks
10% Quiz
Marks 80%
Grading
Distribution to get “A”
20% Midterm
No “D” Grade
40% Final
19
Instructor: Imran Ihsan
20
Programming Foundations
Programming C++:
Datatypes, Conditions, Loops, Arrays, Pointers, Functions,
Pass By Value, Pass By Reference
OOP++
Templates, STL, Design Pattern, Model-View-Controller,
Factory Method, Iterator Design, Composite Design,
Data Structures
Arrays, Linked List, Stack, Queue, Trees, Heaps, Disjoint
Sets, Hash Table, Graphs
21
Why Study Algorithms?
Learning Objective
Understand the type of problem that will be covered in this class.
23
Straight forward Programming Problems
Has straight forward implementation.
Natural solution is already efficient.
24
DISPLAY GIVEN TEXT
25
COPY A FILE
26
SEARCH FOR A GIVEN WORD
27
SEARCH FOR A GIVEN WORD
Linear Scan
28
Simple Programming Problems
Has linear scan.
Cannot do much better.
The obvious program works.
29
Algorithms Problems
Not so clear what to do?
30
Find the Shortest Path Between Locations
31
Find the Best Assignment of Students to
Dorm Rooms
32
Measure Similarity of Documents
33
Algorithms Problems
Not clear how to do
Simple ideas too slow
Room for optimization
34
Artificial Intelligence Problems
Hard to even clearly state
35
Understand Natural Language
36
Identify Objects In Photographs
37
Play Games Well
38
What We’ll Cover
Focus on algorithms problems.
Clearly formulated.
Hard to do efficiently.
39
Coming up
Cover two algorithm problems:
Fibonacci Numbers
Greatest Common Divisors
40
Straightforward Algorithm
Problem
Algorithm
Statement
41
Take Too Long
42
4
3
Slightly More
Complicated
Algorithm
That is Very Fast