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

Setting up a new XBOX Console

Recipe for Cooking Pizza

Directions for Walking to Cafeteria Building

Operations to turn an MP3 File in a sequence of sounds produced by an MP3

Player.

An algorithm is an ordered, deterministic,

executable, terminating set of instructions.
5
 Algorithms – On Computers
The abstract specification of the processes that are running on
all of our computers, phones, games consoles, databases,
autopilots, banking systems, autonomous vehicles, networks, ...

Algorithms process information maintained in data structures

and produce actions and results.

6
 Algorithm

We'll see a more efficient

version of this algorithm
later this semester
which relies on an
efficient data structure
underneath.

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

Does it do How much

what it is How long space does
supposed will it take? it need to
to do? run?

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.

2. Your programs should be efficient

programs that take too long to run are useless
understand the implication of choosing different library functions
understand the implication of choosing different design patterns
what may be easier for you to code may be much worse to run …

1. Faster machines means users expect to solve bigger problems

2. Some problems have known limits on their efficiency

Yawn – machines are getting faster every year

– who cares about efficiency?
13
 What is the point?
3. You must be able to advertise your code to other
programmers in terms they will understand
state what (agreed) abstract data types you are using
also state what data structures and algorithms you have used to
implement them

4. You should not subvert the design pattern

understand the specified ways to interact with the data
don't interact with it in other ways
abandons correctness and efficiency
don't allow other programmers to subvert the design

14
Programming, Coding…

This ain't chemistry - this is art.

Coding is art.
And the shit I code is the bomb,
so don't be telling me.

The shit you code is shit.

You and I will not make garbage.
We will produce a chemically pure and stable product
that performs as advertised.
No adulterants. No baby formula. No chili powder.

15
 ... and a fourth question
How do we implement that?

We are going to use C++ or JAVA or Python.

understand the library functions
learn how to implement structures and algorithms efficiently

The module is a mix of theory and practice.

16
 Course objective

Gain expertise in the use and implementation of simple data structures

Their application in the creation of efficient software

Apply data structures and algorithms appropriately in formulating

solutions of meaningful computational problems

Implement computer applications employing simple data structures

in a modern programming language

Implement simple data structures using array-based techniques and

linked lists.

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

Consultation Direct general questions

• Visit whenever my door is • Those that other students
open, and I am on my may also be wondering
seat. about and
• That Google can’t answer

20
Programming Foundations
Programming C++:
Datatypes, Conditions, Loops, Arrays, Pointers, Functions,
Pass By Value, Pass By Reference

Object Oriented Programming:

Classes, Operator Overloading, Inheritance, This, New,
Delete, Polymorphism, Virtual Functions, Uses & Knows-A

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.

Recognize some problems for which sophisticated algorithms

might not be necessary.

Describe some artificial intelligence problems which go beyond

the scope of this course.

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

Examples of why algorithms are important.

40
 Straightforward Algorithm

Problem
Algorithm
Statement

41
Take Too Long

42
 4
3

Slightly More
Complicated
Algorithm
That is Very Fast