Introduction to Algorithms

By
Dr. Swagata Mandal
Department of Electronics & Comm.
Jalpaiguri Government Engineering College
 What is course about?
The theoretical study of design and
analysis of computer algorithms
Basic goals for an algorithm:
• always correct
• always terminates
• This class: performance
 Performance often draws the line
between
what is possible and what is impossible.
 What is an algorithm?

• An algorithm is “a finite set of precise instructions for

performing a computation or for solving a problem”
– A program is one type of algorithm
• All programs are algorithms
• Not all algorithms are programs!
– Directions to somebody’s house is an algorithm
– A recipe for cooking a cake is an algorithm
– The steps to compute the cosine of 90° is an algorithm
 Some algorithms are harder
than others
• Some algorithms are easy
– Finding the largest (or smallest) value in a list
– Finding a specific value in a list
• Some algorithms are a bit harder
– Sorting a list
• Some algorithms are very hard
– Finding the shortest path between Miami and Seattle
• Some algorithms are essentially impossible
– Factoring large composite numbers

• In next section we’ll see how to rate how “hard”

algorithms are
 Design and Analysis of
Algorithms
• Analysis: predict the cost of an algorithm in
terms of resources and performance

• Design: design algorithms which minimize the

cost
 The problem of sorting

Input: sequence a1, a2, …, an of numbers.

Output: permutation a'1, a'2, …, a'n such

that a'1  a'2 …  a'n .

Example:
Input: 8 2 4 9 3 6
Output: 2 3 4 6 8 9
 Insertion sort
INSERTION-SORT (A, n) ⊳ A[1 . . n]
for j ← 2 to n
do key ← A[ j]
i←j–1
“pseudocode” while i > 0 and A[i] > key
do A[i+1] ← A[i]
i←i–1
A[i+1] = key
1 i j n
A:
key
sorted
Example of insertion sort
8 2 4 9 3 6
Example of insertion sort
8 2 4 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 done
 Running time

• The running time depends on the input: an

already sorted sequence is easier to sort.
• Major Simplifying Convention:
Parameterize the running time by the size of
the input, since short sequences are easier to
sort than long ones.
TA(n) = time of A on length n inputs
• Generally, we seek upper bounds on the
running time, to have a guarantee of
performance.
 Kinds of analyses
Worst-case: (usually)
• T(n) = maximum time of algorithm
on any input of size n.
Average-case: (sometimes)
• T(n) = expected time of algorithm
over all inputs of size n.
• Need assumption of statistical
distribution of inputs.
Best-case: (NEVER)
• Cheat with a slow algorithm that
works fast on some input.
 Machine-independent time
What is insertion sort’s worst-case time?

BIG IDEAS:
• Ignore machine dependent constants,
otherwise impossible to verify and to compare algorithms

• Look at growth of T(n) as n → ∞ .

“Asymptotic Analysis”
 Q-notation
DEF:
Q(g(n)) = { f (n) : there exist positive constants c1, c2, and
n0 such that 0  c1 g(n)  f (n)  c2 g(n)
for all n  n0 }
Basic manipulations:
• Drop low-order terms; ignore leading constants.
• Example: 3n3 + 90n2 – 5n + 6046 = Q(n3)
 Big O notation
• O notation is used to describe asymptotic upper bound.
• Mathematically, if f(n) describe running time of an algorithm;
f(n) is O(g(n)) if there exist positive constant C and no such
that
• 0 <=f(n) <= c g(n) for all n>=n0 n = used to give upper
bound an a function.
If a function is O(n), it is automatically O(n-square) as well !
 Ω- notation
• Just like O notation provide an asymptotic upper bound, Ω
notation provides asymptotic lower bound.
• Let f(n) define running time of an algorithm; f(n) is said to
be Ω(g (n)) if there exists positive constant C and (n0) such
that
O<= C g(n) <= f(n) for all n>=n0
n= used to given lower bound on a function
 Asymptotic performance
When n gets large enough, a Q(n2) algorithm
always beats a Q(n3) algorithm.
.
• Asymptotic analysis is a
useful tool to help to
structure our thinking
toward better algorithm
• We shouldn’t ignore
T(n) asymptotically slower
algorithms, however.
• Real-world design
situations often call for a
n n0
careful balancing
 Insertion sort analysis
Worst case: Input reverse sorted.
n
T ( n)   Q ( j )  Q n 2 [arithmetic series]
j 2
Average case: All permutations equally likely.
n
T ( n)   Q( j / 2)  Qn 2 
j 2
Is insertion sort a fast sorting algorithm?
• Moderately so, for small n.
• Not at all, for large n.
Example 2: Integer Multiplication

• Let X = A B and Y = C D where A,B,C

and D are n/2 bit integers
• Simple Method: XY = (2n/2A+B)(2n/2C+D)
• Running Time Recurrence
T(n) < 4T(n/2) + 100n

• Solution T(n) = q(n2)

Better Integer Multiplication

• Let X = A B and Y = C D where A,B,C and D

are n/2 bit integers
• Karatsuba:
XY = (2n/2+2n)AC+2n/2(A-B)(C-D) + (2n/2+1) BD
• Running Time Recurrence
T(n) < 3T(n/2) + 100n

• Solution: q(n) = O(n log 3)

Example 3:Merge sort

MERGE-SORT A[1 . . n]
1. If n = 1, done.
2. Recursively sort A[ 1 . . n/2 ]
and A[ n/2+1 . . n ] .
3. “Merge” the 2 sorted lists.

Key subroutine: MERGE

 Merging two sorted arrays
20 12
13 11
7 9
2 1
 Merging two sorted arrays
20 12
13 11
7 9
2 1

1
 Merging two sorted arrays
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2

1
 Merging two sorted arrays
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2

1 2
 Merging two sorted arrays
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2

1 2
 Merging two sorted arrays
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2

1 2 7
 Merging two sorted arrays
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2

1 2 7
 Merging two sorted arrays
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2

1 2 7 9
 Merging two sorted arrays
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2

1 2 7 9
 Merging two sorted arrays
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2

1 2 7 9 11

L1.40
 Merging two sorted arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2

1 2 7 9 11
 Merging two sorted arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2

1 2 7 9 11 12
 Merging two sorted arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2

1 2 7 9 11 12

Time = Q(n) to merge a total

of n elements (linear time).
 Analyzing merge sort

T(n) MERGE-SORT A[1 . . n]

Q(1) 1. If n = 1, done.
2T(n/2) 2. Recursively sort A[ 1 . . n/2 ]
and A[ n/2+1 . . n ] .
Q(n) 3. “Merge” the 2 sorted lists
Sloppiness: Should be T( n/2 ) + T( n/2 ) ,
but it turns out not to matter asymptotically.
Recurrence for merge sort
Q(1) if n = 1;
T(n) =
2T(n/2) + Q(n) if n > 1.
• We shall usually omit stating the base
case when T(n) = Q(1) for sufficiently
small n, but only when it has no effect on
the asymptotic solution to the recurrence.
• Couple of slides later we will provide
several ways to find a good upper bound
on T(n).
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
T(n)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2) T(n/2)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2

T(n/4) T(n/4) T(n/4) T(n/4)

 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2

cn/4 cn/4 cn/4 cn/4

Q(1)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
h = lg n cn/4 cn/4 cn/4 cn/4

Q(1)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2
h = lg n cn/4 cn/4 cn/4 cn/4

Q(1)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4

Q(1)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn

…
Q(1)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn

…
Q(1) #leaves = n Q(n)
 Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn

…
Q(1) #leaves = n Q(n)
TotalQ(n lg n)
 Conclusions

• Q(n lg n) grows more slowly than Q(n2).

• Therefore, merge sort asymptotically
beats insertion sort in the worst case.
• In practice, merge sort beats insertion
sort for n > 30 or so.
Thank You
 Introduction to Algorithms
By
Dr. Swagata Mandal
Department of Electronics & Comm.
Jalpaiguri Government Engineering College
Recall: Integer Multiplication

• Let X = A B and Y = C D where A,B,C

and D are n/2 bit integers
• Simple Method: XY = (2n/2A+B)(2n/2C+D)
• Running Time Recurrence
T(n) < 4T(n/2) + 100n

How do we solve it?

 Substitution method
The most general method:
1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
Example: T(n) = 4T(n/2) + 100n
• [Assume that T(1) = Q(1).]
• Guess O(n3) . (Prove O and W separately.)
• Assume that T(k)  ck3 for k < n .
• Prove T(n)  cn3 by induction.
 Example of substitution
T ( n) = 4T ( n / 2) + 100n
 4c( n / 2)3 + 100n
= (c / 2) n3 + 100n
= cn3 - ((c / 2) n3 -100n )
desired – residual
 cn 3 desired
whenever (c/2)n3 – 100n  0, for
example, if c  200 and n  1.
residual
 Example (continued)
• We must also handle the initial conditions,
that is, ground the induction with base
cases.
• Base: T(n) = Q(1) for all n < n0, where n0
is a suitable constant.
• For 1  n < n0, we have “Q(1)”  cn3, if we
pick c big enough.

This bound is not tight!

 A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k)  ck2 for k < n:
T ( n) = 4T ( n / 2) + 100n
 cn 2 + 100n
 cn2

for no choice of c > 0. Lose!

 A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k)  c1k2 – c2k for k < n.
T ( n) = 4T ( n / 2) + 100n
 4(c1 (n / 2) 2 - c2 (n / 2))+ 100n
= c1n 2 - 2c2 n + 100n
= c1n 2 - c2 n - (c2 n -100n)
 c1n 2 - c2 n if c > 100.
2
Pick c1 big enough to handle the initial conditions.
 Recursion-tree method
• A recursion tree models the costs (time) of a
recursive execution of an algorithm.
• The recursion tree method is good for
generating guesses for the substitution method.
• The recursion-tree method can be unreliable,
just like any method that uses ellipses (…).
• The recursion-tree method promotes intuition,
however.
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
T(n)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
T(n/4) T(n/2)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4)

 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

Q(1)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

Q(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
5 n2
(n/4)2 (n/2)2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2

Q(1)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
Q(1)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
Q(1) Total = n2
   + 
1 + 16 + 16
5 5 2 5 3
16
+ 
= Q(n2) geometric series
 Divide and Conquer Paradigm

• An important general technique for

designing algorithms:
• divide problem into subproblems
• recursively solve subproblems
• combine solutions to subproblems to get solution
to original problem
• Use recurrences to analyze the running time
of such algorithms
 Example: Merge-sort

• DIVIDE the input sequence in half

• RECURSIVELY sort the two halves
• basis of the recursion is sequence with 1 key
• COMBINE the two sorted subsequences by
merging them
 Mergesort Example
5 2 4 6 1 3 2 6

5 2 4 6 1 3 2 6

5 2 4 6 1 3 2 6

5 2 4 6 1 3 2

2 5 4 6 1 3 2 6

2 4 5 6 1 2 3 6

1 2 2 3 4 5 6 6
Recurrence Relation for Mergesort

• Let T(n) be worst case time on a sequence of n

keys
• If n = 1, then T(n) = Q(1) (constant)
• If n > 1, then T(n) = 2 T(n/2) + Q(n)
• two subproblems of size n/2 each that are solved
recursively
• Q(n) time to do the merge
 How To Solve Recurrences
• Ad hoc method:
• expand several times
• guess the pattern
• can verify with proof by induction
• Master theorem
• general formula that works if recurrence has the form T(n) =
aT(n/b) + f(n)
• a is number of subproblems
• n/b is size of each subproblem
• f(n) is cost of non-recursive part
 Master Theorem
Consider a recurrence of the form
T(n) = a T(n/b) + f(n)
with a>=1, b>1, and f(n) eventually positive.
a) If f(n) = O(nlogb(a)-), then T(n)=Q(nlogb(a)).
b) If f(n) = Q(nlogb(a) ), then T(n)=Q(nlogb(a) log(n)).
c) If f(n) = W(nlogb(a)+) and f(n) is regular, then
T(n)=Q(f(n))
[f(n) regular iff eventually af(n/b)<= cf(n) for some
constant c<1]
Excuse me, what did it say???
Essentially, the Master theorem compares the
function f(n)
with the function g(n)=nlogb(a).
Roughly, the theorem says:
a) If f(n) << g(n) then T(n)=Q(g(n)).
b) If f(n)  g(n) then T(n)=Q(g(n)log(n)).
c) If f(n) >> g(n) then T(n)=Q(f(n)).
Now go back and memorize the theorem!
 The master method

The master method applies to recurrences of

the form
T(n) = a T(n/b) + f (n) ,
where a  1, b > 1, and f is asymptotically
positive.
 Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)

…
#leaves = ah
= alogbn nlogbaT (1)
T (1)
= nlogba
 Three common cases
Compare f (n) with nlogba:
1. f (n) = O(nlogba – ) for some constant  > 0.
• f (n) grows polynomially slower than nlogba
(by an n factor).
Solution: T(n) = Q(nlogba) .
 Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)

…
CASE 1: The weight increases
geometrically from the root to the nlogbaT (1)
T (1) leaves. The leaves hold a constant
fraction of the total weight. Q(nlogba)
 Three common cases
Compare f (n) with nlogba:

2. f (n) = Q(nlogba lgkn) for some constant k  0.

• f (n) and nlogba grow at similar rates.
Solution: T(n) = Q(nlogba lgk+1n) .
 Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)

…
CASE 2: (k = 0) The weight
nlogbaT (1)
T (1) is approximately the same on
each of the logbn levels.
Q(nlogbalg n)
 Three common cases (cont.)
Compare f (n) with nlogba:
3. f (n) = W(nlogba + ) for some constant  > 0.
• f (n) grows polynomially faster than nlogba (by
an n factor),
and f (n) satisfies the regularity condition that
a f (n/b)  c f (n) for some constant c < 1.
Solution: T(n) = Q( f (n) ) .
 Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)

…
CASE 3: The weight decreases
geometrically from the root to the nlogbaT (1)
T (1) leaves. The root holds a constant
fraction of the total weight. Q( f (n))
 Examples

Ex. T(n) = 4T(n/2) + n

a = 4, b = 2  nlogba = n2; f (n) = n.
CASE 1: f (n) = O(n2 – ) for  = 1.
 T(n) = Q(n2).

Ex. T(n) = 4T(n/2) + n2

a = 4, b = 2  nlogba = n2; f (n) = n2.
CASE 2: f (n) = Q(n2lg0n), that is, k = 0.
 T(n) = Q(n2lg n).
 Examples
Ex. T(n) = 4T(n/2) + n3
a = 4, b = 2  nlogba = n2; f (n) = n3.
CASE 3: f (n) = W(n2 + ) for  = 1
and 4(cn/2)3  cn3 (reg. cond.) for c = 1/2.
 T(n) = Q(n3).

Ex. T(n) = 4T(n/2) + n2/lg n

a = 4, b = 2  nlogba = n2; f (n) = n2/lg n.
Master method does not apply. In particular,
for every constant  > 0, we have n = w(lg n).
 Idea of the Proof
Let us iteratively substitute the recurrence:
T (n) = aT (n / b) + f (n)
= a (aT (n / b 2 )) + f (n / b)) + bn
= a 2T (n / b 2 ) + af (n / b) + f (n)
= a 3T (n / b 3 ) + a 2 f (n / b 2 ) + af (n / b) + f (n)
= ...
(logb n ) -1
= a logb nT (1) +  a f
i =0
( ni
/ b i
)
(log b n ) -1
= n logb aT (1) +  a f
i =0
( n i
/ b i
)
 Idea of the Proof
Thus, we obtained

T(n) = nlogb(a) T(1) +  ai f(n/bi)

The proof proceeds by distinguishing three cases:
1) The first term in dominant: f(n) = O(nlogb(a)-)
2) Each part of the summation is equally dominant: f(n) =
Q(nlogb(a) )
3) The summation can be bounded by a geometric series: f(n) =
W(nlogb(a)+) and the regularity of f is key to make the
argument work.
Thank You
Design and Analysis
of Algorithm
By
Dr. Swagata Mandal
Assistant Professor, Department of Electronics and
Communication
Jalpaiguri Government Engineering College
 Basic Matrix Multiplication
Suppose we want to multiply two matrices of size N
x N: for example A x B = C.

C11 = a11b11 + a12b21

C12 = a11b12 + a12b22
C21 = a21b11 + a22b21 2x2 matrix multiplication can be
accomplished in 8 multiplication.(2log28 =23)
C22 = a21b12 + a22b22
 Basic Matrix Multiplication
void matrix_mult (){
for (i = 1; i <= N; i++) {
algorithm
for (j = 1; j <= N; j++) {
compute Ci,j;
}
}}

N
Ci , j =  ai ,k bk , j
k =1
Time analysis N N N
Thus T ( N ) =  c = cN 3 = O ( N 3 )
i =1 j =1 k =1
 Strassens’s Matrix Multiplication
• Strassen showed that 2x2 matrix multiplication can be accomplished
in 7 multiplication and 18 additions or subtractions. .(2log27 =22.807)
• This reduce can be done by Divide and Conquer Approach.
• Divide-and conquer is a general algorithm design
paradigm:
• Divide: divide the input data S in two or more disjoint
subsets S1, S2, …
• Recur: solve the subproblems recursively
• Conquer: combine the solutions for S1, S2, …, into a
solution for S
• The base case for the recursion are subproblems of
constant size
• Analysis can be done using recurrence equations
Divide and Conquer Matrix Multiply
A  B = R
A0 A1 B0 B1 A0B0+A1B2 A0B1+A1B3
 =
A2 A3 B2 B3 A2B0+A3B2 A2B1+A3B3

a0  b0 = a0  b0

•Divide matrices into sub-matrices: A0 , A1, A2 etc

•Use blocked matrix multiply equations
•Recursively multiply sub-matrices
•Terminate recursion with a simple base case
 Strassens’s Matrix Multiplication

P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11 C11 = P1 + P4 - P5 + P7
P3 = A11 * (B12 - B22) C12 = P3 + P5
P4 = A22 * (B21 - B11) C21 = P2 + P4
P5 = (A11 + A12) * B22 C22 = P1 + P3 - P2 + P6
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
Strassens’s Matrix Multiplication

C11 = P1 + P4 - P5 + P7
= (A11+ A22)(B11+B22) + A22 * (B21 - B11) - (A11 + A12) * B22+
(A12 - A22) * (B21 + B22)
= A11 B11 + A11 B22 + A22 B11 + A22 B22 + A22 B21 – A22 B11 -
A11 B22 -A12 B22 + A12 B21 + A12 B22 – A22 B21 – A22 B22
= A11 B11 + A12 B21
 Strassen Algorithm
void matmul(int *A, int *B, int *R, int n) {
if (n == 1) { Timing Analysis
(*R) += (*A) * (*B);
} else {
matmul(A, B, R, n/4);
matmul(A, B+(n/4), R+(n/4), n/4);
matmul(A+2*(n/4), B, R+2*(n/4), n/4);
matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);
matmul(A+(n/4), B+2*(n/4), R, n/4);
matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);
matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);
matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4);
} Divide matrices in
sub-matrices and
recursively multiply
sub-matrices
 A short list of categories of
Algorithms
• Algorithm types we will consider include:
• Simple recursive algorithms
• Backtracking algorithms
• Divide and conquer algorithms
• Dynamic programming algorithms
• Greedy algorithms
• Branch and bound algorithms
• Brute force algorithms
• Randomized algorithms
 Simple recursive algorithms
• A simple recursive algorithm:
• Solves the base cases directly
• Recurs with a simpler subproblem
• Does some extra work to convert the solution to the simpler
subproblem into a solution to the given problem
• I call these “simple” because several of the other
algorithm types are inherently recursive
 Example recursive algorithms
• To count the number of elements in a list:
• If the list is empty, return zero; otherwise,
• Step past the first element, and count the remaining elements
in the list
• Add one to the result
• To test if a value occurs in a list:
• If the list is empty, return false; otherwise,
• If the first thing in the list is the given value, return true;
otherwise
• Step past the first element, and test whether the value occurs
in the remainder of the list
 Backtracking algorithms
• Backtracking algorithms are based on a depth-first
recursive search
• A backtracking algorithm:
• Tests to see if a solution has been found, and if so, returns it;
otherwise
• For each choice that can be made at this point,
• Make that choice
• Recur
• If the recursion returns a solution, return it
• If no choices remain, return failure
 Example backtracking algorithm
• To color a map with no more than four colors:
• color(Country n):
• If all countries have been colored (n > number of countries) return
success; otherwise,
• For each color c of four colors,
• If country n is not adjacent to a country that has been
colored c
• Color country n with color c
• recursively color country n+1
• If successful, return success
• If loop exits, return failure
 Divide and Conquer
• A divide and conquer algorithm consists of two parts:
• Divide the problem into smaller subproblems of the same
type, and solve these subproblems recursively
• Combine the solutions to the subproblems into a solution to
the original problem
• Traditionally, an algorithm is only called “divide and
conquer” if it contains at least two recursive calls
 Examples
• Quicksort:
• Partition the array into two parts (smaller numbers in one
part, larger numbers in the other part)
• Quicksort each of the parts
• No additional work is required to combine the two sorted
parts
• Mergesort:
• Cut the array in half, and mergesort each half
• Combine the two sorted arrays into a single sorted array by
merging them
 Binary tree lookup
• Here’s how to look up something in a sorted binary tree:
• Compare the key to the value in the root
• If the two values are equal, report success
• If the key is less, search the left subtree
• If the key is greater, search the right subtree
• This is not a divide and conquer algorithm because, although there are two recursive
calls, only one is used at each level of the recursion
• Fibonacci numbers
• To find the nth Fibonacci number:
• If n is zero or one, return one; otherwise,
• Compute fibonacci(n-1) and fibonacci(n-2)
• Return the sum of these two numbers

• This is an expensive algorithm

• It requires O(fibonacci(n)) time
• This is equivalent to exponential time, that is, O(2n)
 Dynamic programming algorithms
• A dynamic programming algorithm remembers past
results and uses them to find new results
• Dynamic programming is generally used for optimization
problems
• Multiple solutions exist, need to find the “best” one
• Requires “optimal substructure” and “overlapping
subproblems”
• Optimal substructure: Optimal solution contains optimal solutions to
subproblems
• Overlapping subproblems: Solutions to subproblems can be stored
and reused in a bottom-up fashion
• This differs from Divide and Conquer, where
subproblems generally need not overlap
 Fibonacci numbers again
• To find the nth Fibonacci number:
• If n is zero or one, return one; otherwise,
• Compute, or look up in a table, fibonacci(n-1) and
fibonacci(n-2)
• Find the sum of these two numbers
• Store the result in a table and return it
• Since finding the nth Fibonacci number involves finding
all smaller Fibonacci numbers, the second recursive call
has little work to do
• The table may be preserved and used again later
 Greedy algorithms
• An optimization problem is one in which you want to
find, not just a solution, but the best solution
• A “greedy algorithm” sometimes works well for
optimization problems
• A greedy algorithm works in phases: At each phase:
• You take the best you can get right now, without regard for
future consequences
• You hope that by choosing a local optimum at each step, you
will end up at a global optimum
 Example: Counting money
• Suppose you want to count out a certain amount of
money, using the fewest possible bills and coins
• A greedy algorithm would do this would be:
At each step, take the largest possible bill or coin
that does not overshoot
• Example: To make $6.39, you can choose:
• a $5 bill
• a $1 bill, to make $6
• a 25¢ coin, to make $6.25
• A 10¢ coin, to make $6.35
• four 1¢ coins, to make $6.39
• For US money, the greedy algorithm always gives
the optimum solution
A failure of the greedy algorithm
• In some (fictional) monetary system, “krons” come
in 1 kron, 7 kron, and 10 kron coins
• Using a greedy algorithm to count out 15 krons, you
would get
• A 10 kron piece
• Five 1 kron pieces, for a total of 15 krons
• This requires six coins
• A better solution would be to use two 7 kron pieces
and one 1 kron piece
• This only requires three coins
• The greedy algorithm results in a solution, but not
in an optimal solution
 Branch and bound algorithms
• Branch and bound algorithms are generally used for
optimization problems
• As the algorithm progresses, a tree of subproblems is formed
• The original problem is considered the “root problem”
• A method is used to construct an upper and lower bound for a
given problem
• At each node, apply the bounding methods
• If the bounds match, it is deemed a feasible solution to that particular
subproblem
• If bounds do not match, partition the problem represented by that
node, and make the two subproblems into children nodes
• Continue, using the best known feasible solution to trim
sections of the tree, until all nodes have been solved or
trimmed
Example branch and bound algorithm
• Traveling salesman problem: A salesman has to visit
each of n cities (at least) once each, and wants to
minimize total distance traveled
• Consider the root problem to be the problem of finding the
shortest route through a set of cities visiting each city once
• Split the node into two child problems:
• Shortest route visiting city A first
• Shortest route not visiting city A first
• Continue subdividing similarly as the tree grows
 Brute force algorithm
• A brute force algorithm simply tries all possibilities until a
satisfactory solution is found
• Such an algorithm can be:
• Optimizing: Find the best solution. This may require
finding all solutions, or if a value for the best solution is
known, it may stop when any best solution is found
• Example: Finding the best path for a traveling
salesman
• Satisficing: Stop as soon as a solution is found that is
good enough
• Example: Finding a traveling salesman path that is
within 10% of optimal
 Improving brute force algorithms
• Often, brute force algorithms require exponential time
• Various heuristics and optimizations can be used
• Heuristic: A “rule of thumb” that helps you decide which possibilities to look
at first
• Optimization: In this case, a way to eliminate certain possibilities without fully
exploring them
 Randomized algorithms
• A randomized algorithm uses a random number at
least once during the computation to make a decision
• Example: In Quicksort, using a random number to choose a
pivot
• Example: Trying to factor a large number by choosing
random numbers as possible divisors
 Greedy Algorithms
Optimization problems
• An optimization problem is one in which you want to find, not just
a solution, but the best solution
• A “greedy algorithm” sometimes works well for optimization
problems
• A greedy algorithm works in phases. At each phase:
• You take the best you can get right now, without regard for future
consequences
• You hope that by choosing a local optimum at each step, you will end up
at a global optimum
 A scheduling problem
• You have to run nine jobs, with running times of 3, 5, 6, 10, 11,
14, 15, 18, and 20 minutes
• You have three processors on which you can run these jobs
• You decide to do the longest-running jobs first, on whatever
processor is available
P1 20 10 3
P2
18 11 6
P3
15 14 5

• Time to completion: 18 + 11 + 6 = 35 minutes

• This solution isn’t bad, but we might be able to do better
 Another approach
• What would be the result if you ran the shortest job first?
• Again, the running times are 3, 5, 6, 10, 11, 14, 15, 18, and 20
minutes

P1 3 10 15
P2
5 11 18
P3
6 14 20

• That wasn’t such a good idea; time to completion is now

6 + 14 + 20 = 40 minutes
• Note, however, that the greedy algorithm itself is fast
• All we had to do at each stage was pick the minimum or maximum
 An optimum solution
• Better solutions do exist:

P1 20 14
P2
18 11 5
P3
15 10 6 3

• This solution is clearly optimal (why?)

• Clearly, there are other optimal solutions (why?)
• How do we find such a solution?
• One way: Try all possible assignments of jobs to processors
• Unfortunately, this approach can take exponential time
 Huffman encoding
• The Huffman encoding algorithm is a greedy algorithm
• You always pick the two smallest numbers to combine

100 • Average bits/char:

0.22*2 + 0.12*3 +
54 0.24*2 + 0.06*4 +
A=00 0.27*2 + 0.09*4
27
B=100 = 2.42
C=01
46 15 D=1010 • The Huffman
E=11 algorithm finds an
F=1011 optimal solution
22 12 24 6 27 9
A B C D E F
 Minimum spanning tree
• A minimum spanning tree is a least-cost subset of the edges of a
graph that connects all the nodes
• Start by picking any node and adding it to the tree
• Repeatedly: Pick any least-cost edge from a node in the tree to a
node not in the tree, and add the edge and new node to the tree
• Stop when all nodes have been added to the tree

• The result is a least-cost

4
6 (3+3+2+2+2=12) spanning tree
2
4 • If you think some other edge should be
1 5 in the spanning tree:
3 2
• Try adding that edge
3 3 2 3 • Note that the edge is part of a cycle
3 • To break the cycle, you must remove
4
2 the edge with the greatest cost
4
• This will be the edge you just added
 Traveling salesman
• A salesman must visit every city (starting from city A), and wants to cover the
least possible distance
• He can revisit a city (and reuse a road) if necessary
• He does this by using a greedy algorithm: He goes to the next nearest city from
wherever he is
• From A he goes to B
A 2 B 4 C • From B he goes to D
• This is not going to result in a
3 3 shortest path!
4 4
• The best result he can get now will
be ABDBCE, at a cost of 16
D • An actual least-cost path from A is
E ADBCE, at a cost of 14
 Analysis
• A greedy algorithm typically makes (approximately) n choices for
a problem of size n
• (The first or last choice may be forced)
• Hence the expected running time is:
O(n * O(choice(n))), where choice(n) is making a choice among
n objects
• Counting: Must find largest useable coin from among k sizes of coin (k is a
constant), an O(k)=O(1) operation;
• Therefore, coin counting is (n)
• Huffman: Must sort n values before making n choices
• Therefore, Huffman is O(n log n) + O(n) = O(n log n)
• Minimum spanning tree: At each new node, must include new edges and
keep them sorted, which is O(n log n) overall
• Therefore, MST is O(n log n) + O(n) = O(n log n)
 Other greedy algorithms
• Dijkstra’s algorithm for finding the shortest path in a
graph
• Always takes the shortest edge connecting a known node to
an unknown node
• Kruskal’s algorithm for finding a minimum-cost spanning
tree
• Always tries the lowest-cost remaining edge
• Prim’s algorithm for finding a minimum-cost spanning
tree
• Always takes the lowest-cost edge between nodes in the
spanning tree and nodes not yet in the spanning tree
 Dijkstra’s shortest-path algorithm
• Dijkstra’s algorithm finds the shortest paths from a given node to all other nodes in
a graph
• Initially,
• Mark the given node as known (path length is zero)
• For each out-edge, set the distance in each neighboring node equal to the
cost (length) of the out-edge, and set its predecessor to the initially given
node
• Repeatedly (until all nodes are known),
• Find an unknown node containing the smallest distance
• Mark the new node as known
• For each node adjacent to the new node, examine its neighbors to see
whether their estimated distance can be reduced (distance to known node
plus cost of out-edge)
• If so, also reset the predecessor of the new node
 Connecting wires
• There are n white dots and n black dots, equally spaced, in a line
• You want to connect each white dot with some one black dot, with a minimum
total length of “wire”
• Example:

• Total wire length above is 1 + 1 + 1 + 5 = 8

• Do you see a greedy algorithm for doing this?
• Does the algorithm guarantee an optimal solution?
• Can you prove it?
• Can you find a counterexample?
 Collecting coins
• A checkerboard has a certain number of coins on it
• A robot starts in the upper-left corner, and walks to the bottom
left-hand corner
• The robot can only move in two directions: right and down
• The robot collects coins as it goes
• You want to collect all the coins using the minimum number of
steps
• Example:
• Do you see a greedy algorithm for doing
this?
• Does the algorithm guarantee an
optimal solution?
• Can you prove it?
• Can you find a counterexample?
Thank You
 Design and Analysis of
Algorithm

By
Dr. Swagata Mandal
Assistant Professor, Department of Electronics
and Communication
Jalpaiguri Government Engineering College
 Dynamic Programming
• An algorithm design technique (like divide and
conquer)

• Divide and conquer

– Partition the problem into independent subproblems

– Solve the subproblems recursively

– Combine the solutions to solve the original problem

2
 Dynamic Programming
• Applicable when subproblems are not independent
– Subproblems share subsubproblems
E.g.: Combinations:
n n-1 n-1
= +
k k k-1

n n
=1 =1
1 n

– A divide and conquer approach would repeatedly solve the

common subproblems
– Dynamic programming solves every subproblem just once and
stores the answer in a table

3
 Example: Combinations

Comb (6,4)

= Comb (5, 3) + Comb (5, 4)

= Comb (4,2) Comb (4, 3) + Comb (4, 3) + Comb (4, 4)

+

= Comb (3, 1)+ + Comb (3, 2) + Comb (3, 2) + Comb

+ (3, 3) + Comb
+ (3, 2) + Comb
+ (3, 3) + 1

= 3 + 1) + Comb (2, 2) + +Comb (2, 1) + Comb (2,

+ Comb (2, + 2) + 1 + +Comb (2, 1) + Comb (2,
+ 2) + 1 + 1+

= 3 + 2 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 1

n n-1 n-1
= +
k k k-1

4
 Dynamic Programming
• Used for optimization problems
– A set of choices must be made to get an optimal
solution
– Find a solution with the optimal value (minimum or
maximum)
– There may be many solutions that lead to an optimal
value
– Our goal: find an optimal solution

5
 Dynamic Programming Algorithm
1. Characterize the structure of an optimal
solution
2. Recursively define the value of an optimal
solution
3. Compute the value of an optimal solution in a
bottom-up fashion
4. Construct an optimal solution from computed
information (not always necessary)

6
 Assembly Line Scheduling
• Automobile factory with two assembly lines
– Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n
– Corresponding stations S1, j and S2, j perform the same function
but can take different amounts of time a1, j and a2, j
– Entry times are: e1 and e2; exit times are: x1 and x2

7
 Assembly Line Scheduling
• After going through a station, can either:
– stay on same line at no cost, or
– transfer to other line: cost after Si,j is ti,j , j = 1, . . . , n - 1

8
 Assembly Line Scheduling
• Problem:
what stations should be chosen from line 1 and which
from line 2 in order to minimize the total time through the
factory for one car?

9
 One Solution
• Brute force
– Enumerate all possibilities of selecting stations
– Compute how long it takes in each case and choose
the best one
• Solution: 1 2 3 4 n

1 0 0 1 1

0 if choosing line 2 1 if choosing line 1

at step j (= 3) at step j (= n)

– There are 2n possible ways to choose stations

– Infeasible when n is large!!

10
1. Structure of the Optimal Solution

• How do we compute the minimum time of going through

a station?

11
1. Structure of the Optimal Solution
• Let’s consider all possible ways to get from the
starting point through station S1,j
– We have two choices of how to get to S1, j:
• Through S1, j - 1, then directly to S1, j
• Through S2, j - 1, then transfer over to S1, j
S1,j-1 S1,j
Line 1 a1,j-1 a1,j

t2,j-1

Line 2 a2,j-1
S2,j-1

12
1. Structure of the Optimal Solution
• Suppose that the fastest way through S1, j is
through S1, j – 1
– We must have taken a fastest way from entry through S1, j – 1
– If there were a faster way through S1, j - 1, we would use it instead
• Similarly for S2, j – 1
S1,j-1 S1,j
Line 1
a1,j-1 a1,j

Optimal Substructure t2,j-1

a2,j-1
Line 2
S2,j-1

13
 Optimal Substructure
• Generalization: an optimal solution to the
problem “find the fastest way through S1, j” contains
within it an optimal solution to subproblems: “find
the fastest way through S1, j - 1 or S2, j – 1”.

• This is referred to as the optimal substructure

property

• We use this property to construct an optimal

solution to a problem from optimal solutions to
subproblems
14
 2. A Recursive Solution
• Define the value of an optimal solution in terms of the optimal
solution to subproblems

15
 2. A Recursive Solution (cont.)
• Definitions:
– f* : the fastest time to get through the entire factory
– fi[j] : the fastest time to get from the starting point through station Si,j

f* = min (f1[n] + x1, f2[n] + x2)

16
 2. A Recursive Solution (cont.)
• Base case: j = 1, i=1,2 (getting through station 1)
f1[1] = e1 + a1,1
f2[1] = e2 + a2,1

17
 2. A Recursive Solution (cont.)
• General Case: j = 2, 3, …,n, and i = 1, 2
• Fastest way through S1, j is either:
– the way through S1, j - 1 then directly through S1, j, or
f1[j - 1] + a1,j
– the way through S2, j - 1, transfer from line 2 to line 1, then through S1, j
f2[j -1] + t2,j-1 + a1,j
S1,j-1 S1,j
Line 1
a1,j-1 a1,j

f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) t2,j-1

a2,j-1
Line 2
S2,j-1
18
 2. A Recursive Solution (cont.)

e1 + a1,1 if j = 1
f1[j] =
min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) if j ≥ 2

e2 + a2,1 if j = 1
f2[j] =
min(f2[j - 1] + a2,j ,f1[j -1] + t1,j-1 + a2,j) if j ≥ 2

19
3. Computing the Optimal Solution
f* = min (f1[n] + x1, f2[n] + x2)
f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j)
f2[j] = min(f2[j - 1] + a2,j ,f1[j -1] + t1,j-1 + a2,j)
1 2 3 4 5
f1[j] f1(1) f1(2) f1(3) f1(4) f1(5)

f2[j] f2(1) f2(2) f2(3) f2(4) f2(5)

4 times 2 times

• Solving top-down would result in exponential

running time

20
3. Computing the Optimal Solution
• For j ≥ 2, each value fi[j] depends only on the
values of f1[j – 1] and f2[j - 1]
• Idea: compute the values of fi[j] as follows:

in increasing order of j
1 2 3 4 5
f1[j]
f2[j]

• Bottom-up approach
– First find optimal solutions to subproblems
– Find an optimal solution to the problem from the
subproblems 21
Example

e1 + a1,1, if j = 1
f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) if j ≥ 2
1 2 3 4 5
f1[j] 9 18[1] 20[2] 24[1] 32[1]
f* = 35[1]
f2[j] 12 16[1] 22[2] 25[1] 30[2]
22
 FASTEST-WAY(a, t, e, x, n)
1. f1[1] ← e1 + a1,1
2. f2[1] ← e2 + a2,1 Compute initial values of f1 and f2

3. for j ← 2 to n
O(N)
4. do if f1[j - 1] + a1,j ≤ f2[j - 1] + t2, j-1 + a1, j
5. then f1[j] ← f1[j - 1] + a1, j
Compute the values of
6. l1[j] ← 1 f1[j] and l1[j]
7. else f1[j] ← f2[j - 1] + t2, j-1 + a1, j
8. l1[j] ← 2
9. if f2[j - 1] + a2, j ≤ f1[j - 1] + t1, j-1 + a2, j
10. then f2[j] ← f2[j - 1] + a2, j
Compute the values of
11. l2[j] ← 2 f2[j] and l2[j]
12. else f2[j] ← f1[j - 1] + t1, j-1 + a2, j
13. l2[j] ← 1
23
 FASTEST-WAY(a, t, e, x, n) (cont.)
14. if f1[n] + x1 ≤ f2[n] + x2
15. then f* = f1[n] + x1
Compute the values of
16. l* = 1 the fastest time through the
17. else f* = f2[n] + x2 entire factory

18. l* = 2

24
 4. Construct an Optimal Solution
Alg.: PRINT-STATIONS(l, n)
i ← l*
print “line ” i “, station ” n
for j ← n downto 2
do i ←li[j]
print “line ” i “, station ” j - 1
1 2 3 4 5
f1[j]/l1[j] 9 18[1] 20[2] 24[1] 32[1]
l* = 1
f2[j]/l2[j] 12 16[1] 22[2] 25[1] 30[2]

25
 Matrix-Chain Multiplication
Problem: given a sequence A1, A2, …, An,
compute the product:
A1  A2  An

• Matrix compatibility:
C=AB C=A1  A2  Ai  Ai+1  An
colA = rowB coli = rowi+1
rowC = rowA rowC = rowA1
colC = colB colC = colAn

26
 MATRIX-MULTIPLY(A, B)
if columns[A]  rows[B]
then error “incompatible dimensions”
else for i  1 to rows[A]
do for j  1 to columns[B] rows[A]  cols[A]  cols[B]
do C[i, j] = 0 multiplications

for k  1 to columns[A]
k do C[i, j]  C[i, j] + A[i, k] B[k, j]
j cols[B]
j cols[B]

i = i
* k
A B C
rows[A]
rows[A] 27
 Matrix-Chain Multiplication
• In what order should we multiply the matrices?
A1  A2  An
• Parenthesize the product to get the order in which
matrices are multiplied
• E.g.: A1  A2  A3 = ((A1  A2)  A3)
= (A1  (A2  A3))
• Which one of these orderings should we choose?
– The order in which we multiply the matrices has a
significant impact on the cost of evaluating the product
28
 Example
A1  A2  A3
• A1: 10 x 100
• A2: 100 x 5
• A3: 5 x 50
1. ((A1  A2)  A3): A1  A2 = 10 x 100 x 5 = 5,000 (10 x 5)
((A1  A2)  A3) = 10 x 5 x 50 = 2,500
Total: 7,500 scalar multiplications
2. (A1  (A2  A3)): A2  A3 = 100 x 5 x 50 = 25,000 (100 x 50)
(A1  (A2  A3)) = 10 x 100 x 50 = 50,000
Total: 75,000 scalar multiplications
one order of magnitude difference!!
29
 Matrix-Chain Multiplication:
Problem Statement
• Given a chain of matrices A1, A2, …, An, where
Ai has dimensions pi-1x pi, fully parenthesize the
product A1  A2  An in a way that minimizes the
number of scalar multiplications.
A1  A2  Ai  Ai+1  An
p0 x p1 p1 x p2 pi-1 x pi pi x pi+1 pn-1 x pn

30
 1. The Structure of an Optimal
Parenthesization
• Notation:
Ai…j = Ai Ai+1  Aj, 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

31
 Optimal Substructure
Ai…j = Ai…k Ak+1…j

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

optimal parentesization
• 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  contradiction!
• An optimal solution to an instance of the matrix-chain
multiplication contains within it optimal solutions to
subproblems

32
 2. 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

33
 2. 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
34
 2. 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

35
 3. 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

• Computing the optimal solution recursively takes

exponential time!
1 2 3 n
• How many subproblems? n
 (n2)
– Parenthesize Ai…j
for 1  i  j  n j
3
– One problem for each 2
choice of i and j 1
i 36
3. 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]?

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

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

– Subproblems’ size is one less than the original size

– Idea: fill in m such that it corresponds to solving problems of

increasing length

37
3. 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

• Length = 1: i = j, i = 1, 2, …, n
• Length = 2: j = i + 1, i = 1, 2, …, n-1
1 2 3 n
n
m[1, n] gives the optimal
solution to the problem

j
Compute rows from bottom to top 3
and from left to right 2
1
i 38
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
6
5
• Values m[i, j] depend only
4
j on values that have been
3
previously computed
2
1

i
39
Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
1 2 3
Compute A1  A2  A3 2
3 2
7500 25000 0
• A1: 10 x 100 (p0 x p1)
1
2 0
• A2: 100 x 5 (p1 x p2) 5000

• A3: 5 x 50 (p2 x p3) 1 0

m[i, i] = 0 for i = 1, 2, 3
m[1, 2] = m[1, 1] + m[2, 2] + p0p1p2 (A1A2)
= 0 + 0 + 10 *100* 5 = 5,000
m[2, 3] = m[2, 2] + m[3, 3] + p1p2p3 (A2A3)
= 0 + 0 + 100 * 5 * 50 = 25,000
m[1, 3] = min m[1, 1] + m[2, 3] + p0p1p3 = 75,000 (A1(A2A3))
m[1, 2] + m[3, 3] + p0p2p3 = 7,500 ((A1A2)A3)
40
Matrix-Chain-Order(p)

O(N3)

41
 4. Construct the Optimal Solution
• In a similar matrix s we
keep the optimal 1 2 3 n
values of k n
• s[i, j] = a value of k
such that an optimal k
j
parenthesization of 3
Ai..j splits the product 2
between Ak and Ak+1 1

42
 4. Construct the Optimal Solution
• s[1, n] is associated with
the entire product A1..n
1 2 3 n
– The final matrix
n
multiplication will be split
at k = s[1, n]
A1..n = A1..s[1, n]  As[1, n]+1..n
j
– For each subproduct 3
recursively find the 2
corresponding value of k 1
that results in an optimal
parenthesization

43
 4. 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 5 6
6 3 3 3 5 5 -
• s[1, n] = 3  A1..6 = A1..3 A4..6
5 3 3 3 4 -
• s[1, 3] = 1  A1..3 = A1..1 A2..3
4 3 3 3 -
• s[4, 6] = 5  A4..6 = A4..5 A6..6
3 1 2 -
j
2 1 -
1 -
i
44
 4. Construct the Optimal Solution (cont.)

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

45
Example: A1  A6 ( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )

PRINT-OPT-PARENS(s, i, j) s[1..6, 1..6] 1 2 3 4 5 6

if i = j 6 3 3 3 5 5 -
then print “A”i 5 3 3 3 4 -
else print “(”
4 3 3 3 -
PRINT-OPT-PARENS(s, i, s[i, j]) j
PRINT-OPT-PARENS(s, s[i, j] + 1, j) 3 1 2 -
print “)” 2 1 -
P-O-P(s, 1, 6) s[1, 6] = 3 1 -
i = 1, j = 6 “(“ P-O-P (s, 1, 3) s[1, 3] = 1 i
i = 1, j = 3 “(“ P-O-P(s, 1, 1)  “A1”
P-O-P(s, 2, 3) s[2, 3] = 2
i = 2, j = 3 “(“ P-O-P (s, 2, 2)  “A2”
P-O-P (s, 3, 3)  “A3”
“)”
“)” … 46
 Memoization
• Top-down approach with the efficiency of typical dynamic
programming approach

• Maintaining an entry in a table for the solution to each

subproblem
– memoize the inefficient recursive algorithm

• When a subproblem is first encountered its solution is

computed and stored in that table

• Subsequent “calls” to the subproblem simply look up that

value
47
 Memoized Matrix-Chain
Alg.: MEMOIZED-MATRIX-CHAIN(p)

1. n  length[p] – 1

2. for i  1 to n
Initialize the m table with
3. do for j  i to n large values that indicate
whether the values of m[i, j]
have been computed
4. do m[i, j]  

5. return LOOKUP-CHAIN(p, 1, n) Top-down approach

48
 Memoized Matrix-Chain
Alg.: LOOKUP-CHAIN(p, i, j) Running time is O(n3)

1. if m[i, j] < 
2. then return m[i, j]
3. if i = j
4. then m[i, j]  0
5. else for k  i to j – 1
6. do q  LOOKUP-CHAIN(p, i, k) +
LOOKUP-CHAIN(p, k+1, j) + pi-1pkpj
7. if q < m[i, j]
8. then m[i, j]  q
9. return m[i, j] 49
Dynamic Progamming vs. Memoization

• Advantages of dynamic programming vs.

memoized algorithms
– No overhead for recursion, less overhead for
maintaining the table
– The regular pattern of table accesses may be used to
reduce time or space requirements
• Advantages of memoized algorithms vs.
dynamic programming
– Some subproblems do not need to be solved

50
Elements of Dynamic Programming
• Optimal Substructure
– An optimal solution to a problem contains within it an
optimal solution to subproblems
– Optimal solution to the entire problem is build in a
bottom-up manner from optimal solutions to
subproblems
• Overlapping Subproblems
– If a recursive algorithm revisits the same subproblems
over and over  the problem has overlapping
subproblems
52
 Parameters of Optimal Substructure

• How many subproblems are used in an optimal

solution for the original problem
– Assembly line: One subproblem (the line that gives best time)
– Matrix multiplication: Two subproblems (subproducts Ai..k, Ak+1..j)

• How many choices we have in determining

which subproblems to use in an optimal solution
– Assembly line: Two choices (line 1 or line 2)
– Matrix multiplication: j - i choices for k (splitting the product)

53
 Parameters of Optimal Substructure
• Intuitively, the running time of a dynamic
programming algorithm depends on two factors:
– Number of subproblems overall
– How many choices we look at for each subproblem
• Assembly line
– (n) subproblems (n stations) (n) overall
– 2 choices for each subproblem
• Matrix multiplication:
– (n2) subproblems (1  i  j  n)
(n3) overall
– At most n-1 choices
54
 Longest Common Subsequence
• Given two sequences
X = x1, x2, …, xm
Y = y1, y2, …, yn
find a maximum length common subsequence
(LCS) of X and Y
• E.g.:
X = A, B, C, B, D, A, B
• Subsequences of X:
– A subset of elements in the sequence taken in order
A, B, D, B, C, D, B, etc.
55
 Example

X = A, B, C, B, D, A, B X = A, B, C, B, D, A, B

Y = B, D, C, A, B, A Y = B, D, C, A, B, A

• B, C, B, A and B, D, A, B are longest common

subsequences of X and Y (length = 4)

• B, C, A, however is not a LCS of X and Y

56
 Brute-Force Solution
• For every subsequence of X, check whether it’s
a subsequence of Y

• There are 2m subsequences of X to check

• Each subsequence takes (n) time to check

– scan Y for first letter, from there scan for second, and
so on

• Running time: (n2m)

57
 Making the choice
X = A, B, D, E
Y = Z, B, E
• Choice: include one element into the common
sequence (E) and solve the resulting
subproblem
X = A, B, D, G
Y = Z, B, D
• Choice: exclude an element from a string and
solve the resulting subproblem
58
 Notations
• Given a sequence X = x1, x2, …, xm we define
the i-th prefix of X, for i = 0, 1, 2, …, m

Xi = x1, x2, …, xi

• c[i, j] = the length of a LCS of the sequences

Xi = x1, x2, …, xi and Yj = y1, y2, …, yj

59
 A Recursive Solution
Case 1: xi = yj
e.g.: Xi = A, B, D, E
Yj = Z, B, E

c[i, j] = c[i - 1, j - 1] + 1

– Append xi = yj to the LCS of Xi-1 and Yj-1

– Must find a LCS of Xi-1 and Yj-1  optimal solution to a
problem includes optimal solutions to subproblems

60
 A Recursive Solution
Case 2: xi  yj
e.g.: Xi = A, B, D, G
Yj = Z, B, D
c[i, j] = max { c[i - 1, j], c[i, j-1] }
– Must solve two problems
• find a LCS of Xi-1 and Yj: Xi-1 = A, B, D and Yj = Z, B, D
• find a LCS of Xi and Yj-1: Xi = A, B, D, G and Yj = Z, B

• Optimal solution to a problem includes optimal

solutions to subproblems
61
 Overlapping Subproblems

• To find a LCS of X and Y

– we may need to find the LCS between X and Yn-1 and

that of Xm-1 and Y

– Both the above subproblems has the subproblem of

finding the LCS of Xm-1 and Yn-1

• Subproblems share subsubproblems

62
3. Computing the Length of the LCS
0 if i = 0 or j = 0
c[i, j] = c[i-1, j-1] + 1 if xi = yj
max(c[i, j-1], c[i-1, j]) if xi  yj
0 1 2 n
yj: y1 y2 yn
0 xi 0 0 0 0 0 0
1 x1 0 first
2 x2 0 second
i
0
0
m xm 0
j
63
 Additional Information
0 if i,j = 0 A matrix b[i, j]:
c[i, j] = c[i-1, j-1] + 1 if xi = yj • For a subproblem [i, j] it
max(c[i, j-1], c[i-1, j]) if xi  yj tells us what choice was
made to obtain the
0 1 2 3 n
b & c: yj: A C D F optimal value
0 xi 0 0 0 0 0 0 • If xi = yj
1 A 0 b[i, j] = “ ”
2 B 0 • Else, if
c[i-1,j]
i c[i - 1, j] ≥ c[i, j-1]
3 C 0
b[i, j] = “  ”
c[i,j-1]
0
else
m D 0
b[i, j] = “  ”
j
64
 LCS-LENGTH(X, Y, m, n)
1. for i ← 1 to m
2. do c[i, 0] ← 0 The length of the LCS if one of the sequences
3. for j ← 0 to n is empty is zero
4. do c[0, j] ← 0
5. for i ← 1 to m
6. do for j ← 1 to n
7. do if xi = yj
8. then c[i, j] ← c[i - 1, j - 1] + 1 Case 1: xi = yj
9. b[i, j ] ← “ ”
10. else if c[i - 1, j] ≥ c[i, j - 1]
11. then c[i, j] ← c[i - 1, j]
12. b[i, j] ← “↑” Case 2: xi  yj
13. else c[i, j] ← c[i, j - 1]
14. b[i, j] ← “←”
15. return c and b
Running time: (mn)
65
 Example
0 if i = 0 or j = 0
X = A, B, C, B, D, A
c[i, j] = c[i-1, j-1] + 1 if xi = yj
Y = B, D, C, A, B, A
max(c[i, j-1], c[i-1, j]) if xi  yj
0 1 2 3 4 5 6
If xi = yj yj B D C A B A
b[i, j] = “ ” 0 xi 0 0 0 0 0 0 0
1 A   
Else if 0 0 0 0 1 1 1
c[i - 1, j] ≥ c[i, j-1] 2 B 0 1 1 1

1 2 2
b[i, j] = “  ” 3 C 0

1

1 2 2

2

2
else 4 B   
0 1 1 2 2 3 3
b[i, j] = “  ” 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
66
 4. Constructing a LCS
• Start at b[m, n] and follow the arrows
• When we encounter a “ “ in b[i, j]  xi = yj is an element
of the LCS
0 1 2 3 4 5 6
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
67
 PRINT-LCS(b, X, i, j)
1. if i = 0 or j = 0 Running time: (m + n)
2. then return
3. if b[i, j] = “ ”
4. then PRINT-LCS(b, X, i - 1, j - 1)
5. print xi
6. elseif b[i, j] = “↑”
7. then PRINT-LCS(b, X, i - 1, j)
8. else PRINT-LCS(b, X, i, j - 1)

Initial call: PRINT-LCS(b, X, length[X], length[Y])

68
 Improving the Code
• What can we say about how each entry c[i, j] is
computed?
– It depends only on c[i -1, j - 1], c[i - 1, j], and
c[i, j - 1]
– Eliminate table b and compute in O(1) which of the
three values was used to compute c[i, j]
– We save (mn) space from table b
– However, we do not asymptotically decrease the
auxiliary space requirements: still need table c

69
 Improving the Code
• If we only need the length of the LCS
– LCS-LENGTH works only on two rows of c at a time

• The row being computed and the previous row

– We can reduce the asymptotic space requirements by

storing only these two rows

70
 Introduction to trees
and graphs
By
Dr. Swagata Mandal
Electronics and Communication Department
Jalpaiguri Government Engineering College
Trees
 What is a tree?
• Trees are structures used to represent
hierarchical relationship
• Each tree consists of nodes and edges
• Each node represents an object
• Each edge represents the relationship between
two nodes.

node
edge

3
 Some applications of Trees
Organization Chart Expression Tree

President
+
VP VP
Personnel Marketing * 5

3 2
Director Director
Customer Sales
Relation

4
 Terminology I
• For any two nodes u and v, if there is an edge
pointing from u to v, u is called the parent of v
while v is called the child of u. Such edge is
denoted as (u, v).
• In a tree, there is exactly one node without
parent, which is called the root. The nodes
without children are called leaves.
root

u
u: parent of v
v: child of u
v
leaves 5
 Terminology II
• In a tree, the nodes without children are
called leaves. Otherwise, they are called
internal nodes.

internal nodes

leaves
6
 Terminology III
• If two nodes have the same parent, they are
siblings.
• A node u is an ancestor of v if u is parent of v or
parent of parent of v or …
• A node v is a descendent of u if v is child of v or
child of child of v or …
u

v and w are siblings

u and v are ancestors of x v w
v and x are descendents of u
x
7
 Terminology IV
• A subtree is any node together with all its
descendants.

T
A subtree of T
v v

8
 Terminology V
• Level of a node n: number of nodes on the path from
root to node n
• Height of a tree: maximum level among all of its node

Level 1

Level 2
height=4
n Level 3

Level 4

9
 Binary Tree
• Binary Tree: Tree in which every node has at
most 2 children
• Left child of u: the child on the left of u
• Right child of u: the child on the right of u

x: left child of u
u v y: right child of u
w: right child of v
x y z: left child of w
w
z
10
 Full binary tree
• If T is empty, T is a full binary tree of height 0.
• If T is not empty and of height h >0, T is a full
binary tree if both subtrees of the root of T are
full binary trees of height h-1.

Full binary tree

of height 3

11
 Property of binary tree (I)
• A full binary tree of height h has 2h-1
nodes
No. of nodes = 20 + 21 + … + 2(h-1)
= 2h – 1
Level 1: 20 nodes

Level 2: 21 nodes

Level 3: 22 nodes
12
 Property of binary tree (II)
• Consider a binary tree T of height h. The
number of nodes of T  2h-1

Reason: you cannot have more nodes than

a full binary tree of height h.

13
 Property of binary tree (III)
• The minimum height of a binary tree with n
nodes is log(n+1)

By property (II), n  2h-1

Thus, 2h  n+1
That is, h  log2 (n+1)

14
Representation of a Binary Tree
• An array-based representation
• A reference-based representation

15
 An array-based representation
nodeNum item leftChild rightChild
–1: empty tree root
0 d 1 2 0
1 b 3 4
2 f 5 -1
3 a -1 -1
d 4 c -1 -1
5 e -1 -1

b f 6 ? ? ? free
7 ? ? ? 6
8 ? ? ?
a c e 9 ? ? ?
... ..... ..... ....
16
 Reference Based
Representation
NULL: empty tree left element right

You can code this with a

class of three fields:
Object element;
BinaryNode left;
BinaryNode right; d d

b f
b f
a c
a c
17
 Tree Traversal
• Given a binary tree, we may like to do
some operations on all nodes in a binary
tree. For example, we may want to double
the value in every node in a binary tree.
• To do this, we need a traversal algorithm
which visits every node in the binary tree.

18
 Ways to traverse a tree
• There are three main ways to traverse a tree:
– Pre-order:
• (1) visit node, (2) recursively visit left subtree, (3) recursively
visit right subtree
– In-order:
• (1) recursively visit left subtree, (2) visit node, (3) recursively
right subtree
– Post-order:
• (1) recursively visit left subtree, (2) recursively visit right
subtree, (3) visit node
– Level-order:
• Traverse the nodes level by level
• In different situations, we use different traversal
algorithm.
19
Examples for expression tree
• By pre-order, (prefix)
+*23/84
• By in-order, (infix) +
2*3+8/4
• By post-order, (postfix) * /
23*84/+ 2 3 8 4
• By level-order,
+*/2384
• Note 1: Infix is what we read!
• Note 2: Postfix expression can be computed
efficiently using stack
20
Graphs

21
 What is a graph?
• Graphs represent the relationships among data
items
• A graph G consists of
– a set V of nodes (vertices)
– a set E of edges: each edge connects two nodes
• Each node represents an item
• Each edge represents the relationship between
two items
node

edge
22
 Examples of graphs
Molecular Structure Computer Network
H Server 1 Terminal 1

H C H
Terminal 2
H Server 2

Other examples: electrical and communication networks,

airline routes, flow chart, graphs for planning projects

23
 Formal Definition of graph
• The set of nodes is denoted as V
• For any nodes u and v, if u and v are
connected by an edge, such edge is denoted
as (u, v) v
(u, v)

u
• The set of edges is denoted as E
• A graph G is defined as a pair (V, E)
24
 Adjacent
• Two nodes u and v are said to be adjacent
if (u, v)  E

v
(u, v)
u
w
u and v are adjacent
v and w are not adjacent

25
 Path and simple path
• A path from v1 to vk is a sequence of
nodes v1, v2, …, vk that are connected by
edges (v1, v2), (v2, v3), …, (vk-1, vk)
• A path is called a simple path if every
node appears at most once.
v2 v
v1 3

- v2, v3, v4, v2, v1 is a path

- v2, v3, v4, v5 is a path, also v4 v5
it is a simple path
26
 Cycle and simple cycle
• A cycle is a path that begins and ends at
the same node
• A simple cycle is a cycle if every node
appears at most once, except for the first
and the last nodes
v2
v1 v3
- v2, v3, v4, v5 , v3, v2 is a cycle
- v2, v3, v4, v2 is a cycle, it is v5
also a simple cycle
v4
27
 Connected graph
• A graph G is connected if there exists path
between every pair of distinct nodes;
otherwise, it is disconnected
v2
v1 v3

v4 v5
This is a connected graph because there exists path
between every pair of nodes
28
Example of disconnected graph

v1 v3 v7 v8
v2
v4 v5
v6 v9

This is a disconnected graph because there does not

exist path between some pair of nodes, says, v1 and v7

29
 Connected component
• If a graph is disconnect, it can be partitioned into
a number of graphs such that each of them is
connected. Each such graph is called a
connected component.

v2 v7 v8
v1 v3

v4 v5
v6 v9
30
 Complete graph
• A graph is complete if each pair of distinct
nodes has an edge

Complete graph Complete graph

with 3 nodes with 4 nodes

31
 Subgraph
• A subgraph of a graph G =(V, E) is a
graph H = (U, F) such that U  V and
F  E.
v2 v2
v1 v3 v3

v4 v5 v4 v5

G H
32
 Weighted graph
• If each edge in G is assigned a weight, it is
called a weighted graph

Chicago 1000 New York

3500
2000

Houston

33
 Directed graph (digraph)
• All previous graphs are undirected graph
• If each edge in E has a direction, it is called a directed
edge
• A directed graph is a graph where every edges is a
directed edge
Chicago 1000 New York

Directed edge
2000 3500

Houston
34
 More on directed graph
x y

• If (x, y) is a directed edge, we say

– y is adjacent to x
– y is successor of x
– x is predecessor of y
• In a directed graph, directed path, directed
cycle can be defined similarly

35
 Multigraph
• A graph cannot have duplicate edges.
• Multigraph allows multiple edges and self
edge (or loop).

Self edge Multiple edge

36
 Property of graph
• A undirected graph that is connected and
has no cycle is a tree.
• A tree with n nodes have exactly n-1
edges.
• A connected undirected graph with n
nodes must have at least n-1 edges.

37
 Implementing Graph
• Adjacency matrix
– Represent a graph using a two-dimensional
array
• Adjacency list
– Represent a graph using n linked lists where
n is the number of vertices

38
Adjacency matrix for directed graph
Matrix[i][j] = 1 if (vi, vj)E 1 2 3 4 5
0 if (vi, vj)E
v1 v2 v3 v4 v5

v2 1 v1 0 1 0 0 0
v1 v3 2 v 0 0 0 1 0
2

3 v3 0 1 0 1 0
v4 v5 4 v4 0 0 0 0 0
5 v5 0 0 1 1 0
G
39
 Adjacency matrix for weighted
undirected graph
Matrix[i][j] = w(vi, vj) if (vi, vj)E or (vj, vi)E
∞ otherwise
1 2 3 4 5
v2 v1 v2 v3 v4 v5
v1 2 v3
5 1 v1 ∞ 5 ∞ ∞ ∞
4 3 7 2 v2 5 ∞ 2 4 ∞
v4
8 v5 3 v3 0 2 ∞ 3 7
4 v4 ∞ 4 3 ∞ 8
G
5 v5 ∞ ∞ 7 8 ∞
40
 Adjacency list for directed graph

1 v1  v2
v2 2 v2  v4
v1 v3
3 v3  v2  v4
4 v4
v4 v5
5 v5  v3  v4
G

41
 Adjacency list for weighted
undirected graph

v2
v1 2 v3 1 v1  v2(5)
5
4 2 v2  v1(5)  v3(2)  v4(4)
3 7
3 v3  v2(2)  v4(3)  v5(7)
v4
8 v5 4 v4  v2(4)  v3(3)  v5(8)
5 v5  v3(7)  v4(8)
G

42
 Pros and Cons
• Adjacency matrix
– Allows us to determine whether there is an
edge from node i to node j in O(1) time
• Adjacency list
– Allows us to find all nodes adjacent to a given
node j efficiently
– If the graph is sparse, adjacency list requires
less space

43
Thank You

44
 Elementary Graph Algorithms
A graph G having V no of vertices and E no. of edges can be denoted as G(V,E) and can be
represented as a collection of adjacency lists or as an adjacency matrix.

Fig1: Two representations of an undirected graph. (a) An undirected graph G with 5 vertices and 7
edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.

Fig 2: Two representations of a directed graph. (a) A directed graph G with 6 vertices and 8 edges. (b)
An adjacency-list representation of G. (c) The adjacency-matrix representation of G.

The adjacency-list representation of a graph G = (V,E) consists of an array Adj of | | lists, one for
each vertex in V . For each , the adjacency list [ ] contains all the vertices such that there
is an edge . That is, [ ] consists of all the vertices adjacent to u in G. Since the
adjacency lists represent the edges of a graph, in pseudocode we treat the array Adj as an attribute of
the graph, just as we treat the edge set E. In pseudocode, therefore, we will see notation such as
[ ]. Figure 1(b) is an adjacency-list representation of the undirected graph in Figure 1(a).
Similarly, Figure 2(b) is an adjacency-list representation of the directed graph in Figure 2(a).

If G is a directed graph, the sum of the lengths of all the adjacency lists is | |, since an edge of the
form (u,v) is represented by having v appear in [ ]. If G is an undirected graph, the sum of the
lengths of all the adjacency lists is 2| |, since if (u,v) is an undirected edge, then u appears in v’s
adjacency list and vice versa. For both directed and undirected graphs, the adjacency-list
representation has the desirable property that the amount of memory it requires is .

We can readily adapt adjacency lists to represent weighted graphs, that is, graphs for which each edge
has an associated weight, typically given by a weight function . For example, let G = (V, E)
be a weighted graph with weight function w. We simply store the weight w(u,v) of the edge
with vertex v in u’s adjacency list. The adjacency-list representation is quite robust in that we can
modify it to support many other graph variants.
For the adjacency-matrix representation of a graph G = (V,E), we assume that the vertices are
numbered | | in some arbitrary manner. Then the adjacency-matrix representation of a graph G
consists of a | | | | matrix such that

Figures 1(c) and 2(c) are the adjacency matrices of the undirected and directed graphs in
Figures 1(a) and 2(a), respectively. The adjacency matrix of a graph requires ‚
memory, independent of the number of edges in the graph.

Since in an undirected graph, and represent the same edge, the adjacency matrix A
of an undirected graph is its own transpose: .

Like the adjacency-list representation of a graph, an adjacency matrix can represent a weighted graph.
For example, if G = (V,E) is a weighted graph with edge-weight function w, we can simply store the
weight of the edge as the entry in row u and column v of the adjacency matrix. If
an edge does not exist, we can store a NIL value as its corresponding matrix entry, though for many
problems it is convenient to use a value such as 0 or .

Breadth-First Search (BFS)

Given a graph G = (V,E) and a distinguished source vertex s, breadth-first search systematically
explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance
(smallest number of edges) from s to each reachable vertex. It also produces a “breadth-first tree” with
root s that contains all reachable vertices. For any vertex v reachable from s, the simple path in the
breadth-first tree from s to v corresponds to a “shortest path” from s to v in G, that is, a path
containing the smallest number of edges. The algorithm works on both directed and undirected
graphs.

Breadth-first search is so named because it expands the frontier between discovered and undiscovered
vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at
distance k from s before discovering any vertices at distance k+1.

To keep track of progress, BFS colours each vertex white, grey, or black. All vertices start out white
and may later become grey and then black. A vertex is discovered the first time it is encountered
during the search, at which time it becomes non-white i.e it will be marked with either grey or black.
If and vertex u is black, then vertex v is either grey or black; that is, all vertices adjacent to
black vertices have been discovered. Grey vertices may have some adjacent white vertices; they
represent the frontier between discovered and undiscovered vertices.

BFS constructs a breadth-first tree, initially containing only its root, which is the source vertex s.
Whenever the search discovers a white vertex v in the course of scanning the adjacency list of an
already discovered vertex u, the vertex v and the edge (u,v) are added to the tree. We say that u is the
predecessor or parent of v in the breadth-first tree. Since a vertex is discovered at most once, it has at
most one parent. Ancestor and descendant relationships in the breadth-first tree are defined relative to
the root s as usual: if u is on the simple path in the tree from the root s to vertex v, then u is an
ancestor of v and v is a descendant of u.
The breadth-first-search procedure BFS below assumes that the input graph G = (V,E) is represented
using adjacency lists. It attaches several additional attributes to each vertex in the graph. We store the
colour of each vertex in the attribute u:color and the predecessor of u in the attribute . If u
has no predecessor (for example, if u = s or u has not been discovered), then NIL. The attribute
u.d holds the distance from the source s to vertex u computed by the algorithm. The algorithm also
uses a first-in, first-out queue Q to manage the set of grey vertices. Pseudo code of BFS is given
below:

BFS (G,s)
1. for each vertex
2. [Link] = WHITE
3.
4. = NIL
5.
6.
7. NIL
8.
9. ENQUEUE(Q,s)
10. While
11. u = DEQUEUE(Q)
12. for each [ ]
13. if
14.
15. v.d = u.d + 1
16.
17. ENQUEUE(Q,v)
18. [Link] = BLACK

With the exception of the source vertex s, lines 1–4 paint every vertex white, set u.d to be infinity for
each vertex u, and set the parent of every vertex to be NIL. Line 5 paints s grey, since we consider it
to be discovered as the procedure begins. Line 6 initializes s.d to 0, and line 7 sets the predecessor of
the source to be NIL. Lines 8–9 initialize Q to the queue containing just the vertex s.

The while loop of lines 10–18 iterates as long as there remain grey vertices, which are discovered
vertices that have not yet had their adjacency lists fully examined.

Fig 3 shows the example of the breadth first search on the graph shown in Figure 3 (a). Here the
starting node is s and the node which is already traversed is marked with black colour and their
adjacent nodes are marked with grey colour. During the graph traversal, adjacent node of each
traversed node is pushed into the queue using the function ENQUEUE. When that nodes has traversed
they will be deleted from queue using DEQUEUE function.
Fig 3: The operation of BFS on an undirected graph. Tree edges are shown shaded as they are
produced by BFS. The value of u.d appears within each vertex u. The queue Q is shown at the
beginning of each iteration of the while loop of lines 10–18. Vertex distances appear below vertices in
the queue.

Shortest paths: At the beginning of this section, we claimed that breadth-first search finds the
distance to each reachable vertex in a graph G = (V,E) from a given source vertex . Define the
shortest-path distance from s to v as the minimum number of edges in any path from vertex s
to vertex v; if there is no path from s to v, then . We call a path of length from s to
v a shortest path from s to v.

Lemma 1: Let G = (V,E) be a directed or undirected graph, and suppose that BFS is run on G from a
given source vertex . Then upon termination, for each vertex , the value v.d computed by
BFS satisfies

Proof: Please consult book “Introduction to Algorithm” by Thomas H. Cormen, Charlese.E.

LEISERSON, Ronald L. Rivest and Clifford Stein. Page no. 598
 Assignment
Write a Python /C/C++ or any other language you know for finding BFS of the following graph
Breadth-first Search (Cont’d……………..)

Breadth-first Trees: The procedure BFS builds a breadth-first tree as it searches the
graph, as Figure 3 in my last note. The tree corresponds to the π attributes. More formally, for
a graph G = (V,E) with source s, we define the predecessor sub-graph of G as
where { } { } and { { }}.

The predecessor sub-graph is a breadth-first tree if consists of the vertices reachable

from s and, for al , the sub-graph contains a unique simple path from s to v that is
also a shortest path from s to v in G. A breadth-first tree is a connected tree and has
number of edges where | | | |

The following procedure prints out the vertices on a shortest path from s to v, as BFS has
already computed a breadth-first tree:

PRINT-PATH (G,s,v)

1. if
2. print s
3. elseif
4. print “no path from” s “to” v “exists”
5. else PRINT-PATH
6. print v.

Depth First Search

The strategy followed by depth-first search is, as its name implies, to search “deeper” in the
graph whenever possible. Depth-first search explores edges out of the most recently
discovered vertex v that still has unexplored edges leaving it. Once all of v’s edges have been
explored, the search “backtracks” to explore edges leaving the vertex from which v was
discovered. This process continues until we have discovered all the vertices that are reachable
from the original source vertex. If any undiscovered vertices remain, then depth-first search
selects one of them as a new source, and it repeats the search from that source. The algorithm
repeats this entire process until it has discovered every vertex.

DFS Algorithm:
A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited
list to the top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

Example:
Step1: Initialize the Stack

Step2 : Mark S as visited and put it onto the stack. Explore any unvisited adjacent node from
S. We have three nodes and we can pick any of them. For this example, we shall take the
node in an alphabetical order.

Step 3: Mark A as visited and put it onto the stack. Explore any unvisited adjacent node from
A. Both S and D are adjacent to A but we are concerned for unvisited nodes only.
Step 4: Visit D and mark it as visited and put onto the stack. Here, we have B and C nodes,
which are adjacent to D and both are unvisited. However, we shall again choose in an
alphabetical order.

Step 5: We choose B, mark it as visited and put onto the stack. Here B does not have any
unvisited adjacent node. So, we pop B from the stack.

Step 6: We check the stack top for return to the previous node and check if it has any
unvisited nodes. Here, we find D to be on the top of the stack.

Step 7: Only unvisited adjacent node is from D is C now. So we visit C, mark it as visited and
put it onto the stack.
As C does not have any unvisited adjacent node so we keep popping the stack until we find a
node that has an unvisited adjacent node. In this case, there's none and we keep popping until
the stack is empty.

So output of DFS is B,C,D,A,S.

DFS pseudocode (recursive implementation)

The pseudocode for DFS is shown below. In the init() function, notice that we run the DFS
function on every node. This is because the graph might have two different disconnected
parts so to make sure that we cover every vertex, we can also run the DFS algorithm on every
node.

DFS(G, u)
[Link] = true
for each v [Link][u]
if [Link] == false
DFS(G,v)

init() {
For each u G
[Link] = false
For each u G
DFS(G, u)
}

Output of a depth-first search:

A convenient description of a depth-first search of a graph is in terms of a spanning tree of
the vertices reached during the search. Based on this spanning tree, the edges of the original
graph can be divided into three classes: forward edges, which point from a node of the tree to
one of its descendants, back edges, which point from a node to one of its ancestors, and cross
edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree
itself, are classified separately from forward edges. If the original graph is undirected then all
of its edges are tree edges or back edges.
Vertex orderings:
It is also possible to use depth-first search to linearly order the vertices of a graph or tree.
There are four possible ways of doing this:

 A Preordering is a list of the vertices in the order that they were first visited by the
depth-first search algorithm. This is a compact and natural way of describing the
progress of the search. A preordering of an expression tree is the expression in Polish
notation.
 A Postordering is a list of the vertices in the order that they were last visited by the
algorithm. A postordering of an expression tree is the expression in reverse Polish
notation.
 A Reverse Preordering is the reverse of a preordering, i.e. a list of the vertices in the
opposite order of their first visit. Reverse preordering is not the same as postordering.
 A Reverse Postordering is the reverse of a postordering, i.e. a list of the vertices in
the opposite order of their last visit. Reverse postordering is not the same as
preordering.

In the above example when searching the directed graph below beginning at node A, the
sequence of traversals is either A B D B A C A or A C D C A B A (choosing to first visit B
or C from A is up to the algorithm). Note that repeat visits in the form of backtracking to a
node, to check if it has still unvisited neighbours, are included here (even if it is found to have
none). Thus the possible preorderings are A B D C and A C D B, while the possible
postorderings are D B C A and D C B A, and the possible reverse postorderings are A C B D
and A B C D.

Assignment
Write a C/Python or any other language you know for depth first search of the following
graph taking 4 as the starting node? Also find the pre-ordering and post-ordering output for
DFS traversal of the following graph taking 2 as starting node.

1 5

2 7
4

3 8

10 9
 Topological Sorting
A topological sort of a Directed Acyclic Graph (DAG) G= (V,E) is a linear ordering of all its
vertices such that if G contains an edge (u, v) then u appears before v in the ordering. (If the
graph contains a cycle, then no linear ordering is possible.) We can view a topological sort of
a graph as an ordering of its vertices along a horizontal line so that all directed edges go from
left to right.

Properties of Topological Sorting:

a) Graph should be directed and should not contain any cycle

b) Every DAG should have at least one topological sorted output
c) Any DAG may have more than one topological sorted output

Example:
2 3

4 5

Step1 : First calculate in-degree of each vertex i.e number of edges entered into a node.

(1)
2 3 (2)
(0)

4 5

(2) (1)
Step 2: Eliminate node have in-degree value ‘0’ and associated edges. Update in-degree value
of each node accordingly and print eliminated node.

2 3 (2)
(0)

Output: 1

4 5

(1) (1)
Step 3: Perform same operation on node 2
3 (1)

Output: 1,2

4 5

(0) (1)
Step 4: Perform same operation on node 4

3 (0)
Output: 1,2,4

5 (0)

Step 5: Now we can choose first node 3 and then node 5. Then output will be 1,2,4,3,5.
Otherwise we can choose node 5 first and then node 3. In this case output will be 1,2,4,5,3.

Now we will check if we select a directed graph which has cycle within it then it cannot
perform the topological sorting.

Example:
2 3

4 5

Step1: As in the previous case, calculate in-degree of each node in the graph.

(2)
2 3 (0)
(1)

4 5

(1) (1)
Step2: Eliminate node 3 and associated edge. Update in-degree value of node 2.

(1)
2
(1)

4 5

(1) (1)
Now in-degree value of each node is same i.e ‘1’ and no one have in-degree value 0. Hence,
we cannot proceed further.

Algorithm of Topological Sorting

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S

if graph has edges then

return error (graph has at least one cycle)
else
return L (a topologically sorted order)

Assignment: Perform Topological Sorting on the following graph

 Strongly Connected Component
A directed graph is called strongly connected if there is a path in each direction between each
pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the
second, and another path exists from the second vertex to the first. In a directed graph G(V,E)
that may not itself be strongly connected, a pair of vertices u and v are said to be strongly
connected to each other if there is a path in each direction between them.

1 2

4 3

Fig 1: Strongly Connected Graph

As all four nodes in Fig 1 can be reached from any other nodes they are called strongly
connected Graph.

A strongly connected component (SCC) of a directed graph is a maximal strongly connected

sub-graph. For example, there are 3 SCCs in the following graph: 0-1-2, 3, 4

1 0 3

2 4

We will use Kosaraju’s Algorithm to compute SCC in a directed graph.

Basic Idea of Kosaraju’s Algorithm:

1) Compute Depth First Search on a graph G (DFS(G)) to compute finish time for each
vertex
2) Compute transpose of a graph G which is represented as
3) Call DFS( ) on vertices in decreasing order of their finish times.
4) Output: Vertices as separate SCC’s

Compute the transpose of a graph: Reverse the direction of edge in the graph keeping the
vertices as it is
 1 2 1 2

4 3 4 3

Fig 2(a): Graph G (V,E) Fig 2(b): Transpose of the graph G(V,E): GT(V,E)

Kosaraju’s Algorithm:
Step 1: Create an empty stack ‘S’

Step 2: Do DFS traversal of the graph. In DFS traversal, after calling recursive DFS for
adjacent vertices of a vertex, push the vertex to stack.

Step 3: Reverse directions of all arcs to obtain the transpose graph.

Step 4: One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’.
Take v as source and do DFS call on v. The DFS starting from v prints strongly connected
component of v.

Example of Kosaraju’s Algorithm:

Find the SCC in the following graph

0 3 5 6 7

1 2 4 8

Step 1: Source vertex is ‘0’. Create an empty stack ‘S’.

Step 2: Start the DFS traversal from vertex ‘0’ and write start and stop time in each node
(7,10) (8,9)
(4,5) (15,18)
(1,14) 0 3 5 6 7

1 2 4 (6,11) 8 (16,17)
(2,13)
(3,12)
Start from node ‘0’ at t=1 and it has unvisited neighbourer. Go to node ‘1’ at t= 2 and it has
also unvisited neighbourer. Similarly go to node 2 and 3 at t = 3 and t = 4 respectively. As
neighbour node of 3 is already visited at t = 5, travel to node 3 will be finished and 3 will be
added to stack S.

S ={3,}

Now come back to node 2 which has still unvisited neighbour which is ‘4’. Visit vertex ‘4’ at
t = 6. Visit neighbour of node 4 i.e node 5 at t = 7. Similarly visit neighbour of node 5 i.e
node 6 at t =8. As node 6 has no neighbourer to visit, stop visit at node 6 and node 6 to stack
S at node t = 9.

S ={3,6}

Similarly, stop visit node 5 at t = 10, node 4 at t = 11 and add to the stack.

S ={3,6,5,4}

Obeying the same rule stop visit at node 2,1 and 0 at t= 12, t= 13 and t = 14 and add to the
stack S

S ={3,6,5,4,2,1,0}

As still some vertices are visited DFS will continue. Pick node 7 starts visiting at t = 15, and
it has neighbourer node 8 which will be visited at t = 16. As node 8 has no neighbourer to
visit, stop visit at t= 17 and add node 8 to stack S. Go back to node 7 and add it to stack at t =
18 as there is no neighbourer to visit. Contain of stack S will be

S ={3,6,5,4,2,1,0,8,7}

Step 3: Transpose the graph to obtain GT

0 3 5 6 7

1 2 4 8

Step 4: Pop first element of the stack i.e 7. As vertex 7 has no neighbour node in GT to visit
so 7 itself form a SCC. Contain of the S will be S={3,6,5,4,2,1,0,8}

Pop 8 from the stack. As the node 8 has no unvisited neighbourer in GT, it will alone form a
SCC. Contain of the S will be S={3,6,5,4,2,1,0}
Next pop 0 from the stack. As from node 0 we can visit 3,2,1 using DFS in GT. So 0,3,2,1
will form SCC. So when we pop 1 and 2 from the stack it will not be considered as they are
already visited. Now content of S will be S = {3,6,5,4}.

Next pop 4 from stack S. Visit vertices 6 and 5 as neighbour node of 4 using DFS in GT. So
4,6,5 will form a SCC. So when we pop 5 and6 from the stack it will not be considered as
they are already visited. Now content of S will be S = {3}.

Next we will pop 3 but it will not be considered as it is already visited. As stack is already
empty we will reach at the terminating condition.

So finally we will get four SCC from graph G. They are {7},{8},{0,3,2,1} and {4,6,5}. It can
be represented as follows

0,3,2,1 4,6,5 8
7

Overall time complexity of the above algorithm is O(V+E)

Assignment
Find the SCC in the following directed graph

H I
A C E

B D F G J

K
 Minimum Spanning Tree
What is a Spanning Tree?

Given an undirected and connected graph G= (V,E), a spanning tree of the graph is a tree that
spans (that is, it includes every vertex of ) and is a sub-graph of G (every edge in the tree
belongs to G). Spanning tree should be acyclic i.e it should not contain any cycle.

What is a Minimum Spanning Tree?

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can
be many spanning trees. Minimum spanning tree is the spanning tree where the cost is
minimum among all the spanning trees. There also can be many minimum spanning trees.

Minimum spanning tree has direct application in the design of networks. It is used in
algorithms approximating the travelling salesman problem, multi-terminal minimum cut
problem and minimum-cost weighted perfect matching. Other practical applications are:

1. Cluster Analysis
2. Handwriting recognition
3. Image segmentation
4. Electronic circuit design and automation

In the graph (G) nodes marked with yellow have more than one spanning tree as shown by
the graph (G’) with blue nodes. If G’ be a spanning tree and have vertices V’ and edges E’
then V’= V, and . Out of all the spanning tree the tree whose weighted
sum of all the edges is minimum will be minimum will be selected as minimum spanning
tree. Here the summation of the weight of all edges is minimum i.e 7 in the second spanning
tree so it will be selected as minimum spanning tree.

There are two famous algorithms for finding the Minimum Spanning Tree:

Kruskal’s Algorithm
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing
spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an
edge which has least weight and adds it to the growing spanning tree.

Algorithm Steps:

 Sort the graph edges with respect to their weights.

 Start adding edges to the MST from the edge with the smallest weight until the edge
of the largest weight.
 Only add edges which doesn't form a cycle, edges which connect only disconnected
components.

So now the question is how to check if two vertices are connected or not?

This could be done using DFS which starts from the first vertex, then check if the second
vertex is visited or not. But DFS will make time complexity large as it has an order of
where is the number of vertices, is the number of edges. So the best solution is
"Disjoint Sets".

Disjoint sets are sets whose intersection is the empty set so it means that they don't have any
element in common.

Fig 1: Example of Kruskal’s algorithm

Consider the example shown in Fig 1.

In Kruskal’s algorithm, at each iteration we will select the edge with the lowest weight. So,
we will start with the lowest weighted edge first i.e., the edges with weight 1. After that we
will select the second lowest weighted edge i.e., edge with weight 2. Notice these two edges
are totally disjoint. Now, the next edge will be the third lowest weighted edge i.e., edge with
weight 3, which connects the two disjoint pieces of the graph. Now, we are not allowed to
pick the edge with weight 4, that will create a cycle and we can’t have any cycles. So we will
select the fifth lowest weighted edge i.e., edge with weight 5. Now the other two edges will
create cycles so we will ignore them. In the end, we end up with a minimum spanning tree
with total cost 11 ( = 1 + 2 + 3 + 5).

Time Complexity: In Kruskal’s algorithm, most time consuming operation is sorting because
the total complexity of the Disjoint-Set operations will be , which is the overall
Time Complexity of the algorithm.

Prim’s Algorithm
Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s
Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's,
we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:

 Maintain two disjoint sets of vertices. One containing vertices that are in the growing
spanning tree and other that are not in the growing spanning tree.
 Select the cheapest vertex that is connected to the growing spanning tree and is not in
the growing spanning tree and add it into the growing spanning tree. This can be done
using Priority Queues. Insert the vertices, that are connected to growing spanning tree,
into the Priority Queue.
 Check for cycles. To do that, mark the nodes which have been already selected and
insert only those nodes in the Priority Queue that are not marked.

Consider the example shown in Fig 2.

In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and
mark it. In each iteration we will mark a new vertex that is adjacent to the one that we have
already marked. As a greedy algorithm, Prim’s algorithm will select the cheapest edge and
mark the vertex. So we will simply choose the edge with weight 1. In the next iteration we
have three options, edges with weight 2, 3 and 4. So, we will select the edge with weight 2
and mark the vertex. Now again we have three options, edges with weight 3, 4 and 5. But we
can’t choose edge with weight 3 as it is creating a cycle. So we will select the edge with
weight 4 and we end up with the minimum spanning tree of total cost 7 ( = 1 + 2 +4).
Fig 2: Example of Prim’s Algorithm
 Assignment
1. Given a weighted undirected graph. Find the sum of weights of edges of a Minimum
Spanning Tree.

Input:
Given two integers N and M. N represents the number of vertices in the graph. M
represents the number of edges between any two vertices.
Then M lines follow, each line has three space separated integers , , where
and represents an edge from a vertex to a vertex and respresents the weight
of that edge.

Output:
Print the summation of edges weights in the MST.

Constraints:
 Single-Source Shortest Paths
In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight
function mapping edges to real-valued weights. The weight w(p) of path
〈 〉 is the sum of the weights of its constituent edges:

( ) ∑ ( )

We define the shortest-path weight ( ) from u to v by

( ) { * ( ) +

A shortest path from vertex u to vertex v is then defined as any path p with weight ( )
( )

The breadth-first-search algorithm discussed in the previous lecture is a shortest-paths

algorithm that works on unweighted graphs, that is, graphs in which each edge has unit
weight.

Here, we will focus on the single-source shortest-paths problem: given a graph G = (V, E),
we want to find a shortest path from a given source vertex to each vertex .The
algorithm for the single-source problem can solve many other problems, including the
following variants.

Single-destination shortest-paths problem: Find a shortest path to a given destination vertex

t from each vertex v. By reversing the direction of each edge in the graph, we can reduce this
problem to a single-source problem.

Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and
v. If we solve the single-source problem with source vertex u, we can solve this problem also.
Moreover, all known algorithms for this problem have the same worst-case asymptotic
running time as the best single-source algorithms.

All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u
and v. Although we can solve this problem by running a singles ource algorithm once from
each vertex, we usually can solve it faster. Additionally, its structure is interesting in its own
right.

Lemma 1: (Sub-paths of shortest paths are shortest paths)

Given a weighted, directed graph G = (V,E) with weight function , let

〈 〉 be a shortest path from vertex to vertex and, for any i and j such that,
, let 〈 〉 be the subpath of p from vertex to vertex .
Then, is a shortest path from to .
Proof:

If we decompose path p into → → → then we have that ( ) ( )

( ) ( ) . Now, assume that there is a path from to with weight ( )

( ). Then, → → → is a path from to whose weight ( ) ( )

( ) is less than ( ), which contradicts the assumption that p is a shortest path from
to .

Negative-weight edges
Some instances of the single-source shortest-paths problem may include edges whose weights
are negative. If the graph G = (V,E) contains no negative weight cycles reachable from the
source s, then for all , the shortest-path weight ( ) remains well defined, even if it
has a negative value. If the graph contains a negative-weight cycle reachable from s,
however, shortest-path weights are not well defined. No path from s to a vertex on the cycle
can be a shortest path—we can always find a path with lower weight by following the
proposed “shortest” path and then traversing the negative-weight cycle. If there is a negative
weight cycle on some path from s to v, we define ( ) .

Figure 1: Negative edge weights in a directed graph

Figure 1 illustrates the effect of negative weights and negative-weight cycles on shortest-path
weights. Because there is only one path from s to a (the path 〈 〉), we have ( )
( ) . Similarly, there is only one path from s to b, and so ( ) ( )
( ) ( ) . There are infinitely many paths from s to c: 〈 〉 〈 〉
〈 〉 and so on. Because the cycle 〈 〉has weight ( ) , the
shortest path from s to c is 〈 〉, with weight ( ) ( ) . Similarly, the shortest
path from s to d is 〈 〉 with weight ( ) ( ) ( ) . Analogously,
there are infinitely many paths from s to e: 〈 〉 〈 〉 〈 〉 and so on.
Because the cycle 〈 〉 has weight ( ) , however, there is no shortest path
from s to e. By traversing the negative-weight cycle 〈 〉 arbitrarily many times, we can
find paths from s to e with arbitrarily large negative weights, and so ( ) . Similarly,
( ) Because g is reachable from f , we can also find paths with arbitrarily large
negative weights from s to g, and so ( ) . Vertices h, i, and j also form a negative-
weight cycle. They are not reachable from s, and so ( ) ( ) ( ) .

In some of the shortest path algorithm may consider negative weight edges and some may not
consider.

Bellman-Ford Algorithm
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general
case in which edge weights may be negative. Given a weighted, directed graph G = (V,E)
with source s and weight function , the Bellman-Ford algorithm returns a boolean
value indicating whether or not there is a negative-weight cycle that is reachable from the
source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no
such cycle, the algorithm produces the shortest paths and their weights.

Following are the detailed steps of Bellman-Ford algorithm.

Input: Graph and a source vertex src

Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then
shortest distances are not calculated, negative weight cycle is reported.

Step1: This step initializes distances from source to all vertices as infinite and distance to
source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src]
where src is source vertex.

Step2: This step calculates shortest distances. Do following |V|-1 times where |V| is the
number of vertices in given graph.

a) Do following for each edge u-v

b) If dist[v] > dist[u] + weight of edge uv, then update dist[v]
c) dist[v] = dist[u] + weight of edge uv

Step3: This step reports if there is a negative weight cycle in graph. Do following for each
edge u-v. If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight
cycle” The idea of step 3 is, step 2 guarantees shortest distances if graph doesn‟t contain
negative weight cycle. If we iterate through all edges one more time and get a shorter path for
any vertex, then there is a negative weight cycle.

Pseudocode:
function bellmanFord(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
distance[S] <- 0
for each vertex V in G
for each edge (U,V) in G
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
 previous[V] <- U

for each edge (U,V) in G

If distance[U] + edge_weight(U, V) < distance[V}
Error: Negative Cycle Exists

return distance[], previous[]

Example of Bellman-Ford algorithm

-1
2 5
6 3
-2
5
1 3 1 7

5 -2
3
4 6
-1

Here we will assume 1 as the source vertex and will find the shortest path to all other
vertices. Like all other dynamic programming problem it will also search all possible
solutions and choose the best solution.

Here number of vertices are 7 so we have to check the weight of each edges for 6 [Link]
each searching we have to the relaxation of each edges i.e If an edge is formed using the
vertices u and v and dist[v] > dist[u] + weight of edge uv, then update dist[v] = dist[u] +
weight of edge uv

Before starting first we have to find all the edges:

(1,2),(1,3),(1,4),(2,5),(3,2),(3,5),(4,3),(4,6),(5,7),(6,7)

Assign distance of source node „0‟ and all other nodes

Step 1:

1 2 3 4 5 6 7
0
Step 2: Update the weight of each node in the 1st round

1,2 1,3 1,4 2,5 3,2 3,5 4,3 4,6 5,7 6,7
1 0
2 6 3
3 5 3
4 5
5 5
6 4
7 8 7

Distance of each node from source node after 1st round

1 2 3 4 5 6 7
0

Step 3: Update the weight of each node in the 2nd round

1,2 1,3 1,4 2,5 3,2 3,5 4,3 4,6 5,7 6,7
1 0
2 3 1
3 3
4 5
5 2
6 4
7 5

Distance of each node after the 2nd round

1 2 3 4 5 6 7
0

Step 4: Update the weight of each node in the 3rd round

1,2 1,3 1,4 2,5 3,2 3,5 4,3 4,6 5,7 6,7
1 0
2 1
3 3
4 5
5 0
6 4
7 3
Distance of each node after the 3rd round

1 2 3 4 5 6 7
0

Step 5: Update the weight of each node in the 4th round

1,2 1,3 1,4 2,5 3,2 3,5 4,3 4,6 5,7 6,7
1 0
2 1
3 3
4 5
5 0
6 4
7 3

Distance of each node after the 4th round

1 2 3 4 5 6 7
0

We will stop the iteration either after 6th round or if there is no change in the distance of each
node from source node between two consecutive rounds. As there is no change in the
distances between source node to other nodes between in 3rd and 4th round we will stop in
this stage and it will be final output. Hence, final shortest distance of source node from other
nodes are

1 2 3 4 5 6 7
0

Time complexity of this algorithm O(| || |). If V= n and E = n, then time complexity
will be ( )

Now we will take another example

4
1 2

5
5 -10

4 3
3
In the above example number of vertices are 4 so we have to search each edges 3 times.
Edges are (3,2),(4,3),(1,4),(1,2),(2,4)

Assign distance of source node „0‟ and all other nodes

Step 1:

1 2 3 4
0

Step 2: Update the weight of each node in the 1st round

3,2 4,3 1,4 1,2 2,4

1 0
2 4
3
4 5

Distance of each node from source node after 1st round

1 2 3 4
0

Step 3: Update the weight of each node in the 2nd round

3,2 4,3 1,4 1,2 2,4

1 0
2 4
3 8
4 5

Distance of each node from source node after 2nd round

1 2 3 4
0 8

Step 3: Update the weight of each node in the 3rd round

3,2 4,3 1,4 1,2 2,4

1 0
2 -2
3 8
4 5 3

Distance of each node from source node after 3rd round

 1 2 3 4
0 -2 8

We have completed 3 iterations. But we proceed one more step

3,2 4,3 1,4 1,2 2,4

1 0
2 -2
3 6
4 3

Distance of each node from source node after 4th round

1 2 3 4
0 -2 6

But no vertices should be relaxed in this stage because we have already completed 3rd round.
Distances of all the node from source node should be stagnant in 3rd stage itself. It indicates
the presence of negative weight cycle.

In this way even after | | iterations if any changes occurred in the distance it indicates
the presence of negative cycle in the graph and hence, shortest distance cannot be calculated.
In this graph 2,4 and 3 form negative weight cycle with total weight -2, so we cannot
calculate shortest distance using Bellman-Ford algorithm.
In our last lecture we have discussed about Bellman-Ford Algorithm which is used to find
the shortest path from source to any other node even if negative cycle is present in the graph.
Now we will discuss an algorithm named as Dijkstra’s Algorithm which will find the
shortest path from source node to any other node in a graph only if weight of each edge is
positive i.e for each . It is basically a greedy method to find the
optimal solution.

Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, (SPF)) is an algorithm for
finding the shortest paths between nodes in a graph, which may represent, for example, road
networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published
three years later.

In order to understand this algorithm we have understand the relaxation method which I have
already discussed in the previous lecture. But here still I am discussing in brief.

X Y

The relaxation rule states if d[X]+cost(X,Y) < d[Y] then replace d[Y] with (d[X]+
cost(X,Y)). Here cost(X,Y) is the weight of the edge connected between node X and node Y.

7
2 4
2 1

2
1 6
1

4
5
3
3 5

Step 1: In the above graph we will choose node 1 as source node. The node which is directly
connected with source node distance between that node and source node will be replaced by
weight of the edge connected between them. Foe all other nodes replace this distance with .

2 3 4 5 6
Cost 2 4

Step 2: Choose the node with least cost as the next node i.e node 2 in our case and marked it
as travelled. Update cost of each node using relaxation method.
 2 3 4 5 6
Cost 2 3 9

Step 3: Node which is already travelled will not be travelled again. So our next node will be
3. Update the cost of the node 5 using relaxation technique (3 +3 < ) as it is directly
connected with 3

2 3 4 5 6
Cost 2 3 9 6

Step 4: Now we will go to node 5 and update the cost of node 4 and node 6

2 3 4 5 6
Cost 2 3 8 6 11

Step 5: As out of node 4 and 6 cost of node 4 is less we will travel to node 4 and update the
cost of node 6

2 3 4 5 6
Cost 2 3 8 6 9

Step 6: Only remaining vertex is 6 and from that vertex there is no path to go. Hence we will
stop here and final cost of each node is the shortest distance of each node from source node.

In order to calculate the time complexity of this algorithm we have to have to consider the
worst case scenario i.e from each node we need to search all other nodes (in case of fully
connected graph). So if there is n no. of vertices in a graph then worst case time complexity
will be O(n2).

3
1 2

5 -3

4 3
2
Now in the above graph we have to find the shortest path from source node 1 using Dijkstra’s
Algorithm. Here weight of one node is –ve as shown in the graph.

Step 1: Assign cost of each node connected with node 1

 2 3 4
Cost 3 5

Step 2: Though the cost of node 2 is low but there is no outgoing path. So we will go to node
4. But we will mark node 2 as travelled node

2 3 4
Cost 3 7 5

Step 3: Start from node 3 and check the cost of node 2. But it is found that it is okay so leave
it to 3.

2 3 4
Cost 3 7 5

So Dijkstra’s Algorithm gives the correct result even if there is negative edge. Now if we
modify the weight of the negative edge in the same graph

3
1 2

5 -6

4 3
2
Here step 1 and step 2 will remain same as the previous case. Only step 3 will be changed as
follows

2 3 4
Cost 3 7 5

Now when check for relaxation of node 2 from node 3 it will updated to 1 which cannot be
possible because node 2 is already travelled.

Hence if negative edges present in the graph Dijkstra’s Algorithm may not work. So we
cannot use this algorithm to find shortest path in the graph with negative edges.
 Pseudocode of Dijkstra’s Algorithm

1: function Dijkstra(Graph, source):

2: for each vertex v in Graph: // Initialization
// initial distance from source to vertex v is
3: dist[v] := infinity
set to infinite
// Previous node in optimal path from
4: previous[v] := undefined
source
5: dist[source] := 0 // Distance from source to source
// all nodes in the graph are unoptimized -
6: Q := the set of all nodes in Graph
thus are in Q
7: while Q is not empty: // main loop
8: u := node in Q with smallest dist[ ]
9: remove u from Q
// where v has not yet been removed from
10: for each neighbor v of u:
Q.
11: alt := dist[u] + dist_between(u, v)
12: if alt < dist[v] // Relax (u,v)
13: dist[v] := alt
14: previous[v] := u
15: return previous[ ]
 All Pair Shortest path algorithm
This algorithm is used to find shortest path between all the nodes in the graph. It works even
if the negative edge presents the graph. We can use either Bellman-Ford Algorithm (if
negative present in the graph) or Dijkstra’s Algorithm (if only positive edge present in the
graph) multiple times. But there is another algorithm known as Floyd-Warshall algorithm
that is used to find shortest path present between every pair of node in the graph.

Consider the graph shown below. We have to find the shortest path between every node in
the graph using Floyd-Warshall algorithm
8
1 2
3
2 7 2
5

4 3
1

First we will create a square matrix whose every entry is the weight of the edge connecting
between the nodes. The matrix is designated by A0 . The number written in red color in A0
indicates nodes in the graph. As there is no path from a particular node to that node itself, the
diagonal elements will be 0. If there is no direct connection from a node to another node entry
corresponding to that element will be . All other entry in the matrix will be the weight of
the edges connecting between the nodes

A0=

As we have four nodes or vertices in the graph we have to perform the following step four
times. During each step we have to calculate the distance of every of nodes through particular
nodes and update the entry of the matrix. As for example in step 1 we have to calculate
distance between each node or vertices through node 1

Step 1: Here we will calculate distance between each nodes or vertices through node 1. Here
we will keep the entry of first row and first column fixed and updated all other entries
according to the following rule:

If distance between two nodes through node 1 is less than the present value in the matrix
update it with that distance otherwise leave it.

As for example distance between node 2 to node 3 through node 1

 [ ] [ ] which is greater than present value of [ ] . Hence
keep as it is without modification.

On the other hand distance between node 2 to node 3 through node 1

[ ] [ ] [ ] which is less than the present value of [ ]

. Hence replace it with 15.

After first step content of the matrix will be

A1=

Step 2: Here we will calculate distance between each nodes or vertices through node 2. Hence
we will keep the entry of A1 2nd row and 2nd column fixed and updated all other entries in the
similar way. After 2nd step content of the matrix will be

A2=

Step 3: Here we will calculate distance between each nodes or vertices through node 3. Hence
we will keep the entry of A2 3rd row and 3rd column fixed and updated all other entries in the
similar way. After 3rd step content of the matrix will be

A3=

Step 4: Here we will calculate distance between each nodes or vertices through node 4. Hence
we will keep the entry of A3 4th row and 4th column fixed and updated all other entries in the
similar way. After 4th step content of the matrix will be

A4=

Now each entry in A4 indicates the shortest distance between each pair of the nodes in the
graph. Like shortest distance between node 2 and node 3 is 2.
In general we can write [ ] { [ ] [ ] [ ]}

Pseudocode of Floyd-Warshall algorithm

Input − The cost matrix of given Graph.

Output − Matrix to for shortest path between any vertex to any vertex.

Begin
for k := 0 to n, do
for i := 0 to n, do
for j := 0 to n, do
if cost[i,k] + cost[k,j] < cost[i,j], then
cost[i,j] := cost[i,k] + cost[k,j]
done
done
done
display the current cost matrix
End