Silicon Institute of Technology

Design and Analysis of

Algorithm

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology Definition of Algorithm
• A step‐by‐step problem‐solving procedure.

• A sequence of instruction that tell how to solve a particular problem.

• A set of instruction for solving a problem, especially on a computer.

• A computable set of steps to achieve a desired result.

However, most agree that algorithm has something to do with defining

generalized processes to get “output” from the “input”.

Design and Analysis of Algorithm

Silicon Institute of Technology Definition of Algorithm
Therefore, we can conclude that:

Algorithm a step‐by‐step problem solving process in which a solution is

arrived in a finite amount of time

OR

An algorithm is a finite list of sequential steps specifying actions that if

performed result in solution of a specific problem.

Design and Analysis of Algorithm

Silicon Institute of Technology Design and Analysis of Algorithms
Analysis: predict the cost of an algorithm in terms of resources
and performance

CPU Time vs Memory Footprint

Design: design algorithms which minimize the cost

Design and Analysis of Algorithm

Silicon Institute of Technology Algorithm : Goals and Representation
Basic goals for an algorithm:
• always correct
• always terminates
• Performance ( Most important for this class)

Representation of Algorithm
1. Give a description in your own language, e.g. English, Spanish, …
2. Pseudo code
3. Graphical

Design and Analysis of Algorithm

Silicon Institute of Technology Performance
Performance often draws the line between what is possible and what is
impossible.
❑ Machine Dependent : Can observe real runtime by running it on a machine.
❑ Machine Independent : Run Time Estimation

Our Machine Model

▪ Generic Random Access Machine (RAM)
▪ Executes operations sequentially
▪ Set of primitive operations: Arithmetic. Logical, Comparisons, Function calls
▪ Simplifying assumption: all operations cost 1 unit
▪ Eliminates dependence on the speed of our computer, otherwise impossible to verify and to
compare
Design and Analysis of Algorithm
Silicon Institute of Technology Algorithm Example
multiplying two positive integers A and B

For example: 45*19

Usually:
45
19 (x
405
45 (+
855

Design and Analysis of Algorithm 7

Silicon Institute of Technology Algorithm Example

A different approach to the same problem:

Multiplier Multiplicand Result
(A/2) (B*2) (pick numbers in column 2 when the corresponding
number under the multiplier is odd)

45 19 19
22 38
11 76 76
5 152 152
2 304
1 608 608 (+
855

Design and Analysis of Algorithm 8

Silicon Institute of Technology Terminology
An instance of a problem is a specific assignment of values to the
parameters.

This algorithm can be used for multiplying any two positive integers, we say
that (45, 19) is an instance of this problem. Most problems have infinite
collection of instances.

It’s ok to define the domain (i.e. the set of instances) to be considered, and
the algorithm should work for all instances in that domain.

Although the above algorithm will not work if the first operand is negative,
this does not invalidate the algorithm since (-45, 19) is not an instance of
the problem being considered.
Design and Analysis of Algorithm 9
Silicon Institute of Technology Order
Usually we use the frequency count to compare algorithms.
Consider the following 3 programs:

(a) (b) (c)

x←x+y for i ← 1 to n do for i ← 1 to n do
x←x+y for j ← 1 to n do
Program
end x←x+y
Snippets
end
End
Frequency
1 n n2
Count

No matter which machine we use to run these programs, we know that the execution time of
(b) is n times the execution time of (a).

Design and Analysis of Algorithm 10

Silicon Institute of Technology General Concepts
• Algorithm strategy
• Approach to solving a problem
• May combine several approaches
• Algorithm structure
• Iterative  execute action in loop
• Recursive  reapply action to subproblem(s)
• Data structure
• Problem type
• Satisfying  find any satisfactory solution
• Optimization  find best solutions (vs. cost metric)

Design and Analysis of Algorithm

Silicon Institute of Technology Some Algorithm Strategies
• Recursive algorithms
• Backtracking algorithms
• Divide and conquer algorithms
• Dynamic programming algorithms
• Greedy algorithms
• Brute force algorithms
• Branch and bound algorithms
• Heuristic algorithms

Design and Analysis of Algorithm

Silicon Institute of Technology Basic of Algorithm Analysis
• Algorithm Complexity Theory:
It’s a branch of algorithm study that deals with analysis of algorithm in terms of
usage of computational Resource such as Time and Space (Performance)

Time Complexity :
Time complexity deals with finding out how the computational time of an algorithm changes
with the change in size of the input
Space Complexity:
Space complexity deals with finding out how much (extra)space would be required by the
algorithm with change in the input size
Not Much importance is given to space complexity:
• Less Cost/ Can be easily increased
• Incase of Embedded System and Mobile applications or memory constraint applications
this is emphasized

Design and Analysis of Algorithm

Silicon Institute of Technology Measures of Algorithm Analysis
Measures of
Algorithm Analysis

• Ease of implementation • Resource Requirement

• Algorithm Style
Subjective
Objective Measures • Computation Time
• Understandability Measures • Memory Requirements

Static Dynamic
Objective Measures Objective Measures
(Program Length) (Time and Space)

Design and Analysis of Algorithm

Silicon Institute of Technology Time Complexity Analysis
• Mathematical Analysis ( a priori analysis/ Theoretical Analysis)
• This is done before the algorithm is translated into a program
• Estimates complexity in terms of step count or operation count
• Independent of particular Machine, Programming Language, OS or compiler

• Empirical Analysis ( Posteriori analysis)

• This is done after the algorithm is translated into a program
• Program is analyzed with real-time datasets
• Advantage is finding actual speed of the program in the field.

Design and Analysis of Algorithm

Silicon Institute of Technology Analysis of Iterative algorithm
1. Measure the Input Size, i.e the length of the input data(n or N)
As we believe computation time is dependent on input size.
2. Measure the running time using either step count or operation
count
3. In case of operation count, find the worst, best and average case
efficiency (dependent on distribution of input data)
4. Identify the rate of growth.(performance of the algorithm when the
input size is scaled higher)

Design and Analysis of Algorithm

Silicon Institute of Technology Analysis of Iterative Algorithms

Algorithm Analysis

Asymptotic Recurrence Amorttized

Step Count Operation Count
Analysis Relation Analysis

Design and Analysis of Algorithm

Silicon Institute of Technology Step Count
Sample Program Step no Program Step per execution Frequency Total
Simple(a, b, c) 1 Simple(a, b, c) 0
Begin 2 Begin 0
a= b+1 3 a= b+1 1 1 1
c=a+2 4 c=a+2 1 1 1
d=a+b 5 d=a+b 1 1 1
end 6 End 0
Total 3

T(n) =3

Design and Analysis of Algorithm

Silicon Institute of Technology Step Count : another example
Sample Program Step no Program Step per execution Frequency Total
1 Sum( ) 0
Sum( )
2 Begin 0
Begin
3 sum=0.0 1 1 1
sum=0.0
4 for i=1 to n do 1 n+1 n+1
for i=1 to n do
5 sum = sum +1 1 n n
sum = sum +1
6 end for 0 0 0
end for
Return sum 7 Return sum 1 1 1
end 8 end 0 0 0
Total 2n+3

T(n) =2n+3

Design and Analysis of Algorithm

Silicon Institute of Technology Operation Count
Step Program Operations Cost of Repetation Total
Sample Program
no Operation per Cost
Execution
Sum( )
1 Sum( ) 0
Begin
sum=0.0 2 Begin 0
for i=1 to n do 3 sum=0.0 Assignment c1 1 c1
sum = sum +1 4 for i=1 to n do Initialization, c2 n+1 (n+1)c2
compare
end for
update
Return sum sum = sum +1
5 Perform sum c3 n nc3
end
6 end for 0 0 0
7 Return sum c4 1 C4
8 end 0 0 0
Total c1 + (n+1)c2 + nc3+c4

T(n) =(c2+c3)n+c1+c2+c4
Design and Analysis of Algorithm
Silicon Institute of Technology Analysis as dominant operation
for i ← 1 to n do
for j ← 1 to n do
x←x+y
end
end T(n) =c1 n2 + c2 n + c3
for i ← 1 to n do Can be ignored for larger value of n

x←x+y
end
x←x+y

Design and Analysis of Algorithm

Silicon Institute of Technology Best, worst and average case Complexity
• Complexity not only depends upon size of input but also distribution
of input data.
• Worst case complexity defines T(n) as a complexity function W(n)
where

W(n) = Max1≤ i ≤ k{Ti(k)}

• Gives the upper bound to the execution Time
• It is crucial as it measures the maximum computational effort
required
Linear Search : Key value is present as the last value in the array or it
is not present.
Design and Analysis of Algorithm
Silicon Institute of Technology Best, worst and average case Complexity
Best Case Complexity: is the minimum computation of the algorithm

B(n) = Min1≤ i ≤ k{Ti(k)}

Best case for the linear search occurs when the item is present in the
first position of the given list.
So B(n) =1

This defines the ideal or lower bound of the algorithm.

Design and Analysis of Algorithm

Silicon Institute of Technology Best, worst and average case Complexity
Average Case Complexity:
Average case analysis assumes the inputs are random, and provides
prediction of execution time when inputs are random.

A(n) = σ𝑘𝑖=1 𝑃𝑖 𝑋 𝑇𝑖 (𝑛)

Where 𝑃𝑖 is the probability of instance i
For linear search the probability of presence of item in an array is
1
𝑃𝑖 =
𝑛
1 1 1 1
So A(n) = 1. + 2. + 3. + . . . +n .
𝑛 𝑛 𝑛 𝑛
𝑛 1 𝑛 𝑛+1 𝑛+1 𝑛
= (1+2+3 . . .+n) = = =
2 𝑛 2 2 2
Design and Analysis of Algorithm
Silicon Institute of Technology Rate of Growth
• Measure of complexity of the algorithm T(n) for larger value of n
• Compare it with collection of function that have same growth rate so
that the algorithm can be classified and ranked
Example three algorithms with T(n)
TA(n) = 7n TB(n) = log10 n TC(n) = n2
What if n is increased from 100 to 10,000
TA(10,000) 7 𝑋 10,000
= = 100
TA(100) 7 𝑋 100
TB(10,000) log 10000 4
= = =2
TB(100) 𝑙𝑜𝑔 100 2
TC(10,000) 100002
= = 10,000
TC(100) 1002

Design and Analysis of Algorithm

Silicon Institute of Technology Algorithm Classes

Function Name Name used in Algorithm Remarks

analysis
C Constant Algorithm Independent of input size
Log Log N Log of Log function Growth rate is very log
Log N Logarithmic Slow growth rate
N Linear algorithm Linear algorithms are preferred
N log N N-Log-N Very popular algorithm like merge sort falls here
N2 Quadratic General sorting algorithms
N3 Cubic Matrix Multiplication
Nk Polynomial Lesser order of k are preferred
aN Exponential Usage of resource is very high (Intractable)
N! Factorial Intractable algorithms

Design and Analysis of Algorithm

Silicon Institute of Technology Comparison of growth for classes

Design and Analysis of Algorithm

Silicon Institute of Technology Comparison in terms of Execution Time
10 6 instructions/sec, runtimes
N O(log N) O(N) O(N log N) O(N2)
10 0.000003 0.00001 0.000033 0.0001

100 0.000007 0.00010 0.000664 0.1000

1,000 0.000010 0.00100 0.010000 1.0

10,000 0.000013 0.01000 0.132900 1.7 min

100,000 0.000017 0.10000 1.661000 2.78 hr

1,000,000 0.000020 1.0 19.9 11.6 day

1,000,000,000 0.000030 16.7 min 18.3 hr 318 centuries

Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Asymptotic Analysis

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology

T1(n) = n2 + n
Lets assume each algorithm takes 1 sec to execute for n=100
How long will it take for n=1000?
T2(n) = n2

Time1 = 1 x = 99.1 (approx.)

Time2 = 1 x = 100

Between Time1 and Time2 there is not much difference so we can

ignore the lower order terms and constants.
Silicon Institute of Technology Asymptotic Analysis
• Analysis of a given algorithm with larger number of input data is called
asymptotic analysis.
• Asymptotic Analysis is the theory of approximation (Greek word for
Approximation)
• For Bigger algorithms where finding exact time complexity is difficult by
the process of counting, Asymptotic analysis can be very effective.
• Also limit theory is helpful in specifying this type of algorithm behavior.
For example
T(n) = when n becomes larger can be neglected
T(n) = 𝑛2 ( we say 𝑛2 is the asymptotic behavior of T(n) when n → ∞)
Design and Analysis of Algorithm
Silicon Institute of Technology

• In general a limit of two complexity function can be written as

• If the limit is a positive constant c, then both the complexity function

are of the same order and grow at the same rate.
• If the limit is zero , 𝑇2 (𝑛) grows faster
• If the limit is ∞, 𝑇1 (𝑛) grows faster
Silicon Institute of Technology Asymptotic Notation
• Asymptotic notations are helpful in classifying Algorithms and also
defining upper and lower bound of algorithm
Big-Oh Notation (O)
Big-Oh notation can be used in the following instances

1. For expressing the upper bound or the worst-case complexity of an

algorithm
2. For expressing that ‘time complexity is never more than’ or ‘at
most’ the given complexity function
Silicon Institute of Technology Big-Oh Notation (O)
Definition: Let t and g be the two functions that 𝑂 𝑔 𝑛 = {f(n): there exist positive
map a set of natural numbers to a set of positive constant c and n0 such that 0 ≤ f(n) ≤ cg(n)
real number N → 𝑅≥0 for all n > n0}

Let O(g) be the set of all functions with a similar

growth rate.
The relation t(n) = O(g(n)) holds good if and only if
there exist two positive constants c and n0 such
that
t(n) ≤ c x g(n) ∀ n > n0
The function t(n) is said to be in O(g(n)) means
t(n) ∈ 𝑂 𝑔 𝑛 But represented as t(n) = O(g(n))
The Upper Bound of an algorithm is given by Big-Oh.
Silicon Institute of Technology Big-Oh Notation (O)
Let t(n) = 3n3 for an algorithm. Prove that t(n) of the algorithm is in O(n 3)

Solution:
As per definition of Big-Oh notation t(n) ≤ c g(n)

So we need to prove 3n3 ≤ cn3 for some positive value of c.

and we can see for all value of c ≥ 4 this relation holds good
So t(n) is in O(g) or the algorithm is in O(n3)
Silicon Institute of Technology Big-Oh Notation (O)
Let t(n) = 3n3+ 2n2 + 3 for an algorithm. Let g(n) = n3. Prove that t(n) of
this algorithm is in O(g(n))

So we need to show
3n3+ 2n2 + 3 ≤ cn3 for some positive integer c
t(n) = 3n3+ 2n2 + 3
≤ 3n3+ 2n3 + 3n3 (as 2n3 > 2n2 and 3n3> 3n for any positive
integer n)
≤ 8n3
So t(n) ≤ 8n3 → t(n) is in O(n3)
Silicon Institute of Technology Big-Oh Notation (O)
Let t(n) = (2n3+ 13 log n)/7n2 for an algorithm. Prove that t(n) of this
algorithm is in O(n)
It can be observed that log n < n always hold good
So 13 log n < 13n and 13n < 13 n3
so t(n) ≤ (2n3 + 13 n3) / 7n2
≤ 15 n3 / 7n2
≤(15/7) n
≤3n
So t(n) is in O(n)
Silicon Institute of Technology Properties of Big-Oh notation
• For big-Oh analysis only the dominating summands maters. For
example O(4n4+7n2+7) = O(n4), all term other than highest degree are
ignored.
• In addition, in the big-Oh notation, the constant factors are not
significant. For example O(3n2) = O(n2)
• Big-Oh can be used to express tight bounds.
• A bound is called tight bound or least upper bound if the difference
between the bound and the actual function is a constant.
• For example n2 can not be expressed as O(n3), it can only be
expressed in O(n2), as it is the best fit.
Silicon Institute of Technology Big-Omega Notation(Ω)
Definition: Let t and g be the two functions that
map a set of natural numbers to a set of positive Ω 𝑔 𝑛 = {f(n): there exist positive
real number N → 𝑅≥0 constant c and n0 such that 0 ≤ cg(n) ≤ f(n)
for all n > n0}
Let Ω(g) be the set of all functions that have a
similar growth rate.
The relation t(n) = Ω(g(n)) holds good if and only if
there exist two positive constants c and n0 such
that
t(n) ≥ c x g(n) ∀ n > n0
The function t(n) is said to be in Ω(g(n)) means
t(n) ∈ Ω 𝑔 𝑛 But represented as t(n) = Ω(g(n))
The Lower Bound of an algorithm is given by Big-Omega.
Silicon Institute of Technology Big-Omega Notation(Ω)
Let t(n) = n4+ 3n3 + 2n +1 for an algorithm. Let g(n) = n4 + 1. Prove that
t(n) of this algorithm is in Ω(g(n))

So we need to show
n4+ 3n3 + 2n +1 ≥ c (n4 + 1) for some positive integer c
for all value of c > 0 this relation holds good
so t(n) is in Ω(g(n))
Silicon Institute of Technology Big-Omega Notation(Ω)
If the relation t(n) = 6n2 + 7n +8 holds, Prove that t(n) of not in Ω(n3)

t(n) can be in Ω(n3) only if

6n2 + 7n +8 ≥ c n3 which can not be true for any value of c > 0
so t(n) is not in Ω(g(n))
Silicon Institute of Technology Big-Theta Notation( )
Definition: Let t and g be the two functions that
map a set of natural numbers to a set of positive 𝜃 𝑔 𝑛 = {f(n): there exist positive
real number N → 𝑅≥0 constant c1, c2 and n0 such that
c1g(n) ≤ f(n) ≤ c2g(n) for all n > n0}
Let 𝜃(g) be the set of all functions that have a
similar growth rate.
The relation t(n) = 𝜃(g(n)) holds good if and only if
there exist two positive constants c1, c2 and n0
such that
c1g(n) ≤ f(n) ≤ c2g(n) ∀ n > n0
The function t(n) is said to be in 𝜃(g(n)) means
t(n) ∈ 𝜃 𝑔 𝑛 But represented as t(n) = 𝜃(g(n))

Both Lower and Upper Bounds of an algorithm is given by Big-Theta

Silicon Institute of Technology Big-Theta Notation( )
Let t(n) = n4+ 3n3 + 5n+1 for an algorithm. Let g(n) = n4+1. Prove that t(n) of
this algorithm is in 𝜃(g(n))

Here we have to prove

c1(n4+1) ≤ n4+ 3n3 + 5n+1 ≤ c2(n4+1) for some positive integer c1 and c2
for c1=1 first part of the inequality hold good
Now n4+ 3n3 + 5n+1 ≤ n4+ 3n4 + 5n4+9
≤ 9 (n4 +1)
So the above inequality holds good for c1=1 and c2=9
So t(n) is in 𝜃(g(n))
Silicon Institute of Technology Properties of Big-Theta Notation
The following are the properties of the Big-Theta Notation

1. If t(n) = O(g(n)) and g(n) = O(t(n)), then t(n) = 𝜃(g(n))

2. For any polynomial of the order of K, one can show that t(n) is in 𝜃(nk)
Silicon Institute of Technology examples of Big-Theta Notation
Consider an algorithm that is assumed to run in time O(n2) and that takes
only five seconds to compute result of an instance of size 30. how long
will the algorithm take to compute the results if the instance size is
increased to 50?
As t(n) is in O(n2)
t(n) ≤ c x (n2)
 cn2 steps = 5 sec
 c (30)2 = 5
 c = 5/ 900
Now for the second case t = c x (50)2 = 2500 x 5/900 = 125/9 = 13.88 secs
Silicon Institute of Technology examples of Big-Theta Notation
Supposed that an algorithm takes eight seconds to run on an input size n
=12. Estimate the instances that can be proposed in 56 secs. Assume that
the algorithm complexity is 𝜃(n)
As t(n) is in 𝜃(n)
12c = 8 sec
 c = 8/12 = 2/3
Now need to calculate n for t = 56
 c n= 56
 n = 56 x 3/2
 n = 84
Hence, the maximum input that is possible is 84
Silicon Institute of Technology Little-oh Notation
Little –Oh notation is similar to Big-Oh but it represents a loose bound
Definition :
The relation t(n) = o(g(n)) holds good, if there exist two positive
constants c and n0 such that

t(n) < c x g(n)

𝑡(𝑛)
if lim =0 then t(n) = o(g(n)) holds good
𝑛→∞ 𝑔(𝑛)
Silicon Institute of Technology Example for little-Oh
Let t(n) = 7n + 6. show that t(n) is in o(n2)

𝑡(𝑛)
As we know, if t(n) = o(g(n)) holds good when lim =0
𝑛→∞ 𝑔(𝑛)

7𝑛+6 7 2
=> lim = lim + =0
𝑛→∞ n2 𝑛→∞ n 𝑛 2

This indicates t(n) is in o(n2)

Silicon Institute of Technology Little-Omega notation
The relation t(n) = 𝜔 𝑔 𝑛 holds good if there exist two positive
constants c and n0 such that t(n) > c (g(n))

The relation holds good if and only if

Silicon Institute of Technology Tilde Notation(~)
The notation is useful when the function t(n) and g(n) grow at the same
rate. The formal definition of this notation is

So if f(n) and g(n) grows at the same growth. Then one can write that

t(n) ~ g(n)
Silicon Institute of Technology Asymptotic Rules
Reflexive Rule
t(n) = O(g(n))
t(n) = Ω(g(n))
=> t(n) = 𝜃(g(n))
Transitivity Rule
If t(n) = O(g(n)) and g(n) = O(h(n))
Then t(n) = 𝑂(h(n))
Law of Composition
If O(O(t(n))) = O(t(n))
Silicon Institute of Technology Law of Addition
Segment 1: complexity -> n
Segment 2: complexity -> log n Total Complexity = n + log n + n2
Segment 3: complexity -> n2

t(n) + g(n) = O(max{t(n), g(n)})

t(n) + g(n) = Ω(max{t(n), g(n)}))
t(n) + g(n) = (max{t(n), g(n)}))
Silicon Institute of Technology Law of Multiplication
Multiplication of complexity of two functions equals to the product of
two complexity functions
Let t1(n) = O(g1(n)) and t2(n) = O(g2(n)
t1(n) ≤c1g1(n) ∀ 𝑛 > 𝑛1 and t2(n) ≤c2g2(n) ∀ 𝑛 > 𝑛2
Let K be a number greater then c1 x c2 and n0 = max{n1,n2}
 t1(n) x t2(n) ≤ c1g1(n) x c2g2(n)
≤ k g1(n) x k g2(n)
≤ k2 (g1(n) x g2(n) ) ∀ 𝑛 > 𝑛0

=> There for t1(n) x t2(n) is in O (g1(n) x g2(n))

Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Recurrence Relation

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology Recurrence Equation
Iterative algorithms are easy to analyse. But its difficult to analyse
Recurrence algorithm.
As its easy to count number of basic operations where as its difficult to
find count of basic operations and also the number of time recursive
function will call itself.
For analysis of recursive algorithms we need to formulate recurrence
Equation.
A Recurrence Equation defines a sequence using the elements of that
sequence so its helpful in analysing them too.
Silicon Institute of Technology Analysis of Recursive Algorithm
To analyse recursive algorithm one need to
1. Formulating recurrence equation for given recursive problem
2. Solving the recurrence equation to understand the behaviour of the
program.
Whether Recurrence Relation and Recurence Equation are same??
A recurrence Relation is basically a definition of a function in terms of itself. For
Example
n! = n x (n - 1)! With base condition as 0! = 1
Where as a recurrence equation is a discrete equivalent of a differential equation
that express a term of sequence as a function of its preceding term. For factorial
T(n) = T(n-1) + 1 or tn = tn-1 +1 where t0 = 0
1 here indicates one addition multiplication is required..
Silicon Institute of Technology

A recurrence equation is also known as difference equation

Example Can also be written as
T(n) = T(n-1) + 2
T(0) = 0;
We can use a simple notation Substitute n=1, 2, 3…
tn = tn-1 +2 t1 = t0 + 2 = 2
t0 = 0 t2 = t1 + 2 = 4
t3 = t2 + 2 = 6
. . .
Even number sequence
But depends upon Initial Condition
Silicon Institute of Technology Linear and Non Liner Recurrence
Linear Recurrence Equation
Recurrence Relation In liner recurrence equation the final term tn is a linear
combination of its previous terms in a polynomial form.

Example Fibonacci Series

tn = tn-1 + tn-2
In general term recurrence equations are represented in the
Linear Non Linear
following form
Recurrence Relation Recurrence Relation
a0tn + a1tn-1 + a2tn-2 .... + aktn-k = f(n)
Non Linear Recurrence Equation
If in a recurrence equation the final term tn is a non linear combination of its previous terms

𝑛 𝑛
𝑇 𝑛 = 𝑎𝑇 𝑏
+ 𝑓(𝑛) where a is the number of sub problem of size 𝑏 each and f(n) is the cost of work
done as non recursive call. Binary
Silicon Institute of Technology Order of Recurrence Equation
The number of preceding terms are being used for computing the
present term is known as order of the recurrence equation

a0tn + a1tn-1 = f(n) ------- First order recurrence equation

a0tn + a1tn-1 + a2tn-2 = f(n) ------- Second order recurrence equation

a0tn + a1tn-1 + a2tn-2 .... + aktn-k = f(n) ------- Order K

For Fibonacci Series tn = tn-1 + tn-2

tn - tn-1 - tn-2 = 0
Silicon Institute of Technology Homogeneous vs Non-Homogeneous
In the recurrence equation
a0tn + a1tn-1 + a2tn-2 .... + aktn-k = f(n)

If f(n) = 0, then the equation is homogeneous

tn = tn-1 + tn-2 tn = tn-1 + (n-3)

Homogeneous Test: Replace all t terms with zero and see the equation
Silicon Institute of Technology Constant vs Variable Co-efficient
a0tn + a1tn-1 + a2tn-2 .... + aktn-k = f(n)

In the above equation the coefficient term ai can be constant or

variable.
Example

tn = n x tn-2

In algorithm study equation with variable co-efficient will be rare.

Silicon Institute of Technology Technique for Solving Recurrence Equations

A solution for Recurrence is a non recursive formula that satisfies the

recurrence equation for all range of values

Following methods are used to solve Recurrence Equation

1. Method of Substitution
2. Recurrence Tree Method
3. Master Method
Silicon Institute of Technology Substitution Method
Substitution for solving recurrence method comprises of two steps

1. Guess the form of solution

2. Use mathematical induction to find the constants and show the induction
works

As the first step guess the solution by substituting the different values of n to
generate the sequence from the recurrence equation

Verify the solution using technique of mathematical induction. Once verified

solution of the problem established.
Silicon Institute of Technology Substitution Method: Example
Solve the recurrence equation
tn = tn-1 +2
t0 = 1
For making a guess, use different value of n in the recurrence equation
t0 = 1
t1 = t0 + 2 = 1 + 2 = 3 It is a series of odd number, starting with one and
every term differs from its previous term by 2.
t2 = t1 + 2 = 3 + 2 = 5 tn = 2n +1 (non recurrence solution)
t3 = t2 + 2 = 5 + 2 = 7

If we assume its true for n and then proof for n+1 then method of
induction can be established
Silicon Institute of Technology Substitution Method: Example
Verify
Let n=0 : t0 = 2 x 0 + 1 = 1
Let n=1 : t1 = 2 x 1 + 1 = 3
Let n=2 : t3 = 2 x 2 + 1 = 5

Lets for n the following equation holds good => tn = 2n +1

Now test for tn+1.
tn+1 = t(n+1)-1 + 2
= tn + 2 = (2n +1) + 2 = 2n +2 +1 = 2(n+1) +1
=> tn+1 = 2(n+1) +1 (∴ as per method of induction its true for all n)
Silicon Institute of Technology Another Example
Solve the recurrence equation
𝑛
T(n) = 3T 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑇 1 = 1
2
Note that n>1 and power of 2
T(1) = 1
2
T(2) = 3T = 3 T(1) = 3 x 1 =3
2
4
Solutions look like
T(4) = 3T = 3 T(2) = 3 x 3 = 32
2
8
𝑡𝑛 = 3𝑙𝑜𝑔2 𝑛
T(8) = 3T 2
3 T(4) = 3x 32 = 33
16
T(8) = 3T 2
3 T(8) = 3x 33 = 34

Lets the equation holds good for n , i.e. 𝑡𝑛 = 3𝑙𝑜𝑔2 𝑛

2𝑛
Now T(2n) = 3T = 3 𝑇 𝑛 = 3 𝑥 3𝑙𝑜𝑔2𝑛 = 31+ 𝑙𝑜𝑔2 𝑛
2
𝑙𝑜𝑔22+ 𝑙𝑜𝑔2𝑛
=3 = 3 𝑙𝑜𝑔2 2𝑛
=> T(2n) = 3 𝑙𝑜𝑔22𝑛 (∴ as per method of induction its true for all n)
Silicon Institute of Technology Another Example
Solve the recurrence equation to find the upper bound on the recurrence
𝑛
T(n) = 2T +𝑛
2
We guess the solution to be T(n) = O(n log n) and lets assume it is true for n/2

𝑇( 𝑛/2 ) ≤ 𝑐 𝑛/2 lg ( 𝑛/2 ) + 𝑛

𝑛
T(n) = 2T +𝑛
2
≤ 2[𝑐 𝑛/2 lg ( 𝑛/2 )] + 𝑛
≤ 𝑐𝑛 lg (n/2) + 𝑛
= 𝑐𝑛 lg n - 𝑐𝑛 lg 2 + 𝑛
= 𝑐𝑛 lg n - 𝑐𝑛 + 𝑛
≤ 𝑐𝑛 lg n ( for all c ≥ 1)
Silicon Institute of Technology Iteration Method
Steps:
1. Expand the Recurrence
2. Express the expansion as a summation by plugging the recurrence
back to it self
3. Find out a pattern and create the general equation, and use the
value of initial condition to find out the value of the variables in the
equation.
Silicon Institute of Technology Iteration Method Example
T(n) = T(n-1) + 3
Base Condition: T(0) = 2
T(n) = T(n-1) + 3
But T(n-1) = T(n-2) + 3
 T(n) = T(n-2) + 3 + 3 = T(n-2) + 6
Again T(n-2) = T(n-3) +3
T(n) = T(n-3) + 3 + 6 = T(n-3) + 9
General Term : T(n) = T(n-k) + 3k ( Now use Base condition to evaluate k)
If n=k, T(n) = T(0) +3n
=> T(n) = 2 + 3n ( Close Form)
Silicon Institute of Technology Iteration Method : Example
T(n) = 2T(n/2) + 1
Base Condition: T(0) = 1 Now
𝑛/22
T(n) = 2 T(n/2) +1 T(n/22) = 2T +1
2
𝑛/2 𝑛/22
T(n/2) = 2 T +1 T(n) = 22 2 T + 1 + 21 + 20
2 2
𝑛/2 𝑛
T(n) = 2 2 T + 1 +1 = 23 T
23 + 22 + 21 + 20
2
𝑛 General Equation
T(n) = 2 2 T + 1 +1
22 𝑛
𝑛 T(n) = 2k T 2𝑘 + 2k−1 + …. 21+ 20
T(n) = 22 T + 2 +1 𝑛
22 T(n) = 2k T + σ𝑘−1 2 𝑖
2𝑘 𝑖=0
𝑛
T(n) = 22 T 2 + 21 + 20 𝑛 2𝑘 −1
2 T(n) = 2k T +
2𝑘 2−1
Silicon Institute of Technology Iteration Method : Example
𝑛
T(n) = 2k T 𝑘 + 2𝑘 − 1 (General Form)
2
Now T(1) =1
𝑛
2𝑘
= 1 => n = 2k
𝑛
T(n) = n T 𝑛
+𝑛−1
T(n) = n +𝑛 − 1
T(n) = 2𝑛 − 1 (Close Form)
O(n)
Silicon Institute of Technology Recurrence Tree Method
It expands the recurrence equation in a tree like fashion( Visual Method)
Steps Involved
1. Formulate the recurrence equation by visualising the calls as a tree
2. Collect the following information from a recurrence tree
a) Level: Determine the level of the generated tree
b) Cost per level : Cost per level has to be calculated for each level of the generated
tree considering the size of the sub problem.
c) Total Cost: It’s the sum of the cost of all levels.
3. Express the complexity in terms of the Total Cost
4. Verify the summation using the method of substitution or some other
method.
Silicon Institute of Technology Recurrence Tree Method
𝑛
T(𝑛) = 2T + 𝑛 ( Recurrence equation for Merge Sort)
2

n
n
n
n/2 n/2
n/2 n/2

n/4 n/4 n/4 n/4

Silicon Institute of Technology Recurrence Tree Method
Level No of problems Problem Size Work Done

n 0 1 n n

n/2 n/2 1 2 n/2 n

Level = log2 n

2 4 n/4 n
n/4 n/4 n/4 n/4
….. ….. ….. ….
k 2k n/2k n
….. ….. ….. …..

1 1 1 1 log2 n 2log n = n 1 n
Total Work Done (1+log n) x n

Total Work Done = n + n log n which is in 𝜽(n log n) => Asymptotic bound is 𝜽(n log n)
Silicon Institute of Technology Another Example
Consider the following Recurrence
Determine the final asymptotic
complexity of the tree for a=1 and a=n

Level No of Problem Work Done Level No of Problem Work Done

Problems Size Problems Size

1 0 1 1 1 n 0 1 n n

1 1 1 1 n-1 1 1 n-1 n–1

1

2 1 1 1 2 1 n–2 n–2
n-2
1

...
…… …… …… ……
...

…… …… …… …..

1 n-1 1 1 1 1 n-1 1 1 1

Total Work Done n Total Work Done n(n+1) /2

Silicon Institute of Technology Another Example
Solve the following Recurrence equation and determine the asymptotic upper bound

The sub problems are increasing

80, 81, 82, 83,… 8i

Level = log n
the problem size is decreasing
𝑛 𝑛
𝑛, , , ….. 1 in log2n steps
2 4
Amount of work done in the last Level
= 8 log n x T(1) = n log 8 x 1 = n3
Work done at other levels : n - 4n - 16 n …. => 4in
𝑙𝑜𝑔𝑛−1 𝑖
σ
Total Work Done = 𝑖=𝑜 4 n + n3
Silicon Institute of Technology
𝑙𝑜𝑔𝑛−1 𝑖 𝑙𝑜𝑔𝑛−1 𝑖
Total Work Done = σ𝑖=𝑜 4 n + n3 = n σ𝑖=𝑜 4 + n3
=n + n3

=n + n3

=n + n3

= + n3 =
Silicon Institute of Technology Master Theorem
Simplified Master Theorem
Theorem
Let the Time Complexity function T(n) be a positive and eventually a
non-decreasing function of the following form

Where a, d, b, c, and k are all constants with following conditions

b ≥ 2 K ≥ 0 a>0 c>0 d ≥ 0
Silicon Institute of Technology Cases of Master Solution
Case 1: When a < bk
T(n) ∈ 𝜃(𝑛𝑘)

Case 2: When a = bk
T(n) ∈ 𝜃(𝑛𝑘log n)

Case 3: When a > bk

T(n) ∈ 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎
Silicon Institute of Technology
Format Recurrence Equation
𝑛 T(n) = 8 T(n/2) + n 2
T(n) = aT + c nk
𝑏 a = 8, b=2, c=1, k =2 (all preconditions satisfied)
T(1) = d a = 8 and bk = 22 = 4
Condition  a > bk (case 3)
Solution is: T(n) = 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎 = 𝜃 𝑛𝑙𝑜𝑔28 = 𝜃 𝑛3
b≥2 K≥0 a>0
c>0 d≥0
Cases Recurrence Equation
Case 1: When a < bk T(n) = 2 T(n/2) + n
Then T(n) ∈ 𝜃(𝑛𝑘)
a = 2, b=2, c=1, k =1 (all preconditions satisfied)
Case 2: When a = bk a = 2 and bk = 21 = 2
Then T(n) ∈ 𝜃(𝑛𝑘log n)  a = bk (case 2)
Solution is: T(n) = 𝜃 𝑛𝑘 𝑙𝑜𝑔𝑛 = 𝜃 𝑛1𝑙𝑜𝑔𝑛 = 𝜃 𝑛 𝑙𝑜𝑔𝑛
Case 3: When a > bk
Then T(n) ∈ 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎
Silicon Institute of Technology
Format Recurrence Equation
𝑛 T(n) = 2 T(n/4) + n
T(n) = aT + c nk
𝑏 a = 2, b=4, c=1, k =1 (all preconditions satisfied)
T(1) = d a = 2 and bk = 41 = 4
Condition  a < bk (case 1)
Solution is: T(n) = 𝜃 𝑛𝑘 = 𝜃 𝑛
b≥2 K≥0 a>0
c>0 d≥0
Cases Recurrence Equation
Case 1: When a < bk T(n) = 2n T(n/2) + 2n3
Then T(n) ∈ 𝜃(𝑛𝑘)
a = 2n, b=2, c=2, k =3 (Does all preconditions satisfied ?)
Case 2: When a = bk  Solution can not be found using
Then T(n) ∈ 𝜃(𝑛𝑘log n)
Case 3: When a > bk
Then T(n) ∈ 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎
Silicon Institute of Technology Generalized Master Theorem
Generalized Master Theorem
If the recurrence equation is of the form

Where a, d, and b are all constants with following conditions

a ≥ 1 b > 1 n0 ≥ 1 c > 0 d > 0 and f(n) should be positive for n > n0

Solution
𝑙𝑜𝑔𝑏𝑎 ∈
1. If f(n) = O 𝑛 /𝑛 for some constant ∈ > 0, then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 )
2. If f(n) = 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎 then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔 𝑛)
𝑙𝑜𝑔𝑏𝑎 ∈
3. If f(n) = Ω 𝑛 . 𝑛 for ∈ > 0 and af(𝑛/𝑏)≤ 𝜕𝑓 𝑛 𝑓𝑜𝑟 𝜕<1, then T(n) = 𝜃(𝑓(𝑛))
Silicon Institute of Technology Example
Condition: a ≥ 1 b > 1 n0 ≥ 1 d > 0 and f(n) should be positive for n > n 0
Solution
∈
1. If f(n) = O 𝑛𝑙𝑜𝑔𝑏𝑎 /𝑛 for some constant ∈ > 0, then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 )
2. If f(n) = 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎 then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔 𝑛)
∈
3. If f(n) = Ω 𝑛𝑙𝑜𝑔𝑏𝑎 . 𝑛 for ∈ > 0 and af(𝑛/𝑏)≤ 𝜕𝑓 𝑛 𝑓𝑜𝑟 𝜕<1, then T(n) = 𝜃(𝑓(𝑛))
Recurrence Equation
T(n) = 8 T(n/2) + n2

a = 8, b=2 and f(n) = n2

𝑛𝑙𝑜𝑔𝑏𝑎 = 𝑛𝑙𝑜𝑔28 = 𝑛3
∈
n2 = O(n3 / n ) when ∈ = 1 n2 = O(n2)

It matches with case 1, So the solution is

T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 ) = 𝜃(𝑛𝑙𝑜𝑔28 ) = 𝜃(𝑛3)
Silicon Institute of Technology Example
Condition: a ≥ 1 b > 1 n0 ≥ 1 d > 0 and f(n) should be positive for n > n 0
Solution
∈
1. If f(n) = O 𝑛𝑙𝑜𝑔𝑏𝑎 /𝑛 for some constant ∈ > 0, then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 )
2. If f(n) = 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎 then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔 𝑛)
∈
3. If f(n) = Ω 𝑛𝑙𝑜𝑔𝑏𝑎 . 𝑛 for ∈ > 0 and af(𝑛/𝑏)≤ 𝜕𝑓 𝑛 𝑓𝑜𝑟 𝜕<1, then T(n) = 𝜃(𝑓(𝑛))

Recurrence Equation
T(n) = 2 T(n/2) + n
a = 2, b=2 and f(n) = n
𝑛𝑙𝑜𝑔𝑏𝑎 = 𝑛𝑙𝑜𝑔22 = 𝑛
n = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 ) = 𝜃(𝑛)

It matches with case 2, So the solution is

T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔𝑛) = 𝜃(𝑛 𝑙𝑜𝑔𝑛)
Silicon Institute of Technology Example
Condition: a ≥ 1 b > 1 n0 ≥ 1 d > 0 and f(n) should be positive for n > n 0
Solution
∈
1. If f(n) = O 𝑛𝑙𝑜𝑔𝑏𝑎 /𝑛 for some constant ∈ > 0, then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 )
2. If f(n) = 𝜃 𝑛𝑙𝑜𝑔𝑏𝑎 then T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔 𝑛)
∈
3. If f(n) = Ω 𝑛𝑙𝑜𝑔𝑏𝑎 . 𝑛 for ∈ > 0 and af(𝑛/𝑏)≤ 𝜕𝑓 𝑛 𝑓𝑜𝑟 𝜕<1, then T(n) = 𝜃(𝑓(𝑛))

Recurrence Equation
T(n) = T(2n/3) + 1
a = 1, b=3/2 and f(n) = 1
𝑛𝑙𝑜𝑔𝑏𝑎 = 𝑛𝑙𝑜𝑔3/21 = 𝑛0 = 1
n = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 ) = 𝜃(1)

It matches with case 2, So the solution is

T(n) = 𝜃(𝑛𝑙𝑜𝑔𝑏𝑎 𝑙𝑜𝑔𝑛) = 𝜃(𝑙𝑜𝑔𝑛)
Silicon Institute of Technology Cases where Master Theorem Fails
𝑛
1. T(n) = 3n T + n (a should be a constant should not be dependent on n)
2
𝑛
2. T(n) = 0.3T + n (a should be greater than equal to 1)
2
𝑛
3. T(n) = T − n4 (f(n) can not be negative)
2
𝑛 𝑛
4. T(n) = 4T +
4 log 𝑛

Here = = = =
1 ∈
Although we know is less then n for any value of ∈ but they are not polynomially
𝑙𝑜𝑔𝑛
comparable
Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Divide and Conquer

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology Divide-and-Conquer
The most-well known algorithm design strategy:

1. Divide: Divide instance of problem into two or more smaller

instances

2. Conquer: Solve smaller instances recursively

3. Combine: Obtain solution to original (larger) instance by combining

these solutions

2
Silicon Institute of Technology Divide-and-Conquer Technique (cont.)

a problem of size n

subproblem 1 subproblem 2
of size n/2 of size n/2

a solution to a solution to
subproblem 1 subproblem 2

a solution to
the original problem

3
Silicon Institute of Technology Divide-and-Conquer Examples

• Sorting: merge sort and quicksort

• Multiplication of large integers
• Matrix multiplication: Strassen’s algorithm
• Closest-pair and convex-hull algorithms
• Binary search: decrease-by-half
• Binary tree traversals

4
Silicon Institute of Technology General Divide-and-Conquer Recurrence

T(n) = aT(n/b) + f (n) where f(n)  (nd), d  0

Master Theorem: If a < bd, T(n)  (nd)

If a = bd, T(n)  (nd log n)
If a > bd, T(n)  (nlog b a )

Note: The same results hold with O instead of .

Examples: T(n) = 4T(n/2) + n  T(n)  ?

T(n) = 4T(n/2) + n2  T(n)  ?
T(n) = 4T(n/2) + n3  T(n)  ?

5
Silicon Institute of Technology Merits and Demerits
Merit
• It is the most applied design technique
• It leads to effective recursive algorithm
• Recursive algorithms are compact and efficient compared to iterative
algorithm

Demerit
• They are not very effective when the division of the problem are
unbalanced
Silicon Institute of Technology Mergesort Example
8 3 2 9 7 1 5 4

8 3 2 9 7 1 5 4

8 3 2 9 71 5 4

8 3 2 9 7 1 5 4

3 8 2 9 1 7 4 5

2 3 8 9 1 4 5 7

1 2 3 4 5 7 8 9

7
Silicon Institute of Technology Mergesort
• Split array A[0..n-1] in two about equal halves and make copies of
each half in arrays B and C
• Sort arrays B and C recursively
• Merge sorted arrays B and C into array A as follows:
• Repeat the following until no elements remain in one of the arrays:
• compare the first elements in the remaining unprocessed portions of
the arrays
• copy the smaller of the two into A, while incrementing the index
indicating the unprocessed portion of that array
• Once all elements in one of the arrays are processed, copy the remaining
unprocessed elements from the other array into A.

8
Silicon Institute of Technology Pseudocode of Mergesort

Thinking about recursive programs: Assume recursive calls work

and ask does the whole program then work?
9
 Silicon Institute of Technology
Pseudocode of Merge

10
Silicon Institute of Technology Merge Sort Time Analysis
Merge(left[0…p-1], right[0…q-1], A[0…n-1])
{
i <- 0; j <- 0; k <- 0; C1

while i<p and j<q do

If left[i]<= right[j]
A[k] = left[i]; i <- i+1;
else
A[k] = right[j]; j <- j+1;
k <- k+1
n . C2

If (i=p)
copy right[j… q-1] to A[k… n-1]
else
copy right[i… p-1] to A[k… n-1]
}
Silicon Institute of Technology Merge Sort Time Analysis
MergeSort(A)
{
n = length(A) Time complexity
if (n < 2) return;
mid = n/2 Constant Time: C3
left <- array of size (mid)
right<- array of size (mid)
for I =0 to mid-1
left[i] = a[i]
Appling Master Theorem
for I =mid to n-1 n . C4
left[i-mid] = a[i] T(n) = 𝜃 (𝑛 log 𝑛)
MergeSort(left)
T( n/2) each total 2T(n/2)
MergeSort(right)

Merge(left, right, A) C1 + n. C2
}
Silicon Institute of Technology Space Complexity
MergeSort(A)
{
n = length(A)
if (n < 2) return;
mid = n/2
left <- array of size (mid)
right<- array of size (mid)
for I =0 to mid-1
left[i] = a[i]
for I =mid to n-1
left[i-mid] = a[i]

MergeSort(left)
MergeSort(right)

Merge(left, right, A)
}
Silicon Institute of Technology Space Complexity:
Additional Memory for Left and Right
L1 => 2 x 4 = 8
L2 => 4 x 2 = 8
L3 => 8 x 1 = 8
Log n layers n element each

Space Complexity = 𝜃( n log n)

Silicon Institute of Technology Optimising Memory Required
Level 1 : n elements
Level 2 : n/2 element
Level 3 : n/4 elements

So total additional memory for left and right

Sn = n + n/2 + n/4 + …..

= n (1 + 1/2 + 1/4 + ……)
We will clear the auxiliary array after merge
Here 1.n < Sn < 2. n
Silicon Institute of Technology

QUICK SORT
Silicon Institute of Technology QuickSort Design
• Follows the divide-and-conquer paradigm.
• Divide: Partition (separate) the array A[p..r] into two (possibly empty)
subarrays A[p..q–1] and A[q+1..r].
• Each element in A[p..q–1] < A[q].
• A[q] < each element in A[q+1..r].
• Index q is computed as part of the partitioning procedure.
• Conquer: Sort the two subarrays by recursive calls to quicksort.

• Combine: The subarrays are sorted in place – no work is needed to

combine them.
• How do the divide and combine steps of quicksort compare with
those of merge sort?
Silicon Institute of Technology Pseudocode
A[p..r]
Partition(A, p, r)
5
x := A[r]; I:= p – 1;
A[p..q – 1] A[q+1..r] for j := p to r – 1 do
Partition
5
if A[j]  x then
i := i + 1;
5 5 A[i]  A[j]
A[i + 1]  A[r];
Quicksort(A, p, r) return i + 1
if p < r then
q := Partition(A, p, r);
Quicksort(A, p, q – 1);
Quicksort(A, q + 1, r)
Silicon Institute of Technology Example
p r
initially: 2 5 8 3 9 4 1 7 10 6 note: pivot (x) = 6
i j

next iteration: 2 5 8 3 9 4 1 7 10 6
i j Partition(A, p, r)
x := A[r]; I:= p – 1;
next iteration: 2 5 8 3 9 4 1 7 10 6 for j := p to r – 1 do
i j if A[j]  x then
i := i + 1;
next iteration: 2 5 8 3 9 4 1 7 10 6 A[i]  A[j]
i j A[i + 1]  A[r];
return i + 1
next iteration: 2 5 3 8 9 4 1 7 10 6
i j
Silicon Institute of Technology Example (Continued)

next iteration: 2 5 3 8 9 4 1 7 10 6
i j
next iteration: 2 5 3 8 9 4 1 7 10 6
i j
next iteration: 2 5 3 4 9 8 1 7 10 6 Partition(A, p, r)
i j x:= A[r], i := p – 1;
next iteration: 2 5 3 4 1 8 9 7 10 6 for j := p to r – 1 do
i j if A[j]  x then
next iteration: 2 5 3 4 1 8 9 7 10 6 i := i + 1;
i j A[i]  A[j]
next iteration: 2 5 3 4 1 8 9 7 10 6 A[i + 1]  A[r];
i j return i + 1
after final swap: 2 5 3 4 1 6 9 7 10 8
i j
Silicon Institute of Technology Partitioning
• Select the last element A[r] in the subarray A[p..r] as the pivot – the element
around which to partition.
• As the procedure executes, the array is partitioned into four (possibly empty)
regions.
1. A[p..i ] — All entries in this region are < pivot.
2. A[i+1..j – 1] — All entries in this region are > pivot.
3. A[r] = pivot.
4. A[j..r – 1] — Not known how they compare to pivot.
• The above hold before each iteration of the for loop, and constitute a loop
invariant. (4 is not part of the loopi.)
p i j r
x

x >x
Silicon Institute of Technology Correctness of Partition
Use loop invariant.
Initialization:
• Before first iteration
• A[p..i] and A[i+1..j – 1] are empty – Conds. 1 and 2 are satisfied
(trivially).
• r is the index of the pivot
Partition(A, p, r)
• Cond. 3 is satisfied.
x:= A[r], i:= p – 1;
Maintenance: for j := p to r – 1 do
• Case 1: A[j] > x if A[j]  x then
i := i + 1;
• Increment j only.
A[i]  A[j]
• Loop Invariant is maintained. A[i + 1]  A[r];
return i + 1
Silicon Institute of Technology Correctness of Partition
Case 1:

p i j r
>x x

x >x
p i j r
x

x >x
Silicon Institute of Technology Correctness of Partition

• Case 2: A[j]  x • Increment j

• Increment i • Condition 2 is maintained.
• Swap A[i] and A[j] • A[r] is unaltered.
• Condition 1 is maintained. • Condition 3 is maintained.

p i j r
x x

x >x
p i j r
x

x >x
Silicon Institute of Technology Correctness of Partition
• Termination:
• When the loop terminates, j = r, so all elements in A are partitioned into one
of the three cases:
• A[p..i]  pivot
• A[i+1..j – 1] > pivot
• A[r] = pivot
• The last two lines swap A[i+1] and A[r].
• Pivot moves from the end of the array to between the two subarrays.
• Thus, procedure partition correctly performs the divide step.
Silicon Institute of Technology Quicksort Overview

To sort a[left...right]:
1. if left < right:
Partition a[left...right] such that:
all a[left...p-1] are less than a[p], and
all a[p+1...right] are >= a[p]
Quicksort a[left...p-1]
Quicksort a[p+1...right]
2. Terminate
Silicon Institute of Technology Partitioning in Quicksort
• A key step in the Quicksort algorithm is partitioning the array
• We choose some (any) number p in the array to use as a pivot
• We partition the array into three parts:

numbers less p numbers greater than or

than p equal to p
Silicon Institute of Technology Alternative Partitioning
• Choose an array value (say, the first) to use as the pivot
• Starting from the left end, find the first element that is greater than
or equal to the pivot
• Searching backward from the right end, find the first element that is
less than the pivot
• Interchange (swap) these two elements
• Repeat, searching from where we left off, until done
Silicon Institute of Technology Alternative Partitioning

To partition a[left...right]:
1. Set pivot = a[left], l = left + 1, r = right;
2. while l < r, do
2.1. while l < right & a[l] < pivot , set l = l + 1
2.2. while r > left & a[r] >= pivot , set r = r - 1
2.3. if l < r, swap a[l] and a[r]
3. Set a[left] = a[r], a[r] = pivot
4. Terminate
Silicon Institute of Technology Example of partitioning
• choose pivot: 436924312189356
• search: 436924312189356
• swap: 433924312189656
• search: 433924312189656
• swap: 433124312989656
• search: 433124312989656
• swap: 433122314989656
• search: 433122314989656
• swap with pivot: 133122344989656
Silicon Institute of Technology Partition Implementation (C)

int Partition(int a[], int left, int right) {

int p = a[left], l = left + 1, r = right;
while (l < r) {
while (l < right && a[l] < p) l++;
while (r > left && a[r] >= p) r--;
if (l < r) {
int temp = a[l]; a[l] = a[r]; a[r] = temp;
}
}
a[left] = a[r];
a[r] = p;
return r;
}
Silicon Institute of Technology Quicksort Implementation (C)

static void Quicksort(int array[], int left, int right) {

if (left < right) {
int p = Partition(array, left, right);
Quicksort(array, left, p - 1);
Quicksort(array, p + 1, right);
}
}
Silicon Institute of Technology Complexity of Partition
• PartitionTime(n) is given by the number of iterations in the for loop.
• (n) : n = r – p + 1.

Partition(A, p, r)
x, i := A[r], p – 1;
for j := p to r – 1 do
if A[j]  x then
i := i + 1;
A[i]  A[j]
A[i + 1]  A[r];
return i + 1
Silicon Institute of Technology Analysis of quicksort—best case
• Suppose each partition operation divides the array almost
exactly in half
• Then the depth of the recursion in log2n
• Because that’s how many times we can halve n
• We note that
• Each partition is linear over its subarray
• All the partitions at one level cover the complete array
Silicon Institute of Technology Best Case Analysis
• We cut the array size in half each time

T(n) = T(n/2) + O(n)

• The depth of the recursion in log2n
• At each level of the recursion, all the partitions at that level do work that is
linear in n
• O(log2n) * O(n) = O(n log2n)
• Hence in the best case, quicksort has time complexity O(n log2n)
• What about the worst case?
Silicon Institute of Technology Worst case
• Consider an all ready sorted array
10 15 17 21 23 28 35 42 50 55 62 72 81 91
81 9 95

• In the worst case, partitioning always divides the size n array into these
three parts:
• A length one part, containing the pivot itself
• A length zero part, and
• A length n-1 part, containing everything else
• We don’t recur on the zero-length part
• Recurring on the length n-1 part requires (in the worst case) recurring
to depth n-1
Silicon Institute of Technology
Worst case partitioning
Silicon Institute of Technology Worst case for quicksort
• In the worst case, recursion may be n levels deep (for an array of size n)
• But the partitioning work done at each level is still n

T(n) = T(n-1) + O(n)

• O(n) * O(n) = O(n2)
• So worst case for Quicksort is O(n2)
• When does this happen?
• There are many arrangements that could make this happen
• Here are two common cases:
• When the array is already sorted
• When the array is inversely sorted (sorted in the opposite order)
Silicon Institute of Technology Typical case for quicksort
• If the array is sorted to begin with, Quicksort is terrible: O(n2)
• It is possible to construct other bad cases
• However, Quicksort is usually O(n log2n)
• The constants are so good that Quicksort is generally the faster
algorithm.
• Most real-world sorting is done by Quicksort
Silicon Institute of Technology Picking a better pivot
• Before, we picked the first element of the subarray to use as a pivot
• If the array is already sorted, this results in O(n2) behavior
• It’s no better if we pick the last element
• We could do an optimal quicksort (guaranteed O(n log n)) if we
always picked a pivot value that exactly cuts the array in half
• Such a value is called a median: half of the values in the array are larger, half
are smaller
• The easiest way to find the median is to sort the array and pick the value in
the middle (!)
Silicon Institute of Technology Median of three
• Obviously, it doesn’t make sense to sort the array in order to find the
median to use as a pivot.
• Instead, compare just three elements of our (sub)array—the first, the
last, and the middle
• Take the median (middle value) of these three as the pivot
• It’s possible (but not easy) to construct cases which will make this technique
O(n2)
Silicon Institute of Technology Randomize Quick Sort
• Selection of Pivot element is done randomly from the array.
Pivot = random(p, r)
RandPartition(A, p, r) Partition(A, p, r)
i = Random(p,r) x := A[r]; I:= p – 1;
exchange A[r] with A[i] for j := p to r – 1 do
return partition(A,p,r) if A[j]  x then
i := i + 1;
RandQuicksort(A, p, r) A[i]  A[j]
if p < r then A[i + 1]  A[r];
q := RandPartition(A, p, r); return i + 1
RandQuicksort(A, p, q – 1);
RandQuicksort(A, q + 1, r)
Silicon Institute of Technology Quicksort for Small Arrays
• For very small arrays (N<= 20), quicksort does not perform as well as
insertion sort
• A good cutoff range is N=10
• Switching to insertion sort for small arrays can save about 15% in the
running time
Silicon Institute of Technology Mergesort vs Quicksort
• Both run in O(n lgn)
• Mergesort – always.
• Quicksort – on average
• Compared with Quicksort, Mergesort has less number of comparisons
but larger number of moving elements
• In Java, an element comparison is expensive but moving elements is
cheap. Therefore, Mergesort is used in the standard Java library for
generic sorting
Silicon Institute of Technology Mergesort vs Quicksort
In C++, copying objects can be expensive while comparing objects often
is relatively cheap. Therefore, quicksort is the sorting routine
commonly used in C++ libraries

Note these last two rules are not really language specific, but rather
how the language is typically used.
Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Heap and Heap Sort

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology Heap data structure
A heap is a balanced binary tree data structure either complete
or the tree is completely filled on all levels except possibly the
lowest, which is filled from the left up to a point.
• Binary tree
• Balanced
• Complete or Left-justified
• (Max) Heap property: no node has a value greater than the
value in its parent
• (Min) Heap property: no node has a value smaller than the
value in its parent
Silicon Institute of Technology Balanced binary trees
• Recall:
• The depth of a node is its distance from the root
• The depth of a tree is the depth of the deepest node
• A binary tree of depth n is balanced if all the nodes at depths 0 through
n-2 have two children

n-2
n-1
n
Balanced Balanced Not balanced
Silicon Institute of Technology Left-justified binary trees
• A balanced binary tree of depth n is left-justified if:
• it has 2n nodes at depth n (the tree is “full”), or
• it has 2k nodes at depth k, for all k < n, and all the leaves at depth n
are as far left as possible

Left-justified Not left-justified

Silicon Institute of Technology The heap(Order) Property
• A node has the heap property if the value in the node is as large as or
larger than the values in its children ( Max-Heap)
• In case of Min-Heap the value of the parent node is less than or equal
to it’s child nodes
12 12 12

8 3 8 12 8 14
Red node has Red node has Red node does not
heap property heap property have heap property
• All leaf nodes automatically have the heap property
• A binary tree is a heap if all nodes in it have the heap property
Silicon Institute of Technology siftUp
• Given a node that does not have the heap property, you can give it the heap
property by exchanging its value with the value of the larger child

12 14

8 14 8 12
Blue node does not Blue node has
have heap property heap property

This is sometimes called sifting up

Silicon Institute of Technology Heap is an Array
For simplicity heap is represented as an array
1 25
2 3
22 17

4 5 6 7
19 22 14 15
8 9 10 11 12 13
18 14 21 3 9 11

25 22 17 19 22 14 15 18 14 21 3 9 11
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Silicon Institute of Technology Parent, Left and Right in array

25 22 17 19 22 14 15 18 14 21 3 9 11 PARENT(i)
{
return(i/2)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 }

LEFT(i)
{
Parent of i => 𝑖/2 MAX-Heap return(2i)
A(PARENT(i)) >= A(i) }
Left of i => 2 i
MIN-Heap RIGHT(i)
Right of i => 2 i +1 A(PARENT(i)) <= A(i) {
return(2i+1)
}
Silicon Institute of Technology Building up to heap sort

• How to maintain a heap

• How to build a heap

• How to use a heap to sort data

Silicon Institute of Technology Maintaining a Heap: MAX-HEAPIFY

Alg: MAX-HEAPIFY(A, i)
• In order to maintain the Max Heap
1. l ← LEFT(i)
property we call procedure 2. r ← RIGHT(i)
MAX-HEAPIFY( A, i) 3. if l ≤ Heap-Size(A) and A[l] > A[i]
4. then largest ←l
• This function ensures the sub-tree 5. else largest ←i
6. if r ≤ Heap-Size(A) and A[r] > A[largest]
rooted at index i obeys the MAX-
7. then largest ←r
HEAP property 8. if largest  i
9. then exchange A[i] ↔ A[largest]
10. MAX-HEAPIFY(A, largest)
Silicon Institute of Technology
MAX-HEAPIFY( A, 2)
16 16

i 4 10 14 10

i
14 7 9 3 4 7 9 3

2 8 1 2 8 1
16

14 10

8 7 9 3

2 i 4 1
Silicon Institute of Technology Building a heap from an array - I
• We have an existing Array … A[1…n] where n is [Link], we want to
convert it into MAX-HEAP
• By default leaf nodes are MAX-HEAP
• The elements A[(n/2)+1] to A[n] are the leaf nodes of the tree all other
nodes from A[1] to A[n/2] are non-leaf nodes.
• We can call the MAX-HEAPIFY function bottom up manner for all non leaf
nodes 4
Alg: BUILD-MAX-HEAP(A)
1 3
1. Heap-Size(A) = length[A]
2. for i ←  length[A] /2 downto 1 2 16 9 10

3. do MAX-HEAPIFY(A, i) 14 8 7
Silicon Institute of Technology Building a heap from an array - II
Need to built a heap from a given array

4 1 3 2 16 9 10 14 8 7
0 1 2 3 4 5 6 7 8 9 10

4 4

1 3 1 3

2 i 16 9 10 i 2 16 9 10

14 8 7 14 8 7
Silicon Institute of Technology Building a heap from an array - III
4 4

1 i 3 i 1 10

14 16 9 10 14 16 9 3

2 8 7 2 8 7

4 16

16 10 14 10

14 7 9 3 8 7 9 3

2 8 1 2 4 1
Silicon Institute of Technology Sorting an Array-I
16
• If we observe the max value of the array after heapify sits at the
root.
14 10
• Idea is to remove this element from the root and heapify the tree
again from root.
• Place the removed element at the last element in the array and
8 7 9 3 decrease the heap length

2 4 1 Alg: HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. Heap-Size(A) = Heap-Size(A) -1
5. MAX-HEAPIFY(A, 1)
Silicon Institute of Technology Sorting an Array-II
1 14
16

14 10 8 10
14 10

8 7 9 3 4 7 9 3
8 7 9 3

2 4 16 2 1 16
2 4 1

14 1 10

8 10 8 10 8 9

4 7 9 3 4 7 9 3 4 7 1 3

2 1 16 2 14 16 2 14 16
Silicon Institute of Technology Sorting an Array-III
10 2 9

8 9 8 9 8 3

4 7 1 3 4 7 1 3 4 7 1 2

2 14 16 10 14 16 10 14 16

9 2 8

8 3 8 3 7 3

4 7 1 2 4 7 1 9 4 2 1 9

10 14 16 10 14 16 10 14 16
Silicon Institute of Technology Sorting an Array-IV
8 1 7

7 3 7 3 4 3

4 2 1 9 4 2 8 9 1 2 8 9

10 14 16 10 14 16 10 14 16

2 4
7
4 3 2 3
4 3

1 7 8 9 1 7 8 9
1 2 8 9
10 14 16 10 14 16
10 14 16
Silicon Institute of Technology Sorting an Array-V
4 1 3

2 3 2 3 2 1

1 7 8 9 4 7 8 9 4 7 8 9

10 14 16 10 14 16 10 14 16

1 2
3

2 3 1 3
2 1

4 7 8 9 4 7 8 9
4 7 8 9

10 14 16 10 14 16
10 14 16
Silicon Institute of Technology Sorting an Array-VI
2 1

1 3 2 3

4 7 8 9 4 7 8 9

10 14 16 10 14 16

1 2 3 4 7 8 9 10 14 16

Sorted Array
Silicon Institute of Technology MAX-HEAPIFY Running Time
• Intuitively:
– It traces a path from the node to a leaf. Alg: MAX-HEAPIFY(A, i)
1. l ← LEFT(i)
– At each level it makes exactly 2 comparisons.
2. r ← RIGHT(i)
– Total number of comparisons is 2h. 3. if l ≤ Heap-Size(A) and A[l] > A[i]
– Running time is O(h) or O(lg n). 4. then largest ←l
5. else largest ←i
• Running time of MAX-HEAPIFY is O(lgn) 6. if r ≤ Heap-Size(A) and A[r] > A[largest]
7. then largest ←r
• Can be written in terms of the height of the 8. if largest  i
heap, as being O(h) 9. then exchange A[i] ↔ A[largest]
10. MAX-HEAPIFY(A, largest)
• Since the height of the heap islgn

–
Silicon Institute of Technology Running Time of BUILD MAX HEAP
Alg: BUILD-MAX-HEAP(A)
1. Heap-Size(A) = length[A]
2. for i ←  length[A] /2 downto 1
O(n)
3. do MAX-HEAPIFY(A, i) O(lgn)

 Running time: O(nlgn) 16

• This is not an asymptotically tight upper bound 14 10

4 7 9 3

2 8 1
Silicon Institute of Technology Running Time of BUILD MAX HEAP
• build-max-heap algorithm executes bottom-to-top.
• Let the size of heap = n
• Maxm no. of elements with height h =

• When max-heapify is called to a node having height h, the

cost is O(h)

• For all nodes of height h, the total cost = * O(h)

Silicon Institute of Technology Running Time of BUILD MAX HEAP
For all nodes with varying height, the time complexity

∗ 𝑂(ℎ)

∞
ℎ 1/2
𝐵𝑢𝑡 ෍ ℎ = 2
=2
2 1 − 1/2
ℎ=0

= O 𝑛
Silicon Institute of Technology Total Running time of Sorting Algorithm
Alg: HEAPSORT(A)
1. BUILD-MAX-HEAP(A) O(n)

2. for i ← length[A] downto 2

3. do exchange A[1] ↔ A[i] (1)
n-1
4. Heap-Size(A) = Heap-Size(A) -1 (1) times

5. MAX-HEAPIFY(A, 1) O(lgn)

• Running time: O(nlgn)

25
Silicon Institute of Technology

Priority Queues
Silicon Institute of Technology
Priority Queues
Silicon Institute of Technology Operations on Priority Queues
Max-Priority queues support the following operations:
– INSERT(S, x): inserts element x into set S
– MAXIMUM(S): returns element of S with largest key
– EXTRACT-MAX(S): removes and returns element of S with
largest key
– INCREASE-KEY(S, x, k): increases value of element x’s key to k
(Assume k ≥ x’s current key value)
– REMOVE(S,i) : Remove an element pointed by i.
Silicon Institute of Technology HEAP-MAXIMUM
Goal:
– Return the largest element of the heap

Alg: HEAP-MAXIMUM(A)
1. return A[1] Running time: O(1)

Heap-Maximum(A) returns 7
Silicon Institute of Technology HEAP-EXTRACT-MAX
Goal:
– Extract the largest element of the heap (i.e., return the max value and also remove
that element from the heap
Idea:
– Exchange the root element with the last
– Decrease the size of the heap by 1 element
– Call MAX-HEAPIFY on the new root, on a heap of size n-1

Heap A: Root is the largest element

Silicon Institute of Technology Example: HEAP-EXTRACT-MAX
16 1

14 10 max = 16 14 10
8 7 9 3 8 7 9 3
2 4 1 2 4
Heap size decreased with 1

14

Call MAX-HEAPIFY(A, 1)
8 10
4 7 9 3
2 1
Silicon Institute of Technology HEAP-EXTRACT-MAX
Alg: HEAP-EXTRACT-MAX(A)
1. if heap-size[A] < 1
2. then error “heap underflow”

3. max ← A[1]

4. A[1] ← A[heap-size[A]]

5. heap-size[A] ← heap-size[A] - 1

6. MAX-HEAPIFY(A, 1) remakes heap

7. return max
Running time: O(lgn)
Silicon Institute of Technology HEAP-INCREASE-KEY
• Goal:
– Increases the key of an element i in the heap
• Idea:
– Increment the key of A[i] to its new value
– If the max-heap property does not hold anymore: traverse a path
toward the root to find the proper place for the newly increased key

16

14 10
8 i 7 9 3
Key [i] ← 15 2 4 1
Silicon Institute of Technology Example: HEAP-INCREASE-KEY
16 16

14 10 14 10
8 i 7 9 3 8 i 7 9 3
2 4 1 2 15 1
Key [i ] ← 15

16 16
i
14 10 15 10
i
15 7 9 3 14 7 9 3
2 8 1 2 8 1
Silicon Institute of Technology HEAP-INCREASE-KEY

Alg: HEAP-INCREASE-KEY(A, i, key)

1. if key < A[i]
2. then error “new key is smaller than current key”
3. A[i] ← key
4. while i > 1 and A[PARENT(i)] < A[i] 16

5. do exchange A[i] ↔ A[PARENT(i)] 14 10

6. i ← PARENT(i) 8 7 9 3
i
2 4 1

Running time: O(lgn) Key [i] ← 15

Silicon Institute of Technology MAX-HEAP-INSERT
• Goal:
16
– Inserts a new element into a max-
heap
14 10
• Idea: 8 7 9 3

– Expand the max-heap with a new 2 4 1 -∞

16
element whose key is -
– Calls HEAP-INCREASE-KEY to 14 10

set the key of the new node to its 8 7 9 3

correct value and maintain the 2 4 1 15

max-heap property
Silicon Institute of Technology Example: MAX-HEAP-INSERT
Insert value 15: Increase the key to 15
- Start by inserting - Call HEAP-INCREASE-KEY on A[11] = 15
16
16

14 10
14 10
8 7 9 3
8 7 9 3
2 4 1 15
2 4 1 -

16 16

14 10 15 10

8 15 9 3 8 14 9 3
2 4 1 7 2 4 1 7 The restored heap containing
the newly added element
Silicon Institute of Technology MAX-HEAP-INSERT

Alg: MAX-HEAP-INSERT(A, key) 16

14 10
1. heap-size[A] ← heap-size[A] + 1
8 7 9 3

2. A[heap-size[A]] ← - 2 4 1 -

3. HEAP-INCREASE-KEY(A, heap-size[A] , key)

Running time: O(lgn)

Silicon Institute of Technology MAX-HEAP-REMOVE

Alg: MAX-HEAP-REMOVE(A, i)
1. X ← HEAP-MAXIMUM(A) + 1 14
2. HEAP-INCREASE-KEY(A, i , X)
3. HEAP-EXTRACT-MAX(A) 8 10
4 i 7 9 3
2 1

Running time: O(lgn)

Silicon Institute of Technology Summary
• We can perform the following operations on heaps:

– MAX-HEAPIFY O(lgn)
– BUILD-MAX-HEAP O(n)
– HEAP-SORT O(nlgn)
– MAX-HEAP-INSERT O(lgn)
– HEAP-EXTRACT-MAX O(lgn)
Average
– HEAP-INCREASE-KEY O(lgn) O(lgn)
– HEAP-MAXIMUM O(1)
Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Dynamic Programming

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology
A method for solving complex problems by breaking them into smaller,
easier, sub problems
Term Dynamic Programming coined by mathematician Richard Bellman in
early 1950s
employed by Rand Corporation
Rand had many, large military contracts
Secretary of Defense, Charles Wilson “against research, especially mathematical
research”. how could any one oppose "dynamic"?

"Thus, I thought dynamic programming was a good name. It

was something not even a Congressman could object to. So I
used it as an umbrella for my activities"
- Richard E. Bellman
Silicon Institute of Technology What is Dynamic Programming?
• Dynamic programming solves optimization problems by combining
solutions to subproblems

• “Programming” refers to a tabular method with a series of choices,

not “coding”

Break big problem up into smaller problems ...

Sound familiar?

Recursion?
Problems with Recursion…
Silicon Institute of Technology Fibonacci Series: An Example
Using Recursion
Silicon Institute of Technology
Problem With Recursion
Silicon Institute of Technology Slow Fibonacci

Why so slow?
• Algorithm keeps calculating the same value over
and over
• When calculating the 40th Fibonacci number the
algorithm calculates the 4th Fibonacci number
24,157,817 times!!!
Silicon Institute of Technology Dynamic Programming: Approach

• Given Problem is divided into number of interrelated over lapping

Sub-problems

• To avoid recomputation of multiple overlapping sub problem

repeatedly a table is created. When ever the sub-problem is solved,
then the solution is stored and reuse in future

• The solution of the sub-problem are combined in a bottom –up

approach to obtain the final solution
Silicon Institute of Technology Multistage Optimization

• Dynamic programming is useful in case of multi stage optimization

problems

• Each Optimisation Problem has an objective function and a set of

constraints/ restrictions.

• Optimization problem deals with the maximization or minimization

of the objective function.

• In multistage optimization problem, decisions are taken at multiple

stages to obtain a global solution
Silicon Institute of Technology Components of Dynamic Programming
Stages : Given problem can be divided into a number of sub problems called
stages.
• division of problem into number of sub-problems should be done in polynomial
time.
• Its also referred as polynomial breakup.
Decision: In each stage there can be multiple decisions, out of which the
best decision should be taken.
• A decision taken at every stage should be optimal.

State: A state indicates the sub problem for which decision needs to be
taken.
• The variables that are used to take decision at every stage are called state variables
• Number of state variables should be as small as possible.
Silicon Institute of Technology Components of Dynamic Programming
Policy: Policy is a rule that determines the decision at each stage
• A policy is called optimal, if it is globally optimal
• This is called the Bellmann’s Principle of Optimality
Principle of Optimality
• The core principle of Dynamic Programming is ‘Principle of Optimality’
It states that the optimal sequence of decisions in a multistage decision
problem is feasible if and only if its sub-sequences are optimal
In other words
An optimal policy (a sequence of decision) has the property that whatever
the initial state and decision are, the remaining decisions must constitute
an optimal policy with regards to the state resulting from the first decision
Silicon Institute of Technology Procedure for Dynamic Programming
Step 1: Identify the objective function of the given problem
Step 2: Identify the decision variables that characterize the objective
function
Step 3: Generalisation of the problem by creating a set related similar
sub problems
Step 4: Identify the stages and state variables of the problem
Step 5: Write a recursive relation of the problem in terms of its sub
problem
Step 6: Solve the recursive relation
Step 7 : Recover and the state the final solution in terms of the result of
the sub problem
Silicon Institute of Technology Characteristic of Dynamic Programming
Overlapping Sub-problem:
• One of the main characteristics of dynamic programming is to spilt the problem
into sub-problems.
• But unlike divide and conquer approach here many subproblems overlap and
can not be treated distinctly
Two ways of handling overlapping problems
1. Memorization Technique: This method looks into a table to check
whether the table has any entry or not.
• Initially all entries are filled with NIL or undefined
• If no value is present then it is computed
• Here the computation flows in a top-down method.
Silicon Institute of Technology Characteristic of Dynamic Programming
2. Tabulation Method: Here is the problem is solved from scratch
• The smallest subproblem is solved and it is stored in the table.
• Its value is used in the table. Its value is later used later for solving larger problem
• In other words computation follows a Bottom-up method.

Optimal Substructures:
• An optimal solution to a problem contains within it an
optimal solution to sub-problems
• Optimal solution to the entire problem is build in a
bottom-up manner from optimal solutions to sub-
Each substructure is optimal.
problems
(Principle of optimality)
Silicon Institute of Technology Algorithm Fibonacci(n)
Divide and Conquer Approach

Algo Fibonacci(n)
Begin
if((n==0) OR (n==1)) then
return n
else return [ Fibonacci(n-1) + Fibonacci(n-2)]
end if
End
Silicon Institute of Technology Algorithm Fibonacci(n)
Algo mem_Fibonacci(n) // top down approach

Begin
if((n==0) OR (n==1)) then return n
else if A[n] is undefined then
A[n] = mem_Fibonacci(A[n-1]) + mem_Fibonacci(A[n-2])
return A[n]
else return A[n]
end if
End
Silicon Institute of Technology Algorithm Fibonacci(n)
Algo dp_Fibonacci(n) // bottom up approach
Begin
first = 0
second = 1
if(n==0) OR (n==1) then
return n
end if
repeat n-1 times
current = first + second
first = second
second = current
End repeat
return(current)
End
Silicon Institute of Technology Matrix-Chain Multiplication
Problem: given a sequence A1, A2, …, An , compute the product:
A1  A2  An

• Matrix Multiplications and not Commutative but Associative.

• In what order should we multiply the matrices?
• Parenthesize the product to get the order in which matrices are multiplied

E.g.: A1  A2  A3 = ((A1  A2)  A3) = (A1  (A2  A3))

• The order in which we multiply the matrices has a significant impact on the cost of
evaluating the product
Silicon Institute of Technology MATRIX-MULTIPLY(A, B)
[Link] columns[A]  rows[B]
2. then error “incompatible dimensions”
3. else for i  1 to rows[A]
4. do for j  1 to columns[B] rows[A]  cols[A]  cols[B]
multiplications
5. do C[i, j] = 0
6. for k  1 to columns[A]
7. do C[i, j]  C[i, j] + A[i, k] B[k, j]
k
j cols[B]
j cols[B]

i = i
* k
A B C
rows[A]
rows[A]
Silicon Institute of Technology Matrix Compatibility for Multiplication

pxq X qxr = pxr

No of multiplications = p x q x r

A1  A2  Ai  Ai+1  An No of Multiplication Ai  Ai+1

Pi-1Pi Pi Pi+1
{P0xP1, P1xP2, … Pi-1xPi, PixPi+1 …Pn-1xPn}
{P0 P1 P2 . . . Pi-1 Pi Pi+1 . . . Pn-1 Pn} Pi-1 . Pi . Pi+1
What is the size of matrix for the chain : Ai  Ai+1  Aj
Silicon Institute of Technology Matrix Chain Multiplication
A:2x3 AXBXC
B:3x4 Two Possible Ordering
C:4x5 ((A B) C)
(A (B C))

[(A B) C] = (2x3x4) + (2x4x5) = 24 + 40 = 64

[A (B C)] = (3x4x5) + (2x3x5) = 60 + 30 = 90

So the optimal order is [(A B) C]

Silicon Institute of Technology Matrix Chain Multiplication
AXBXCXD Five Possible Ordering
A:2x3 A(B(CD))
B:3x4 (AB)(CD)
A((BC)D)
C:4x3
((AB)C)D
D: 3 x 2 (A(BC))D
<

[A(B(CD))] = (4x3x2) + (3x4x2) + (2x3x2) = 24 + 24 + 12 = 60

[(AB)(CD)] = (2x3x4) + (4x3x2) + (2x4x2) = 24 + 24 + 16 = 64
Optimal Ordering
[A((BC)D)] = (3x4x3) + (3x3x2) + (2x3x2) = 36 + 18 + 12 = 66
[((AB)C)D] = (2x3x4) + (2x4x3) + (2x3x2) = 24 + 24 + 12 = 60
[(A(BC))D] = (3x4x3) + (2x3x3) + (2x3x2) = 36 + 18 + 12 = 66
Silicon Institute of Technology The Structure of an Optimal Parenthesization

Notation:
Ai…j = Ai Ai+1  Aj, i  j

For i < j:
Suppose that an optimal parenthesization of Ai…j splits the product
between Ak and Ak+1, where ik<j

Ai…j = Ai Ai+1  Aj

= Ai Ai+1  Ak Ak+1  Aj
= Ai…k Ak+1…j
Silicon Institute of Technology MCP Dynamic Programming Steps
Step 1: structure of an optimal parenthesization
• Let Ai..j (i  j) denote the matrix resulting from AiAi+1…Aj
• Any parenthesization of AiAi+1…Aj must split the product between Ak and Ak+1
for some k, (i k <j).

• The cost = # of computing Ai..k + # of computing Ak+1..j + # Ai..k  Ak+1..j.

• If k is the position for an optimal parenthesization, the parenthesization of

“prefix” subchain AiAi+1…Ak within this optimal parenthesization of
AiAi+1…Aj must be an optimal parenthesization
AiAi+1…Ak  Ak+1…Aj
Silicon Institute of Technology Optimal Substructure
Ai…j = Ai…k Ak+1…j

• The parenthesization of the “prefix” Ai…k must be an optimal parenthesization

• If there were a less costly way to parenthesize Ai…k, we could substitute that one
in the parenthesization of Ai…j and produce a parenthesization with a lower cost
than the optimum.
• An optimal solution to an instance of the matrix-chain multiplication
contains within it optimal solutions to subproblems
Silicon Institute of Technology A Recursive Solution
Subproblem:

determine the minimum cost of parenthesizing Ai…j = Ai Ai+1  Aj

for 1  i  j  n

Let m[i, j] = the minimum number of multiplications needed to

compute Ai…j
• Full problem (A1..n): m[1, n]

• i = j: Ai…i = Ai  m[i, i] = 0, for i = 1, 2, …, n

Silicon Institute of Technology A Recursive Solution
• Consider the subproblem of parenthesizing

• Ai…j = Ai Ai+1  Aj for 1  i  j  n

pi-1pkpj

= Ai…k Ak+1…j for i  k < j

m[i, k] m[k+1,j]

• Assume that the optimal parenthesization splits the product Ai Ai+1 
Aj at k (i  k < j)

m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj

min # of multiplications min # of multiplications # of multiplications

to compute Ai…k to compute Ak+1…j to compute Ai…kAk…j
Silicon Institute of Technology A Recursive Solution (cont.)
m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj
• We do not know the value of k
• There are j – i possible values for k: k = i, i+1, …, j-1
• Minimizing the cost of parenthesizing the product Ai Ai+1
 Aj becomes:
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j
Silicon Institute of Technology Reconstructing the Optimal Solution

Additional information to maintain:

s[i, j] = a value of k at which we can split the product Ai Ai+1  Aj in

order to obtain an optimal parenthesization

Silicon Institute of Technology Computing the Optimal Costs
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

• How many subproblems do we have?

• Parenthesize Ai…j 1 2 3 n

for 1  i  j  n 1

• One problem for each 2

choice of i and j 3

n
Silicon Institute of Technology Computing the Optimal Costs (cont.)
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

• How do we fill in the tables m[1..n, 1..n] and s[1..n, 1..n] ?

• Determine which entries of the table are used in computing m[i, j]

Ai…j = Ai…k Ak+1…j

• Fill in m such that it corresponds to solving problems of increasing length
Silicon Institute of Technology Computing the Optimal Costs (cont.)
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j m[1, n] gives the optimal
solution to the problem
• Length = 1: i = j, i = 1, 2, …, n
• Length = 2: j = i + 1, i = 1, 2, …, n-1 1 2 3 n
1

2
Compute rows from top to bottom 3
and from left to right
In a similar matrix s we keep the
optimal values of k
n
Silicon Institute of Technology Example: min {m[i, k] + m[k+1, j] + pi-1pkpj}

m[2, 2] + m[3, 5] + p1p2p5 k=2

m[2, 5] = min m[2, 3] + m[4, 5] + p1p3p5 k=3

m[2, 4] + m[5, 5] + p1p4p5 k=4

1 2 3 4 5 6

1
2
• Values m[i, j] depend only on
3
values that have been
previously computed 4
5
6
i
Silicon Institute of Technology Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
A1 A2 A 3 A4 1 2 3 4

4x5 5x3 3x2 2x7 1 0

P0P1 P1P2 P2P3 P3P4 2 0 M
3 0
Length = 1: i = j, i = 1, 2, …, n 4 0
When i==j then M[i, j] =0

 M[1,1] =0 1 2 3 4
 M[2,2] =0 1 0
 M[3,3] =0
2 0
 M[4,4] =0 S
3 0
4 0
Silicon Institute of Technology Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
A1 A2 A 3 A4 1 2 3 4

4x5 5x3 3x2 2x7 1 0 60

P0P1 P1P2 P2P3 P3P4 2 0 30 M
3 0 42
For the Second Super Diagonal 4 0
Length = 2: j = i+1, i = 1, 2, …, n

 M[1,2] = M[1,1] + M[2,2] + P0P1P2 = 0+0+60=60 ( k=1) 1 2 3 4

 M[2,3] = M[2,2] + M[3,3] + P1P2P3 = 0+0+30=30 ( k=2) 1 0 1
 M[3,4] = M[3,3] + M[4,4] + P2P3P4 = 0+0+42=42 ( k=3)
2 0 2
S
3 0 3
4 0
Silicon Institute of Technology Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
A1 A2 A 3 A4 1 2 3 4

4x5 5x3 3x2 2x7 1 0 60 70

P0P1 P1P2 P2P3 P3P4 2 0 30 100

M
3 0 42
For the Third Super Diagonal 4 0
Length = 3: j = i+2, i = 1, 2, …, n

 M[1,3] = M[1,1] + M[2,3] + P0P1P3 = 0+30+40=70 ( k=1) 1 2 3 4

Or M[1,3] = M[1,2] + M[3,3] + P0P2P3 = 60+0+24=84 ( k=2) 1 0 1 1
2 0 2 3
S
 M[2,4] = M[2,2] + M[3,4] + P1P2P4 = 0+42+105=147 ( k=2) 3 0 3
Or M[2,4] = M[2,3] + M[4,4] + P1P3P4 = 30+0+70=100 ( k=3) 4 0
Silicon Institute of Technology Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
A1 A2 A3 A4 1 2 3 4
4x5 5x3 3x2 2x7 1 0 60 74 126
P0P1 P1P2 P2P3 P3P4 2 0 30 100
M
For the Forth Super Diagonal 3 0 42
Length = 3: j = i+3, i = 1, 2, …, n 4 0

 M[1,4] = M[1,1] + M[2,4] + P 0P1P4

= 0+100+140=240 ( k=1) 1 2 3 4
Or M[1,4] = M[1,2] + M[3,4] + P0P2P4 1 0 1 1 3
= 60+42+84=186 ( k=2) 2 0 2 3
Or M[1,4] = M[1,3] + M[4,4] + P0P3P4 S
3 0 3
= 74+0+56=126 ( k=3)
4 0
Silicon Institute of Technology Construct the Optimal Solution
Store the optimal choice made at each subproblem
s[i, j] = a value of k such that an optimal parenthesization of Ai..j splits
the product between Ak and Ak+1
s[1, n] is associated with the entire product A1..n
The final matrix multiplication will be split at k = s[1, n]
A1..n = A1..s[1, n]  As[1, n]+1..n
For each subproduct recursively find the corresponding value of k that results in
an optimal parenthesization
Silicon Institute of Technology Construct the Optimal Solution
• s[i, j] = value of k such that the optimal
parenthesization of Ai Ai+1  Aj splits the product
between Ak and Ak+1

1 2 3 4
1 0 1 1 3
2 0 2 3 • s[1, n] = 3  A1..4 = A1..3 A4..4
3 0 3 • s[1, 3] = 1  A1..3 = A1..1 A2..3
4 0
Final Parenthesis: (A1(A2 A3) A4)
Silicon Institute of Technology MATRIX-CHAIN-ORDER(p)
1. n  length[p] – 1
2. for i  1 to n Running time: (n 3)

3. do m[i, i]  0 Chains of length one have cost 0

4. for l  2 to n l is the length of the chain
5. do for i  1 to n – l + 1
6. do j  i + l – 1
7. m[i, j]  
8. for k  i to j – 1 For a particular
9. do q  m[i, k] + m[k+1, j] + pi-1pkpj m[i, j], look at all
possible choices
10. if q < m[i, j]
for k and choose
11. then m[i, j]  q the one that
12. s[i, j]  k gives the
minimum cost
13. return m, s
Silicon Institute of Technology Construct the Optimal Solution (cont.)

PRINT-OPT-PARENS(s, i, j)

if i = j
1 2 3 4
then print “A i”
1 0 1 1 3
else print “(”
2 0 2 3
PRINT-OPT-PARENS(s, i, s[i, j]) 3 0 3
PRINT-OPT-PARENS(s, s[i, j] + 1, j) 4 0
print “)”

Initial Call is PRINT-OPT-PARENS(s, 1, 4)

Silicon Institute of Technology Memorization: Top Down Approach
Memorization-Matrix-Chain(p)
1. n <- [Link] -1 Lookup-Matrix-Chain(m, p, i, j)
2. Let m[1..n, 1..n] be a new table
1. if m[i, j] < ∞ then return m[i, j]
3. for i = 1 to n
2. if i == j then m[i, j] = 0
4. for j = 1 to n
5. M[i, j] = ∞ 3. else for k = i to j-1
6. Return Lookup-Matrix-Chain(m,p,1,n) 4. q  Lookup-Matrix-Chain(m,p,i,k) +
Lookup-Matrix-Chain(m,p,k+1,j) + Pi-1PkPj
5. if q < m[i, j] then m[i, j] = q
6. s[i, j] =k
7. Return m[i, j]
Silicon Institute of Technology Recursive Approach
Recursive-Matrix-Chain(m, p, i, j)
1. if i == j then return 0
2. m[i, j] = ∞
3. for k = i to j-1
4. q  Recursive-Matrix-Chain(m,p, i, k ) +
Recursive-Matrix-Chain(m,p,k+1,j) + Pi-1PkPj
5. if q < m[i, j] then m[i, j] = q
6. s[i, j] = k
7. Return m[i, j]
Silicon Institute of Technology

Thank You
Silicon Institute of Technology

Longest Common Subsequence

Dynamic Programming

Bhawani Shankar Pattnaik

Faculty Chamber- 04-58(A)
Mob: 9437166101
Email: [Link]@[Link]
Silicon Institute of Technology Longest Common Subsequence
DNA Strand is expressed as a string over a finite set {A, C, G, T}
S1 = ACCGGTCGAGTCGCGCGGAAGCCGGCCGAA ( Organ 1)
S2 = GTCCGTTCGGAATGCCGTTGCTCTGTAAA ( Organ 1)

Need to check how similar the DNA stands are:

1. We can say DNA strands are similar if one is substring of other
2. No of changes need to change one into other
3. Finding a third strand S3, where the bases in S3 appears in each of S1
and S2
These bases must appear in the same order, but not necessarily
consecutively. The longer the strand S3, more is the similarity
Silicon Institute of Technology Longest Common Subsequence
Formal Definition : Subsequence
Given a Sequence X = <x1,x2,x3…….xn>
another sequence Z = <z1,z2,z3…….zk> is a subsequence of X if there exist
a strictly increasing sequence <i1,i2,i3…….ik> of indices of X such that for
all j = 1, 2,…k we have 𝑥𝑖𝑗 = 𝑧𝑗

Example
X = <A, B, C, B, D, A, B>
Z = <B, C, D, B> is a subsequence of X with index sequence (2, 3, 5, 7)
Silicon Institute of Technology Longest Common Subsequence
Formal Definition : Common Subsequence
Given two Sequences X and Y, we say that a sequence Z is a common
subsequence of X and Y if Z is a subsequence of both X and Y.
For Example: Given two sequences
X = <A, B, C, B, D, A, B> Y =<B, D, C, A, B, A>
Common Subsequence
<A, B, C, B, D, A, B> <A, B, C, B, D, A, B>
Z1= <B, C, B, A>
Z2= <B, D, A, B>

<B, D, C, A, B, A> <B, D, C, A, B, A>

Longest Common Subsequence(LCS) : Maximum of all possible subsequence possible

Silicon Institute of Technology Longest Common Subsequence
LCS Problem: We are given two sequences X = <x1,x2,x3…….xm> and Y = <y1,y2,y3…….yn>
and wish to find the maximum length common subsequence of X and Y.

Brute-force Approach: We will find all subsequence of X and check each subsequence to see whether it
is also a subsequence of Y. (Keeping track of the longest sequence)

Note: As there are 2m possible sub sequences of X, It is going to take exponential time.
Silicon Institute of Technology Theorem
Optima Structure of LCS
Let X = <x1,x2,x3…….xm> and Y = <y1,y2,y3…….yn> be sequences. And let
Z = < z1,z2,33…….zk > be any LCS of X and Y

1. If xm = yn then zk = xm = yn and Zk-1 is the LCS of Xm-1 and Yn-1

2. If xm ≠ yn then zk ≠ xm implies Z is the LCS of Xm-1 and Y
3. If xm ≠ yn then zk ≠ yn implies Z is the LCS of X and Yn-1
Proof
X = x1, x2, x3….xm-1 xm Y = y1, y2, y3….yn-1 yn
Z = z1, z2, z3….zk-1 zk
Silicon Institute of Technology Xi and Yj end with xi=yj
Let Xi denote the ith prefix x[1..i] of x[1..m], and
X0 denotes an empty prefix

Xi x1 x2 … xi-1 xi

Yj y1 y2 … yj-1 yj=xi

Zk z1 z2…zk-1 zk =yj=xi

Zk is Zk -1 followed by zk = yj = xi where
Zk-1 is an LCS of Xi-1 and Yj -1 and
LenLCS(i, j)=LenLCS(i-1, j-1)+1
7
Silicon Institute of Technology Xi and Yj end with xi  yj

Xi x1 x2 … xi-1 xi Xi x1 x2 … xi-1 x i

Yj y1 y2 … yj-1 yj Yj yj y1 y2 …yj-1 yj

Zk z1 z2…zk-1 zk yj Zk z1 z2…zk-1 zk  xi

Zk is an LCS of Xi and Yj -1 Zk is an LCS of Xi -1 and Yj

LenLCS(i, j)=max{LenLCS(i, j-1), LenLCS(i-1, j)}

8
Silicon Institute of Technology

C[i, j] =
Recursive Approach
Silicon Institute of Technology Writing the recurrence equation
• Let Xi denote the ith prefix x[1..i] of x[1..m], and
• X0 denotes an empty prefix
• We will first compute the length of an LCS of Xm and Yn , LenLCS(m, n),
and then use information saved during the computation for finding the
actual subsequence
• We need a recursive formula for computing LenLCS(i, j).

X = ABCBDAB
Y = BDCABA
Silicon Institute of Technology LCS Example
j 0 1 2 3 4 5 6
i Yj B D C A B A
0 Xi 0 0 0 0 0 0 0

1 A 0

2 B 0

3 C 0

4 B 0

5 D 0

6 A 0

7 B 0
Silicon Institute of Technology LCS Example
j 0 1 2 3 4 5 6
i Yj B D C A B A
0 Xi 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4
Silicon Institute of Technology LCS Example
j 0 1 2 3 4 5 6
i Yj B D C A B A
0 Xi 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4
Silicon Institute of Technology LCS Example
j 0 1 2 3 4 5 6
i Yj B D C A B A
0 Xi 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4
Silicon Institute of Technology LCS Length Algorithm
Algo LCS_Length
1. m [Link]
2. n [Link]
3. Let B[1..m, 1..n] and C[1..m, 1..n] be two tables
4. for i= 0 to m
5. C[i, 0] =0
6. for j= 0 to n
7. C[0, j] =0
Silicon Institute of Technology

8. for i= 1 to m
9. for j= 1 to n
10. if ( xi == yj)
11. then C[i, j] = C[i-1, j-1]+1
12. B[i, j] = “↖”
13. else if (C[i-1, j] >= C[i, j-1])
14. then C[i, j] = C[i-1, j]
15. B[i, j] = “↑”
16. else C[i, j] = C[i, j-1]
17. B[i, j] = “←”
Silicon Institute of Technology PRINT-LCS(B,X,i,j)
Algo PRINT-LCS(B, X, i, j)
1. if i==0 OR j==0 then return
2. if B[i, j] == “↖”
3. PRINT-LCS(B, X, i-1, j-1)
4. print x
5. else if B[i, j] == “↑”
6. PRINT-LCS(B, X, i-1, j)
7. else PRINT-LCS(B, X, i, j-1)
Silicon Institute of Technology

Thank You