Design & Analysis of Algorithms (2230322)

LECTURE 1

DR. ABHISHEK DIXIT

Assistant Professor,
Deptt. of IT
MITS, Gwalior
Madhav Institute of Technology & Science, Gwalior
 Design & Analysis of Algorithms

COURSE OBJECTIVE & SYLLABUS

COURSE OUTCOMES

RECOMMENDED BOOKS

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Design & Analysis of Algorithms

Why we study this Course

Engineers working in Google, Microsoft, Facebook, Amazon-

like such companies are different than others and paid higher as
compared to other companies…but why?

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Design Techniques of Algorithm

 Selecting a proper design technique for algorithms is a complex but important task. Following are
some of the main algorithm design techniques:

1. Brute-force or exhaustive search

2. Divide and Conquer
3. Greedy Algorithms
4. Dynamic Programming
5. Branch and Bound Algorithm
6. Randomized Algorithm
7. Backtracking

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Algorithm

 An algorithm is a sequence of computational

steps that transform the input into output.
(Thomas H. Cormen)

 An algorithm is a finite set of instructions that if

followed accomplishes a particular task.
(Sartaj Sahni)

An algorithm is a step by step procedure to

transform a given input to the desired output and
solve a computational problem (The computational •Start from the leftmost element of arr[] and one by one
problems is collection of questions that computer compare x with each element of arr[]
•If x matches with an element, return the index.
might be able to solve).
•If x doesn’t match with any of the elements, return -1.
Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit
 Pseudocode

It is one of the methods which can be used to represent an algorithm for a program. It does not have a
specific syntax like any of the programming language and thus can not be executed on a computer. It
allows you to include several control structure such as while, if-else etc.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Program

It is exact code written for problem

following all the rules of the
programming language.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 PROBLEM

ALGORITHM

PROGRAM

COMPUTER

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Why Analysis of Algorithms

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Why Analysis of Algorithms

• Execution Time
• Number of statements executed

• Running Time

• It is the process of determining how processing time increases as the

size of the problem increases.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 …..Thanks

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Design & Analysis of Algorithms (160401)

LECTURE 2

DR. ABHISHEK DIXIT

Assistant Professor,
Deptt. of IT
Madhav Institute of Technology & Science, Gwalior MITS, Gwalior
 OUTLINE

 Steps to plan an Algorithm.

 Characteristics of an Algorithm.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Steps to plan an Algorithm

How to devise an algorithm?

How to validate an algorithm?

How to analyse an algorithm?

How to test a program?

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 How to devise an • By using various designing techniques like
algorithm? Divide & Conquer, Greedy Method etc.

• Once an algorithm is devised, it is

necessary that it shows correct answer.
How to validate an
• One simple way is to code a program and
algorithm? check whether it provides reasonable
output or not.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 • Analysis of an algorithm or performance of
How to analyse an an analysis refers to the task of
algorithm? determining how much computing time and
storage an algorithm requires.

• Testing a program consists of two phases

debugging and profiling (or performance
measurement).
How to test a • Debugging is the process of executing programs to
determine whether faulty results occurs or not, if so
program? to correct them.
• Profiling is the process of executing a correct
program and measure the time and space it takes to
compute the results.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Characteristics of an Algorithm

INPUT

OUTPUT

DEFINITENESS

FINITENESS

EFFECTIVENESS

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 INPUT OUTPUT DEFINITENESS

Zero or more Each instruction must

At least one
quantities are be clear and
quantity is
externally unambiguous.
produced.
supplied. • Directions such as
“add 6 or 7” to x or
compute “5/0” are not
permitted because it is
not clear that what
should be done or
what will be the result
with these two
possibilities.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 FINITENESS EFFECTIVENESS

If we trace out the

Every instruction must be
instructions of an
very basic so that it can be
algorithm, then for all
carried out, in principle by a
cases the algorithm
person using only pen and
terminates after a finite
paper.
number of steps.

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 …..Thanks

Madhav Institute of Technology & Science, Gwalior Dr. Abhishek Dixit

 Design & Analysis of Algorithms

LECTURE 3

ABHISHEK DIXIT
Assistant Professor,
Deptt. of IT
MITS, Gwalior
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
 OUTLINE
 Algorithm Analysis
 Complexity of an Algorithm
 Asymptotic Notations

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Algorithm Analysis

Efficiency of an
algorithm can be
analysed at two • APRIORI ANALYSIS
different stages,
before
implementation and • APOSTERIOR ANALYSIS
after
implementation.

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Algorithm Analysis

Apriori Analysis Aposterior Analysis

• Theoretical analysis of an • Empirical analysis of an

algorithm. algorithm.
• Measured by factors like • Actual statistics like running time
processor speed must be constant and space required are collected.
and must not have effect on
implementation.

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Complexity of an Algorithm

Time Complexity - Time complexity of an algorithm is the amount of time

taken by an algorithm to run as a function of the length of the input.

Space Complexity - Similarly, Space complexity of an algorithm is the

amount of space or memory taken by an algorithm to run as a function of the
length of the input.

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 P

A1 A2 A3 A4 A5

Out of the many possible algorithms for given problem

‘P’ we choose that algorithm which takes less time &
less storage space.

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Asymptotic Notations

 Asymptotic Notations are mathematical notations that are used to analyze an algorithm’s running
time by identifying its behaviour as the input size for the algorithm increases.
OR
 Asymptotic Notation is used to describe the running time of an algorithm - how much time an
algorithm takes with a given input, n.
 This is also known as an algorithm’s growth rate.

i. Big-O Notation
ii. Omega Notation
iii. Theta Notation
iv. Little-o Notation
v. Little omega Notation
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
 Big-O Notation

 It represents the upper bound of the running time of an algorithm.

 n= input size ; t= time ; c= constant
 After some input n0 value of function c.g(n) will always be
greater or equal to than f(n).

f(n) ≤ c.g(n)
for n ≥ n0 ; c > 0 ; n0 ≥ 1

Therefore,

f(n) = O g(n)

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Omega Notation

 It represents the lower bound of the running time of an algorithm.

 n= input size ; t= time ; c= constant
 After some input n0 value of function c.g(n) will always be
lesser than or equal to f(n).

f(n) ≥ c.g(n)
for n ≥ n0 ; c > 0 ; n0 ≥ 1
Therefore,

f(n) = Ω g(n)

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Theta Notation

 It represents the average bound of the running time of an algorithm.

 n= input size ; t= time ; c= constant
 After some input n0 value of function f(n) will be sandwiched
between c1g(n) and c2g(n).

c1g(n) ≤ f(n) ≤ c2g(n)

for n ≥ n0 ; c > 0 ; n0 ≥ 1

Therefore,

f(n) = Ѳ g(n)

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

  Little-o Notation
f(n) = o g(n) if, f(n) < c.g(n)
for some constant n0 and c.

 Little omega Notation

f(n) = ω g(n) if, f(n) > c.g(n)
for some constant n0 and c.

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Worst Case

Average Case
Time Taken

Best Case

Input Size

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 EXAMPLE:

Perform linear search to find element x in given array.

10 20 5 25 30 45

 Now, if x is found at 1st position then,

Best Case Time =
 if x is found at last position then,
Worst Case Time =
 if x is found at middle of an array then,
Average Case Time =

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 …..Thanks

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Design & Analysis of Algorithms

LECTURE 4

ABHISHEK DIXIT
Assistant Professor,
Deptt. of IT
MITS, Gwalior
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
 OUTLINE
 Order of Growth of Functions
 Asymptotic Notation Properties

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Order of Growth of Functions

1< log n < √ < n < n log n < < 2 < n!

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
 PRACTICE SET

 Arrange the following functions in increasing order.

a) n1/3 b) en c) n7/4 d) n log n e) 1.00001n

i. ABCDE
ii. DACEB
iii. ADCEB
iv. ACDEB

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Properties
 Reflexivity
 Symmetry
 Transitivity
 Transpose Symmetry

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Properties

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Design & Analysis of Algorithms

LECTURE 5

ABHISHEK DIXIT
Assistant Professor,
Deptt. of IT
MITS, Gwalior
Madhav Institute of Technology & Science, Gwalior
 Time Complexity Analysis

Algorithm

Iterative Recursive
A() A()
{ {
for( i=1 to n) if ( )
max(a,b) {
} A( )
}
}

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
Madhav Institute of Technology & Science, Gwalior Abhishek Dixit
 Time Complexity Analysis : Iterative Functions

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Time Complexity Analysis : Iterative Functions

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Time Complexity Analysis : Iterative Functions

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 Time Complexity Analysis Methods

 Substitution Method
 Iteration Method
 Recursion Method
 Master Method

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit

 …..Thanks

Madhav Institute of Technology & Science, Gwalior Abhishek Dixit