ECS122A

Algorithm Design and Analysis

Fall 2025

1 / 278
Overview
I. Introduction and getting started
II. Characterizing running time
III. Linear and Divide-and-conquer recurrences
IV. Divide-and-conquer algorithms
V. Greedy algorithms
VI. Dynamic programming
VII. Graph algorithms
VIII. NP-completeness

Based on selected chapters from the textbook “Introduction to

Algorithms”, by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein,
Third Edition (2009) or Fourth Edition (2022), MIT Press.

2 / 278
I. Introduction and Getting Started

3 / 278
Introduction
I Algorithm is a tool for solving a well-specified computational problem
I An algorithm is a well-defined procedure for transforming some input
into a desired output.
I A poem by D. Berlinski in “Advent of the Algorithm”
In the logician’s voice:
an algorithm is
a finite procedure,
written in a fixed symbolic vocabulary
governed by precise instructions,
moving in discrete steps, 1, 2, 3, ...
whose execution requires no insight, cleverness,
intuition, intelligence, or perspicuity
and that sooner or later comes to an end.

4 / 278
Introduction
I Basic questions about an algorithm

1. Does it halt?
2. Is it correct?
3. Is it fast? (Can it be faster?)
4. How much memory does it use?
5. How does data communicate?

5 / 278
Getting started: Example 1
I Fibonacci numbers:

F0 = 0,
F1 = 1,
Fn = Fn−1 + Fn−2 for n≥2

I Fact:
Fibonacci numbers grow almost as fast as the power of 2:

Fn ≈ 20.694n

I Problem statement:
given n, computing the n-th Fibonacci number Fn

6 / 278
Getting started: Example 1
I Recursive algorithm (Algorithm 1) for computing Fn (top-down):

1. By definition, Fn = Fn−1 + Fn−2

2. Compute Fn−1 = Fn−2 + Fn−3 , Fn−2 = Fn−3 + Fn−4 , ...
3. Running time:
Let T (n) = number of operations to compute Fn , then

T (n) = T (n − 1) + T (n − 2) + 1
= O(2n ).

7 / 278
Getting started: Example 1
I Iterative algorithm (Algorithm 2) for computing Fn (bottom-up,
memoization):
1. Compute F0 , F1 , F2 , ...., until Fn
2. Running time:

T (n) = T (n − 1) + 1
=n−1

8 / 278
Getting started: Example 1
I Divide-and-conquer algorithm (Algorithm 3) for computing Fn :
1. Reformulation
    
Fn 0 1 Fn−1
=
Fn+1 1 1 Fn
     2  
0 1 0 1 Fn−2 0 1 Fn−2
= =
1 1 1 1 Fn−1 1 1 Fn−1
= ···
 n      
0 1 F0 F0 0
= ≡ Xn = Xn
1 1 F1 F1 1

2. Compute X n by divide-and-conquer
n n
Xn = X 2 · X 2

3. Running time
n
T (n) = T + const.
2
= O(lg n)

9 / 278
Getting started: Example 1
I Approximation algorithm (Algorithm 4) for computing Fn :

1. The solution of the linear recursion Fn = Fn−1 + Fn−2 is given by

 √ n  √ n
1 1+ 5 1 1− 5
Fn = √ −√
5 2 5 2

2. Running time for computing Fn approximately/inexactly

T (n) = const = O(1)

10 / 278
Getting started: Example 2
I Problem statement:
Input: a sequence of n numbers ha1 , a2 , . . . , an i
Output: a permutation (reordering) ha01 , a02 , . . . , a0n i of the
a-sequence such that a01 ≤ a02 ≤ · · · ≤ a0n
In short, sorting

11 / 278
Getting started: Example 2
Algorithm 1: Insertion sort
I Idea: incremental approach

12 / 278
Getting started: Example 2
Algorithm 1: Insertion sort
I Pseudocode
InsertionSort(A)
1 n = length(A)
2 for j = 2 to n
3 key = A[j]
4 // insert ‘‘key’’ into sorted array A[1...j-1]
5 i = j-1
6 while i > 0 and A[i] > key do
7 A[i+1] = A[i]
8 i = i-1
9 end while
10 A[i+1] = key
11 end for
12 return A

13 / 278
Getting started: Example 2
Analysis of Algorithm 1: Insertion sort
I Correctness:
argued by induction (“loop-invariant”)
I Complexity (running time):
Define
I T (n) = number of operations for sorting an array of length n,
I tj = number of while-loop executed for j
Then
n
X
T (n) = (1 + 1 + tj + 1)
j=2
n
X
= 3(n − 1) + tj
j=2

14 / 278
Getting started: Example 2
Analysis of Algorithm 1: Insertion sort, cont’d
Xn
I Complexity: T (n) = 3(n − 1) + tj
j=2
I best-case:

tj = 1
T (n) = 4(n − 1) = O(n)
I worst-case:

tj = j
n
X
T (n) = 3(n − 1) + j = O(n2 )
j=2

I average-case:
j
tj =
2
n
X j
T (n) = 3(n − 1) + = O(n2 )
j=2
2

15 / 278
Getting started: Example 2
Analysis of Algorithm 1: Insertion sort, cont’d
I Insertion sort is a “sort-in-place”, no extra memory necessary
I Importance of writing a good pseudocode: “expressing algorithm to
human”
I Homework problem: write a recurisve version of insertion sort.

16 / 278
Getting started: Example 2
Algorithm 2: Merge sort
I Idea: divide-and-conquer approach

17 / 278
Getting started: Example 2
Algorithm 2: Merge sort
I Pseudocode
MergeSort(A,p,r) // Merge-sort of array A[p..r]
1 if p < r then // check for base case
2 q = flooring( (p+r)/2 ) // divide
3 MergeSort(A,p,q) // conquer
4 MergeSort(A,q+1,r) // conquer
5 Merge(A,p,q,r) // combine/merge
6 end if

18 / 278
Getting started: Example 2
Algorithm 2: Merge sort
I Pseudocode, cont’d
Merge(A,p,q,r)
n1 = q-p+1; n2 = r-q
for i = 1 to n1 // create arrays L[1...n1+1] and R[1...n2+1]
L[i] = A[p+i-1]
end for
for j = 1 to n2
R[j] = A[q+j]
end for
L[n1+1] = infty; R[n2+1] = infty // mark the end of arrays L and R
i = 1; j = 1
for k = p to r // Merge arrays L and R to A
if L[i] <= R[j] then
A[k] = L[i]
i = i+1
else
A[k] = R[j]
j = j+1
end if
end for
19 / 278
Getting started: Example 2
Analysis of Algorithm 2: Merge sort
I Merge sort is a divide-and-conquer algorithm consisting of three steps:
divide → conquer → combine
I To sort the entire sequence A[1...n], we make the initial call
MergeSort(A,1,n)
I Complexity:
I Define:
T (n) = number of operations for sorting an array of length n,
I Then
n
T (n) = 1 + 2 · T +n−1
2
= O(n lg(n))

20 / 278
 II. Characterizing Running Times
Growth of Functions and Asymptotic Notations

21 / 278
Overview
I Study a way to describe the growth of functions in the limit –
asymptotic efficiency
I Focus on what’s important (leading factor) by abstracting lower-order
terms and constant factors
I Characterize running times of algorithms
I Provide a way to compare “sizes” of functions

O ≈ ≤
Ω ≈ ≥
Θ ≈ =

In addition,

o ≈ <
ω ≈ >

22 / 278
O-notation
3.1 Asymptotic notation

I Definition. g(n) is an asymptotic upper

bound for f (n), denoted by c2 g.n/ cg.n/

f (n) = O(g(n)) f .n/

f .n/
c1 g.n/
if there exist constants c and n0 such
that

0 ≤ f (n) ≤ c g(n) for n ≥ n0

n n
n0 n0
f .n/ D ‚.g.n// f .n/ D O.g.n//
(a) (b)

Figure 3.1 Graphic examples of the ‚, O, and  notations. In ea

is the minimum possible value; any greater value would also work.
tion to within constant factors. We write f .n/ D ‚.g.n// if there e
and c2 such that at and to the right of n0 , the value of f .n/ always li
inclusive. (b) O-notation gives an upper bound for a function to with
f .n/ D O.g.n// if there are positive constants n0 and c such that at a
of f .n/ always lies on or below cg.n/. (c) -notation gives a lower
a constant factor. We write f .n/ D .g.n// if there are positive cons
23 / 278
O-notation
I Example: Show that 2n + 10 = O(n2 ).

Proof: since
2n + 10 ≤ n2 for n ≥ 5,
therefore, 2n + 10 = O(n2 ) is true for c = 1 and n0 = 5.

Alternative proof: Observe that

2n + 10 ≤ 2n2 + 10n2 = 12n2 for n ≥ 1,

therefore, 2n + 10 = O(n2 ) is true for c = 12 and n0 = 1.

24 / 278
More on O-notation
I O(g(n)) is a set of functions
n o
O(g(n)) = f (n) : ∃ c, n0 s.t. 0 ≤ f (n) ≤ cg(n) for n ≥ n0

I The following functions are in O(n2 ), for examples:

I n2 + n
I n2 + 1000n
I 1000n2 + 1000n
I n/1000
I n2 / lg n

25 / 278
Ω-notation
3.1 Asymptotic notation 45

I Definition. g(n) is an asymptotic lower

c2 g.n/
bound for f (n), denoted by cg.n/

f .n/
f .n/ f (n) = Ω(g(n)) f .n/
cg.n/
c g.n/
1
if there exist constants c and n0 such
that

0 ≤ cg(n) ≤ f (n) for n ≥ n0

n n n
n0 n0 n0
f .n/
I D ‚.g.n//
Example f .n/ D O.g.n// f .n/ D .g.n//
(a) I Since (b) (c)

√
n ≥ lg n for n ≥ 16,
Figure 3.1 Graphic examples of the ‚, O, and  notations. In each part, the value of n0 shown
√
is the minimum possible value; any greater value would also work. (a) ‚-notation bounds a func-
n = Ω(lg n) is true with c = 1 and
tion to within constant factors. We write f .n/ D ‚.g.n// if there exist positive constants n0 , c1 ,
and c2 n 0 =that
such [Link] and to the right of n0 , the value of f .n/ always lies between c1 g.n/ and c2 g.n/
inclusive. (b) O-notation gives an upper bound for a function to within a constant factor. We write
f .n/ D O.g.n// if there are positive constants n0 and c such that at and to the right of n0 , the value
of f .n/ always lies on or below cg.n/. (c) -notation gives a lower bound for a function to within
a constant factor. We write f .n/ D .g.n// if there are positive constants n0 and c such that at and 26 / 278
More on Ω-notation
I Ω(g(n)) is a set of functions
n o
Ω(g(n)) = f (n) : ∃ c, n0 s.t. 0 ≤ cg(n) ≤ f (n) for n ≥ n0

I The following functions are in Ω(n2 ), for examples:

I n2
I n2 + n
I n2 − n
I 1000n2 + 1000n
I 1000n2 − 1000n
I n2.00001
I n2 lg n
I n3

27 / 278
Θ-notation
3.1 Asymptotic notation

I Definition. g(n) is an asymptotic tight

bound for f (n), denoted by c2 g.n/

f .n/
f (n) = Θ(g(n))
c1 g.n/
if there exist constants c1 , c2 and n0
such that

0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) n

n0
f .n/ D ‚.g.n//
for n ≥ n0 . (a)

Figure 3.1 Graphic exampl

is the minimum possible valu
tion to within constant factor
and c2 such that at and to the
inclusive. (b) O-notation giv
f .n/ D O.g.n// if there are p
of f .n/ always lies on or bel
a constant factor. We write f
to the right of n0 , the value of
28 / 278
Θ-notation
I Example:
1 2
I Show that
2
n − 2n = Θ(n2 )

Proof: Consider
1 2
c1 n2 ≤ n − 2n ≤ c2 n2
2
i.e.,
1 2
c1 ≤ − ≤ c2 ,
2 n
which is true if we pick
1 1
c1 = , c2 = and n0 = 8.
4 2
d
X
I Lemma. If p(n) = ai ni and ad > 0, then p(n) = Θ(nd ).
i=1

29 / 278
More on Θ-notation
I Θ(g(n)) is a set of functions

Θ(g(n)) =
n o
f (n) : ∃ c1 , c2 , n0 s.t. 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) for n ≥ n0

I The following functions are in Θ(n2 ), for examples:

I n2
I n2 + n
I n2 − n
I 1000n2 + 1000n
I 1000n2 − 1000n

30 / 278
Theorem
Theorem. O and Ω iff Θ.

31 / 278
Using limits for comparing orders of growth
In order to determine the relationship between f (n) and g(n), it is often
usefuly to examine
f (n)
lim =L
n→∞ g(n)

The possible outcomes:

1. L = 0:
f (n) = O(g(n))

2. L = ∞:
f (n) = Ω(g(n))

3. L 6= 0 is finite:
f (n) = Θ(g(n))

4. There is no limit: this technique cannot be used to determine the

asymptotic relationship between f (n) and g(n).

32 / 278
Review: L’Hopital’s rule
L’Hopital’s rule. Let f (x) and g(x) be differential functions with
derivatives f 0 (x) and g 0 (x), respectively, such that

lim f (x) = lim g(x) = ∞.

x→∞ x→∞

Then
f (x) f 0 (x)
lim = lim 0 .
x→∞ g(x) x→∞ g (x)

33 / 278
Examples for using limits and L’Hopital’s rule
for comparing orders of growth
1. f (n) = n2 and g(n) = n lg n

n2 = Ω(n lg n)

2. f (n) = n100 and g(n) = 2n

n100 = O(2n )

3. f (n) = 10n(n + 1) and g(n) = n2

10n(n + 1) = Θ(n2 )

34 / 278
Reading assignment
Read the textbook to review standard notations and common functions:

1. Floor: bxc and ceiling: dxe

2. Modular arithmetic: a mod m = remainder of the quotient a/m

3. Exponentials: ab , where a > 0

4. Logarithms: lg n = log2 n

5. Factorials: n! = n · (n − 1)! and 0! = 1

n
X
and basic formulas and properties of summation ak
k=1

35 / 278
III. Linear and Divide-and-Conquer Recurrences

36 / 278
Recurrence relations
I A recurrence relation (RR) for the sequence {an } is an equation
that expresses an in terms of one or more of the previous terms of the
sequence, namely, a0 , a1 , . . . , an−1 , for n ≥ n0 , where n0 is a
nonnegative integer.
The initial conditions for a sequence specify the terms that precede the
first term where the RR takes effect.
I Example.
fn = fn−1 + fn−2 for n ≥ 2 with initials f0 = 0 and f1 = 1.
I A sequence {an } is called a solution of a RR if {an } satisfies the RR.

I Example. Consider the RR: an = 2an−1 − an−2 for n ≥ 2.

I an = 3n is a solution
I an = 5 is also a solution.
I an = 2n is not a solution

37 / 278
Explicit substitution
For simple RRs, we can find its solution by an explicit substitution.
Examples
1. Find the solution of an = an−1 + 3 with a1 = 2.

2. Find the solution of an = 2an−1 + 1 with a1 = 1.

38 / 278
Linear recurrence relations
I A linear kth-order recurrence relation with constant coefficients is of
the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k + f (n),

where
I c1 , c2 , . . . ck are constants (do not depend on n),
I ck =6 0,
I f (n) is a function of n.
If f (n) = 0, then the relation is also called to be homogeneous.
Otherwise, it is called nonhomogeneous.

39 / 278
Linear recurrence relations
I A linear second-order homogeneous linear recurrence relation
with constant coefficients is a recurrence relation of the form

an = c1 an−1 + c2 an−2 , (1)

where c1 , c2 are constants (do not depend on n), and c2 6= 0.

I Theorem. For the RR (1), let r1 and r2 be the roots of the
characteristic equation:

r2 − c1 r − c2 = 0.
Then
I if r1 6= r2 , then the solution of the RR (1) is given by

an = αr1n + βr2n ,
I if r1 = r2 , then the solution of the RR (1) is given by

an = αr1n + βnr1n ,

where the constants α and β may be uniquely determined using the

initial conditions.
40 / 278
Linear recurrence relations
Exercises: find the solutions of the following recurrence relations:
I fn = fn−1 + fn−2 with f0 = 0 and f1 = 1.

I an = 6an−1 − 9an−2 with a0 = 1 and a1 = 6.

41 / 278
Divide-and-Conquer recurrences
I Divide-and-Conquer (DC) recurrence:
n
T (n) = a · T + f (n)
b
where
I constants a ≥ 1 and b > 1,
I function f (n) is nonnegative, f (n) ≥ 0.
I Example. the cost function of Merge Sort
n
T (n) = 1 + 2 · T + (n − 1)
2
where
I a = 2 (the number of subproblems)
I b = 2 (n/2 is the size of subproblems)
I f (n) = 1 + (n − 1) = n (the cost to divide and combine)
for simplicity, assuming n = 2k for k ≥ 1.

42 / 278
Two methods for finding solutions of DC recurrences
1. Explicit substitution/recursion
2. The master theorem/method

43 / 278
Solving DC recurrences by explicit substitution
I Explicit substitution can be illustrated by the following example
n
T (n) = 4 · T + n, n = 2k
2
I By iterating the recurrence (i.e. explicit substitution), we have
n
T (n) = 4 · T +n
 2 n 
n n
2
= 4 · 4 · T( ) + + n = 42 · T ( 2 ) + 2n + n
2 2 2
n
3 2
=4 ·T + 2 n + 2n + n
23
= ···
n
= 4k · T + 2k−1 n + · · · + 2n + n
2k
= 4k · T (1) + (2k−1 + · · · + 2 + 1)n
 k 
2 −1
= 4k · T (1) + n = n2 · T (1) + n(n − 1) = Θ(n2 )
2−1
44 / 278
The master theorem/method to solve DC recurrences
I For the DC recurrence, let n = bk , then by substitution1 , we have

k−1
X n
T (n) = nlogb a · T (1) + aj f
j=0
bj

I By carefully analyzing the terms in T (n), we can provide asymptotic

bounds on the growth of T (n) in the following three cases.

1 details can be safely skipped for our purpose.

45 / 278
The master theorem/method to solve DC recurrences
Case 1: If nlogb a is polynomially larger than f (n), i.e.,

nlogb a
= Ω(n ) for some constant  > 0,
f (n)

then
T (n) = Θ(nlogb a ).

Example. T (n) = 7 · T ( n2 ) + Θ(n2 )

46 / 278
The master theorem/method to solve DC recurrences
Case 2: If nlogb a and f (n) are on the same order, i.e.,

f (n) = Θ(nlogb a ),

then
T (n) = Θ(nlogb a lg n).

Example. T (n) = 2 · T ( n2 ) + Θ(n)

47 / 278
The master theorem/method to solve DC recurrences
Case 3: If f (n) is polynomially greater than nlogb a , i.e.,

f (n)
= Ω(n ) for some constant  > 0
nlogb a
and f (n) satisfies the regularity condition (see next slide),
then
T (n) = Θ(f (n)).

Example. T (n) = 4 · T ( n2 ) + n3

48 / 278
Remarks
1. f (n) satisfies the regularity condition if
n
a·f ≤ cf (n)
b
for some constant c < 1 and for all sufficient large n.
2. The proof of the master theorem is involved, shown in section 4.6,
which we can safely skip.
3. The master theorem doesn’t cover all possible cases, and the master
method cannot solve every DC recurrences.

49 / 278
IV. Divide-and-Conquer Algorithms

50 / 278
Divide-and-Conquer algorithms – Overview
The Divide-and-Conquer (DC) strategy solves a problem by

1. Breaking the problem into subproblems that are themselves smaller

instances of the same type of problem (”divide”),
2. Recursively solving these subproblems (”conquer”),
3. Appropriately combining their answers (”combine”)

Recall that MergeSort (in Part I) served as the first example of the DC
algorithm paradigm. In addition, in Homework 1, we have also explored the
DC strategy for finding min and max, ...

51 / 278
The maximum-subarray problem
Problem statement:
Input: an array A[1...n] of (positive/negative) numbers.
Output:
(1) Indices i and j such that the subarray A[i...j] has the
greatest sum of any nonempty contiguous subarray of A
(2) the sum of the values in A[i...j].

Note: Maximum subarray might not be unique, though its value is, so we
speak of a maximum subarray, rather than the maximum subarray.

52 / 278
The maximum-subarray problem
Example 1: stock prices and changes
Day 0 1 2 3 4
Price 10 11 7 10 6
A[...] (change) 1 -4 3 -4
maximum-subarray: A[3] (i = j = 3) and Sum = 3

Example 2: stock prices and changes

Day 0 1 2 3 4 5 6
Price 10 11 7 10 14 12 18
A[...] (change) 1 -4 3 4 -2 6
maximum-subarray: A[3...6] (i = 3, j = 6) and Sum = 11.

53 / 278
The maximum-subarray problem
Example 3: stock prices and changes

I Problem: find a maximum-subarray A[i...j]

I Solution: A[8...11] and sum = 43

54 / 278
The maximum-subarray problem
Algorithm 1. Solve by brute-force
I Check all subarrays A[i...j]
I Total number of subarrays A[i...j]:
 
n n! 1
= = n(n − 1) = Θ(n2 )
2 2!(n − 2)! 2

plus the arrays of length = 1.

I Cost
T (n) = Θ(n2 )

55 / 278
The maximum-subarray problem
Algorithm 2. Solve by Divide-and-Conquer
I Generic problem:
Find a maximum subarray of A[low...high]
with initial call: low = 1 and high = n
I DC strategy:

1. Divide A[low...high] into two subarrays of as equal size as possible by

finding the midpoint mid
2. Conquer:
(a) finding maximum subarrays of A[low...mid] and A[mid + 1...high]
(b) finding a max-subarray that crosses the midpoint
3. Combine: returning the max of the three

56 / 278
The maximum-subarray problem
I Possible locations of max subarrays:

I Correctness: This strategy works because any subarray must either lie
entirely in one side of midpoint or cross the midpoint.

57 / 278
The maximum-subarray problem
MaxSubarray(A,low,high)
if high == low // base case: only one element
return (low, high, A[low])
else
// divide
mid = floor( (low + high)/2 )
// conquer
(leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
(rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
(xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
// combine
if leftsum >= rightsum and leftsum >= xsum
return (leftlow,lefthigh,leftsum)
else if rightsum >= leftsum and rightsum >= xsum
return (rightlow,righthigh,rightsum)
else
return (xlow,xhigh,xsum)
end if
end if

58 / 278
The maximum-subarray problem
MaxXingSubarray(A,low,mid,high)
leftsum = -infty; sum = 0 // Find max-subarray of A[i..mid]
for i = mid downto low
sum = sum + A[i]
if sum > leftsum
leftsum = sum
maxleft = i
end if
end for
rightsum = -infty; sum = 0 // Find max-subarray of A[mid+1..j]
for j = mid+1 to high
sum = sum + A[j]
if sum > rightsum
rightsum = sum
maxright = j
end if
end for
// Return the indices i and j and the sum of two subarrays
return (maxleft,maxright,leftsum+rightsum)

59 / 278
The maximum-subarray problem
Remarks:
1. Initial call: MaxSubarray(A,1,n)
2. Base case is when the subarray has only 1 element.
3. Divide by computing mid.
Conquer by the two recursive calls to MaxSubarray. and a call to
MaxXingSubarray
Combine by determining which of the three results gives the maximum
sum.
4. Complexity:
n
T (n) = 2 · T + Θ(n) + Θ(1)
2
= Θ(n lg n)

60 / 278
Matrix-matrix multiplication: Strassen’s method
I Problem statement:
Given n × n matrices A and B, compute the product

C =A·B

61 / 278
Matrix-matrix multiplication: Strassen’s method
I Traditional method: (i, j, k)-triple-loop

for i = 1 to n
for j = 1 to n
C(i,j) = 0
for k = 1:n
C(i,j) = C(i,j) + A(i,k)*B(k,j)
end
end
end

I Complexity:
 
n
X Xn X
n 
T (n) =  2  = 2n3 = Θ(n3 )
i=1 j=1 k=1

62 / 278
Matrix-matrix multiplication: Strassen’s method
I Divide-and-conquer: a naive implementation

1. partition A and B and then direct block multiplication

  
A11 A12 B11 B12
AB =
A21 A22 B21 B22
 
A11 B11 + A12 B21 A11 B12 + A12 B22
=
A21 B11 + A22 B21 A21 B12 + A22 B22
 
C11 C12
≡ =C
C21 C22

2. Complexity:
n
T (n) = 8 · T ( ) + Θ(n2 ) = Θ(n3 )
2
Same cost as the traditional method, No improvement!

63 / 278
Matrix-matrix multiplication: Strassen’s method
I Strassen’s divide-and-conquer method (Strassen’s method) reduces the
complexity to
T (n) = Θ(nlg 7 ) = Θ(n2.8074.... ).
I Reference:
V. Strassen, Gaussian elimination is not optimal. Numer. Math.
Vol.13, pp.354-356, 1969
I The subsequent improvements, with the current world record2 being
O(n2.3728596 ), are much more complicated (and astonishing), but less
practical.

2 Oct. 2020, [Link]/abs/2010.05846

64 / 278
Matrix-matrix multiplication: Strassen’s method
I Strassen’s method – Step 1:
Divide
n n n n
 2 2   2 2 
n
2 A11 A12 n
2 B11 B12
A= and B =
n
2 A21 A22 n
2 B21 B22

65 / 278
Matrix-matrix multiplication: Strassen’s method
I Strassen’s method – Step 2:
Compute 10 matrices by + or − operations only:

S1 = B12 − B22
S2 = A11 + A12
S3 = A21 + A22
S4 = B21 − B11
S5 = A11 + A22
S6 = B11 + B22
S7 = A12 − A22
S8 = B21 + B22
S9 = A11 − A21
S10 = B11 + B12

66 / 278
Matrix-matrix multiplication: Strassen’s method
I Strassen’s method – Step 3:
Compute 7 matrices by multiplication:

P1 = A11 · S1
P2 = S2 · B22
P3 = S3 · B11
P4 = A22 · S4
P5 = S5 · S6
P6 = S7 · S8
P7 = S9 · S10

67 / 278
Matrix-matrix multiplication: Strassen’s method
I Strassen’s method – Step 4:
Add and subtract Pi to construct submatrices Cij of the product C:

C11 = P5 + P4 − P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 − P3 − P7

68 / 278
Matrix-matrix multiplication: Strassen’s method
I Correctness: straightfoward verification

I Complexity of Strassen’s method

n
T (n) = 7 · T ( ) + Θ(n2 )
2
= Θ(nlg 7 ) = Θ(n2.8074.... )

69 / 278
The closest pair of points
Problem statement:
Given a set of n points on a line (1-dimensional, unsorted), find
two points whose distance is shortest.

Remark:
I The problem is known as the closest pair problem in 1-dimension.
There is an algorithm for finding the closest pair of points in
2-dimension, i.e., on a plane, by extending the DC strategy we discuss
here.

70 / 278
The closest pair of points
A brute-force solution
I Pick two of n points and compute the distance

I Cost:  
n n!
T (n) = = = Θ(n2 ).
2 2!(n − 2)!

71 / 278
The closest pair of points
I Algorithm 1

1. Sort the points, say Merge Sort

2. Perform a linear scan

I Cost:
Θ(n lg n) + Θ(n) = Θ(n lg n)
I Unfortunately, the algorithm cannot be extended to the 2-dimension
case.

72 / 278
The closest pair of points
I Algorithm 2 (Divide-and-Conquer):
1. Divide the set S of n points by some point mid ∈ S into two sets S1
and S2 such that

p<q for all p ∈ S1 and q ∈ S2

For example, mid ∈ S can be the median, found in O(n).

2. Conquer:
(a) finds the closest pair recursively on S1 and S2 , gives us two closest
pairs of points
{p1 , p2 } ∈ S1 and {q1 , q2 } ∈ S2

(b) finds the closest crossing pair {p3 , q3 } with p3 ∈ S1 and q3 ∈ S2 .

3. Combine: the closest pair in the set S is

argmin{|p1 − p2 |, |q1 − q2 |, |p3 − q3 |}.

73 / 278
The closest pair of points
Remarks:
1. Both p3 and q3 must be within distance d = min{|p1 − p2 |, |q1 − q2 |}
of mid if {p3 , q3 } is to have a distance smaller than d.
2. How many points of S1 can lie in (mid − d, mid]?
answer: at most one
3. How many points of S2 can lie in [mid, mid + d)?
answer: at most one
4. Therefore, the number of pairwise comparisons that must be made
between points in different subsets is thus at most one.

74 / 278
The closest pair of points
Pseudocode of Algorithm 2 (Divide-and-Conquer)
ClosestPair(S)
if |S| = 2, then
d = |S[2] - S[1]|
else
if |S| = 1
d = infty
else
mid = median(S)
construct S1 and S2 from mid
d1 = ClosestPair(S1)
d2 = ClosestPair(S2)
p3 = max(S1)
q3 = min(S2)
d = min(d1, d2, q3-p3)
end if
end if
return d
75 / 278
The closest pair of points
Remark:
1. A median of a set A is the “halfway point” of the set A can be found
in linear time Θ(n) on average (see Chapter 9).
2. The points in the intervals (mid − d, mid] and [mid, mid + d) can be
found in linear time O(n), called linear scan.
3. Total cost:
n
T (n) = 2 · T ( ) + Θ(n)
2
= Θ(n lg n).

4. In general, given n points in m-dimension, the closest pair of points

can be found in O(n(lg n)m−1 ).

76 / 278
Extra: Medians and order statistics
I Selection problem:
Input:
A set A of n (distinct) numbers and an integer i, with 1 ≤ i ≤ n.
Output:
The element x ∈ A that is larger than exactly i − 1 other elements
of A. In other words, x is the ith smallest element of A.
I A median is the “halfway point” of the set A, i.e, i = d(n + 1)/2e.
I A simple sorting algorithm will take O(n lg n) time.
I Yet, a DC strategy leads to running time of O(n).

77 / 278
V. Greedy Algorithms

78 / 278
Greedy algorithms – Overview
I Algorithms for solving (optimization) problems typically go through a
sequence of steps, with a set of choices at each step.

I A greedy algorithm always makes the choice that looks best at the
moment, without regard for future consequence, i.e., “take what you
can get now” strategy

I Greedy algorithms do not always yield optimal solutions,

Local optimum =⇒
? Global optimum

but for many problems they do.

79 / 278
Activity-selection problem
Problem statement:

Input: Set S = {1, 2, . . . , n} of n activities

s[i] = start time of activity i
f [i] = finish time of activity i

Output: Maximum-size subset A ⊆ S of compatible activities

Remarks:
I Activities i and j are compatible if the intervals [s[i], f [i]) and
[s[j], f [j]) do not overlap.
I Without loss of generality, assume

f [1] ≤ f [2] ≤ · · · ≤ f [n]

80 / 278
Activity-selection problem
Example
i s[i] f [i]∗
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
*Note that f [i] are sorted

A = {1, 4, 8, 11} is an optimal solution.

A = {2, 4, 9, 11} is also an optimal solution.

81 / 278
Activity-selection problem
Greedy algorithm:
I pick the compatible activity with the earliest finish time.

Why?
I Intuitively, this choice leaves as much opportunity as possible for the
remaining activities to be scheduled

I That is, the greedy choice is the one that maximizes the amount of
unscheduled time remaining.

82 / 278
Activity-selection problem
I Pseudocode
Greedy_Activity_Selector(s,f)
// the array f already sorted
n = length(s)
A = {1}
j = 1
for i = 2 to n
if s[i] >= f[j]
A = A U {i}
j = i
end if
end for
return A

I Complexity: T (n) = O(n)

83 / 278
Activity-selection problem
Example
Pseudocode
i s[i] f [i]
1 1 4 Greedy_Activity_Selector(s,f)
2 3 5 n = length(s)
3 0 6 A = {1}
4 5 7 j = 1
5 3 8 for i = 2 to n
6 5 9 if s[i] >= f[j]
7 6 10 A = A U {i}
8 8 11 j = i
9 8 12 end if
10 2 13 end for
11 12 14 return A

Solution A = {1, 4, 8, 11} by Greedy Activity Selector.

84 / 278
Activity-selection problem
Question: Does Greedy Activity Selector work?
Answer: Yes!

Theorem. Algorithm Greedy Activity Selector produces a solution of

the activity-selection problem.

85 / 278
Activity-selection problem
The proof of Theorem is based on the following two properties:
Property 1.
There exists an optimal solution A such that the greedy choice “1”
in A.
Proof:
I let’s order the activities in A by finish time such that the first
activity in A is k1 .
I If k1 = 1, then A begins with a greedy choice
I If k1 6= 1, then let A0 = (A − {k1 }) ∪ {1}.
Then
1. the sets A − {k1 } and {1} are disjoint
2. the activities in A0 are compatible
3. A0 is also optimal, since |A0 | = |A|
I Therefore, we conclude that there always exists an optimal
solution that begins with a greedy choice.

86 / 278
Activity-selection problem
Property 2.
If A is an optimal solution, then A0 = A−{1} is an optimal solution
to S 0 = {i ∈ S, s[i] ≥ f [1]}.
Proof: By contradiction. If there exists B 0 to S 0 such that |B 0 | >
|A0 |, then let
B = B 0 ∪ {1},
we have
|B| > |A|,
which is contradicting to the optimality of A.

87 / 278
Activity-selection problem
Proof of Theorem: By Properties 1 and 2, we know that
I After each greedy choice is made, we are left with an optimization
problem of the same form as the original.
I By induction on the number of choices made, making the greedy
choice at every step proceduces an optimal solution.
Therefore, the Greedy Activity Selector produces an optimal solution
of the activity-selection problem.

88 / 278
Activity-selection problem
I Property 1 is called the greedy-choice property, generally casted as
a globally optimal solution can be arrived at by making a locally
optimal (greedy) choice.

I Property 2 is called the optimal substructure property, generally

casted as
an optimal solution to the problem contains within it optimal so-
lution to subprograms.

These are two key properties for the success of greedy algorithms!

89 / 278
Huffman codes
I Used for data compression, typically saving 20%–90%

I Basic idea:
represent often encountered characters by shorter (binary) codes

90 / 278
Huffman codes
Example
I Suppose we have the following data file with total 100 characters:

Character a b c d e f
Frequency 45 13 12 16 9 5
3-bit fixed length code 000 001 010 011 100 101
variable length code 0 101 100 111 1101 1100

I Total number of bits required to encode the file:

I 3-bit fixed-length code:

100 × 3 = 300 bits

I Variable-length code:

1·45 +3·13 + 3·12 + 3·16 + 4·9 + 4·5 = 225 bits

I Variable-length code saves 25%.

91 / 278
Huffman codes
Prefix(-free) codes:
1. No codeword is also a prefix3 of some other code.
2. Example. A prefix code
Char. a b c d e f
Code 0 101 100 111 1101 1100

3. Encoding and decoding with a prefix code.

Example, cont’d.
I Encode:
I beef −→ 101110111011100
I face −→ 110001001101

I Decode:
I 101110111011100 −→ beef
I 110001001101 −→ face

3 prefix: a word, letter or number placed before another

92 / 278
Huffman codes
4. Representation of prefix code:
I full binary tree: every nonleaf node has two children.
I All legal codes are at the leaves, since no prefix is shared
I Fact: an optimal code for a file is always represented by a full binary
tree.

93 / 278
Huffman codes
5. Example, cont’d
Character a b c d e f
Frequency 45 13 12 16 9 5
3-bit fixed length code 000 001 010 011 100 101
variable length code 0 101 100 111 1101 1100

(a) the (not-full-binary) tree corresponding to the fixed-legnth code

(b) the (full-binary) tree corresponding to the prefix code

94 / 278
Huffman codes
Let C = set of characters/alphabets, then
I A code = a binary tree T
I For each character c ∈ C, define

f (c) = frequency of c in the file

dT (c) = length of the code for c
= number of bits
= depth of c’ leave in the tree T

Then the number of bits (“cost of the tree/code T ”) required to

encode the file X
B(T ) = f (c) · dT (c),
c∈C

I A code T is optimal if B(T ) is minimal.

95 / 278
Huffman codes
Let C = set of characters/alphabets, then the basic idea of Huffman codes
to produce a prefix code for C:
represent often encountered characters by shorter (binary) codes
via
1. Building a full binary tree T in a bottom-up manner
2. Beginning with |C| leaves, performs a sequence of |C| − 1 “merging”
operations to create T
3. “Merging” operation is greedy: the two with lowest frequencies are
merged.

96 / 278
Review: data structure:priority queue
I A priority queue is a data structure for maintaining a set S of
elements, each with an associated key.
I A min-priority queue supports the following operations:
I Insert(S,x): inserts the element x into the set S, i.e., S = S ∪ {x}.
I Minimum(S): returns the element of S with the smallest “key”.
I ExtractMin(S): removes and returns the element of S with the
smallest “key”.
I DecreaseKey(S,x,k): decreases the value of element x’s key to the new
value k, which is assumed to be at least as small as x’s current key
value.
I A max-priority queue supports the operations:
Insert(S, x), Maximum(S), ExtractMax(S), IncreaseKey(S, x, k).
I Section 6.5 describes a binary heap implementation.
I Cost: let n = |S|, then
I initialization building heap = O(n)
I each heap operation = O(lg n)

97 / 278
Huffman codes
Pseudocode:
Huffmancode(C)
n = |C|
Q = C // min-priority queue, keyed by freq attribute
for i = 1 to n-1
allocate a new node z
z_left = x = ExtractMin(Q)
z_right = y = ExtractMin(Q)
freq[z] = freq[x] + freq[y]
Insert(Q,z)
endfor
return ExtractMin(Q) // the root of the tree

98 / 278
Huffman codes
Example

99 / 278
Huffman codes
Running time:

T (n) = init. Heap + (n − 1) loop × each Heap op.

= O(n) + O(n lg n) = O(n lg n),

assume that the min-priority queue Q is implemented as a binary min-heap.

100 / 278
Huffman codes
Optimality:
To prove the greedy algorithm Huffmancode producing an optimal prefix
code, we show that it exhibits the following two ingradients:
1. The greedy-choice property
If x, y ∈ C having the lowest frequencies, then there exists an optimal
code T such that
I dT (x) = dT (y)
I the codes for x and y differ only in the last bit

2. The optimal substructure property

If x, y ∈ C have the lowest frequencies, and let z be their parent.
Then the tree
T 0 = T − {x, y}
represents an optimal prefix code for the alphabet

C 0 = (C − {x, y}) ∪ {z}.

101 / 278
Huffman codes
By the above two properties, after each greedy choice is made, we are left
with an optimization problem of the same form as the original. By
induction, we have

Theorem. Huffman code is an optimal prefix code.

102 / 278
Greedy algorithms – Recap
I A greedy algorithm makes the choice that looks best at the moment,
without regard for future consequence

I The proof of the greedy algorithm producing an optimal solution is

based on the following two key properties:
I The greedy-choice property
a globally optimal solution can be arrived at by making a locally
optimal (greedy) choice.
I The optimal substructure property
an optimal solution to the problem contains within it optimal solution
to subprograms.

I Greedy algorithms do not always yield optimal solutions, but for many
problems they do.

103 / 278
Knapsack problem
Problem statement:
I Given n items {1, 2, . . . , n}, and item i is worth vi and weight wi
I Given a total allowable weight W
I Find a most valuable subset of items with total weight ≤ W
Rule: have to either take an item or not take it cannot take part of it (“0-1
Knapsack”).

Example: Given
i vi wi vi /wi
1 6 1 6
2 10 2 5
3 12 3 4
Total weight W = 5
Find a most valuable subset of items with total weight ≤ W = 5

104 / 278
Knapsack problem
Problem statement, mathematically – version 1:
Find a subset S ⊆ {1, 2, . . . , n} such that
X
maximize vi
i∈S
X
subject to wi ≤ W
i∈S

105 / 278
Knapsack problem
Problem statement, mathematically – version 2:
Let x = (x1 , x2 , . . . , xn ), and

1 i-th item is in the knapsack
xi =
0 i-th item is not in the knapsack

Then the knapsack problem is

n
X
maximize vi x i
i=1
subject to xi ∈ {0, 1}
Xn
wi xi ≤ W
i=1

106 / 278
Knapsack problem
The brute-force algorithm
I 2n feasible solutions
I Total cost = O(n · 2n )

107 / 278
Knapsack problem
Three possible greedy strategies:

1. Greedy by highest value vi

2. Greedy by least weight wi

vi
3. Greedy by largest value density
wi

All three appraches generate feasible solutions. However, we cannot

guarantee that any of them will always generate an optimal solution!

108 / 278
Knapsack problem
Example 1. Consider
i vi wi vi /wi
1 6 1 6
2 10 2 5
3 12 3 4
Total weight W = 5
Greedy by value density vi /wi : Optimal solution
I take items 1 and 2. I take items 2 and 3.
I value = 16, weight = 3 I value = 22, weight = 5
I Leftover capacity = 2 I no leftover capacity

109 / 278
Knapsack problem
Example 2. Given the following six items with W = 100:
Greedy by
i vi wi vi /wi value weight vi /wi
1 40 100 0.4 1 0 0
2 35 50 0.7 0 0 1
3 18 45 0.4 0 1 0
4 4 20 0.2 0 1 1
5 10 10 1 0 1 1
6 2 5 0.4 0 1 1
Total value 40 34 51
Total weight 100 80 85
All three greedy approaches generate feasible solutions, but none of them
generate the optimal solution:

Take items 2, 3 and 6, yield total value = 55, and total weight = 100.
Conclusion: Greedy algorithms doesn’t work for the knapsack problem!

110 / 278
VI. Dynamic Programming

111 / 278
Dynamic Programming – Overview
I Not a specific algorithm, but a technique like Divide-and-Conquer and
Greedy algorithms
I Developed back in the day (1950s) when “programming” meant
“tabular method”
I Used for optimization problems
I Find a solution with the optimal value
I Minimization or maximization

112 / 278
Dynamic Programming
Four-step (two-phase) method:
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

113 / 278
The rod cutting problem
Problem statement:
I Input:
1) a rod of length n
2) an array of prices pi for a rod of length i for i = 1, . . . , n.

I Output:
1) the maximum revenue rn obtainable for a rod of length n
2) optimal cut

In short,
How to cut a rod into pieces in order to maximize the revenue you
can get?

114 / 278
The rod cutting problem

Example

rod length i 1 2 3 4 5 6 7 8 9 10
price pi 1 5 8 9 10 17 17 20 24 30
ri 1 5 8 10 13 17 18 22 25 30
si 1 2 3 2 2 6 1 2 3 10

I ri : maximum revenue of a rod of length i

I si : optimal size of the first piece to cut

115 / 278
The rod cutting problem
A brute-force solution:
cut up a rod of length n in 2n−1 different ways (because can choose
to cut or not cut after each of the first n − 1 inchies)

Cost: Θ(2n−1 )

rod length i 1 2 3 4
Example. Given
price pi 1 5 8 9
There are 24−1 = 8 possible ways to cutting a rod of length 4:

116 / 278
The rod cutting problem
Dynamic Programming – Phase I:

I Since every optimal solution rn has a leftmost cut with length i, the
optimal revenue rn is given by

rn = max{p1 + rn−1 , p2 + rn−2 , . . . , pn−1 + r1 , pn + r0 }

= max {pi + rn−i } (2)
1≤i≤n
= pi∗ + rn−i∗ (3)

where

i∗ = the index attains the maximum

= the length of the leftmost cut

117 / 278
The rod cutting problem
Dynamic Programming – Phase II:
I How to compute rn by the expression (2)
I Recursive solution:
I top-down
I Calling graph

I Cost: let T (n) be the number of calls to compute rn , then

n−1
X
T (n) = 1 + T (j) for n > 1
j=0

with T (0) = 1.
Solution: T (n) = Θ(2n ).

118 / 278
The rod cutting problem
Dynamic Programming – Phase II:
I How to compute rn by the expression (2), cont’d
I Iterative solution
I bottom-up (memoization) (Pseudocode – see next page)
I Calling graph

I Cost: T (n) = Θ(n2 )

119 / 278
The rod cutting problem
cut-rod(p,n)
// an iterative (bottom-up) procedure for finding ‘‘r’’ and
// the optimal size of the first piece to cut off ‘‘s’’
Let r[0...n] and s[0...n] be new arrays
r[0] = 0
for j = 1 to n
// find q = max{p[i]+r[j-i]} for 1 <= i <= j
q = -infty
for i = 1 to j
if q < p[i] + r[j-i]
q = p[i] + r[j-i]
s[j] = i
end if
end for
r[j] = q
end for
return r and s

120 / 278
The rod cutting problem

Example

rod length i 1 2 3 4 5 6 7 8 9 10
price pi 1 5 8 9 10 17 17 20 24 30
ri 1 5 8 10 13 17 18 22 25 30
si 1 2 3 2 2 6 1 2 3 10

I ri : maximum revenue of a rod of length i

I si : optimal size of the first piece to cut
Note: si = i∗ in expression (3).

121 / 278
Matrix-chain multiplication
Review: Matrix-matrix multiplication
I Given A of order p × q and B of order q × r, then

C = AB is of order p × r

and (i, j)-entry of C is given by

q
X
Cij = Aik Bkj
k=1

I Cost: pqr scalar multiplications

122 / 278
Matrix-chain multiplication
Review: ordering of matrix-chain multiplication
I Given A1 : p0 × p1 , A2 : p1 × p2 and A3 : p2 × p3 , then different
orderings of the product A1 A2 A3 generate the same result, i.e.,

(A1 A2 )A3 = A1 (A2 A3 ).

I But the costs are different!

Example: Let A1 : 10 × 5, A2 : 5 × 10, A3 : 10 × 5
I cost of (A1 A2 )A3 = 10 · 5 · 10 + 10 · 10 · 5 = 1000

I cost of A1 (A2 A3 ) = 5 · 10 · 5 + 10 · 5 · 5 = 500

123 / 278
Matrix-chain multiplication

Problem statement:

Input: A sequence (chain) of (A1 , A2 , . . . , An ) of matrices,

where Ai is of order pi−1 × pi .

Output: full parenthesization (ordering) for the product

A1 · A2 · · · · An that minimizes the number
of (scalar) multiplications.

124 / 278
Matrix-chain multiplication
Brute-force solution
I Exhaustive search for determining the optimal ordering
I Counting the total number of orderings
1. Define
P (n) = the number of orderings for a chain of n matrices

2. Then

P (1) = 1
P (n) = P (1)P (n − 1) + P (2)P (n − 2) + · · · + P (n − 1)P (1)
n−1
X
= P (k)P (n − k) for n ≥ 2,
k=1

3. P (n) is called a Catalan number, and P (n) = Ω(2n )

I Therefore, exhaustive search for determining the optimal ordering is
infeasible!

125 / 278
Matrix-chain multiplication
DP – step 1: characterize the structure of an optimal ordering
I An optimal ordering of the product A1 A2 · · · An splits the product
between Ak and Ak+1 for some k:

A1 A2 · · · An = A1 · · · Ak · Ak+1 · · · An
| {z } | {z }
I Key observation:
I Within this (“global”) optimal ordering of A1 · · · An must be an
optimal ordering of (sub-product) A1 · · · Ak .4
I Similar observation holds for Ak+1 · · · An
I Thus, an optimal (“global”) solution contains within it the optimal
(“local”) solutions to subproblems.

4 Why? simply argue by contradiction: If there was a less costly way to order the

product A1 · · · Ak , substituting that ordering within this (global) optimal ordering would
produce another ordering of A1 A2 · · · An , whose cost would be less than the optimum, a
contradiction!
126 / 278
Matrix-chain multiplication
DP – step 2: recursively define the value of an optimal solution
I Define

m[i, j] = min. number of multip. needed to compute Ai · · · Aj .

Then m[1, n] = the cheapest way for the product A1 A2 · · · An .

I m[i, j] can be defined recursively:
for 1 ≤ i ≤ j ≤ n,

 0 if i = j
m[i, j] = n o
 min m[i, k] + m[k + 1, j] + pi−1 pk pj if i < j
i≤k<j

I To construct an optimal ordering, we track

the value k such that m[i, j] attains the minimum ≡ k∗ ≡ s[i, j]

127 / 278
Matrix-chain multiplication
DP – step 3: compute the value of an optimal solution in a bottom-up
approach
I Compute m[i, j] and s[i, j] in a bottom-up approach (see the
pseudocode in next page)

I Cost: T (n) = Θ(n3 )

1. compute n(n − 1)/2 entries of m-table

2. for each entry of m-table, it finds the minimum of fewer than n
numbers.

128 / 278
Matrix-chain multiplication
matrix-chain-order(p)
create m[1...n,1...n] and s[1...n,1...n] and n = length(p)-1
for i = 1 to n
m[i,i] = 0
for d = 2 to n
for i = 1 to n-d+1
j = i + d - 1
m[i,j] = +infty //compute m[i,j]=min_k{...}
for k = i to j-1
q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
endif
endfor
endfor
endfor
return m and s

129 / 278
Matrix-chain multiplication
DP – step 4: construct an optimal solution from computed m and s tables

130 / 278
Matrix-chain multiplication
Example 1. Let p = [10 5 10 5], then A1 : 10 × 5, A2 : 5 × 10,
A3 : 10 × 5
matrix-chain-order(p) generates the following m-table for optimal
costs, and s-table for orderings:
m = [ 0 500 500 ] s = [ 0 1 1 ]
[ 0 0 250 ] [ 0 0 2 ]
[ 0 0 0 ] [ 0 0 0 ]

By m-table, the minimum number of multiplications is m[1,3] = 500

By s-table, an optimal parenthesization (ordering) of the matrix-chain
multiplication is given by ( A1 )( A2 A3 )
131 / 278
Matrix-chain multiplication
Example 2. Let p = [3 1 4 5 4], then A1 : 3 × 1, A2 : 1 × 4, A3 : 4 × 5,
A4 : 5 × 4.
matrix-chain-order(p) generates the following m-table for optimal
costs, and s-table for orderings:
m = [ 0 12 35 52 ] s = [ 0 1 1 1 ]
[ 0 0 20 40 ] [ 0 0 2 3 ]
[ 0 0 0 80 ] [ 0 0 0 3 ]
[ 0 0 0 0 ] [ 0 0 0 0 ]

132 / 278
Matrix-chain multiplication
Example 2, cont’d
matrix-chain-order(p) generates the following m-table for optimal
costs, and s-table for orderings:
m = [ 0 12 35 52 ] s = [ 0 1 1 1 ]
[ 0 0 20 40 ] [ 0 0 2 3 ]
[ 0 0 0 80 ] [ 0 0 0 3 ]
[ 0 0 0 0 ] [ 0 0 0 0 ]

By m-table, the minimum number of multiplications is

m[1,4] = 52
By s-table, an optimal parenthesization (ordering) of the matrix-chain
multiplication is given by

( A1 )( ( A2 A3 ) A4 )

133 / 278
Matrix-chain multiplication
Example 3. Let p = [30 35 15 5 10 20 25].

matrix-chain-order(p) generates the following m-table for optimal

costs, and s-table for orderings:
m = [ 0 15750 7875 9375 11875 15125 ] s = [ 0 1 1 3 3 3 ]
[ 0 0 2625 4375 7125 10500 ] [ 0 0 2 3 3 3 ]
[ 0 0 0 750 2500 5375 ] [ 0 0 0 3 3 3 ]
[ 0 0 0 0 1000 3500 ] [ 0 0 0 0 4 5 ]
[ 0 0 0 0 0 5000 ] [ 0 0 0 0 0 5 ]
[ 0 0 0 0 0 0 ] [ 0 0 0 0 0 0 ]

By m-table, the minimum number of multiplications is

m[1,6] = 15125

By s-table, an optimal parenthesization (ordering) of the matrix-chain

multiplication is given by

( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 )
134 / 278
Longest Common Subsequence (LCS)

Problem statement:

Input: Sequences

Xm = hx1 , x2 , x3 , . . . , xm i
Yn = hy1 , y2 , . . . , yn i

Output: longest common subsequence (LCS) of Xm and Yn

135 / 278
LCS: terminology
1. Sequence: an order list of elements, e.g.
I X7 = hA, B, C, B, D, A, Bi
I Y6 = hB, D, C, A, B, Ai
I algorithm

2. Subsequence, e.g.
I hA, C, D, Bi is a subsequence of X7
I hB, C, Ai is a subsequence of Y6
I art is a subsequence of algorithm

3. Common subsequence, e.g.

I Z3 = hB, C, Ai is a common subsequence of X7 and Y6
I Z4 = hB, C, B, Ai is also a common subsequence of X7 and Y6

4. Longest common subsequence (LCS), e.g.

I Z4 is a longest common subsequence (LCS) of X7 and Y6
I LCS is not unique, hB, C, A, Bi is also a LCS.

136 / 278
LCS
A brute-force solution:
I For every subsequence of Xm , check if it is a subsequence of Yn .

I Running time: Θ(n · 2m )

I Intractable!

137 / 278
LCS
DP – step 1: characterize the structure of an optimal solution
Let Zk = hz1 , z2 , . . . , zk i be any LCS of

Xm = hx1 , x2 , . . . , xm i and Yn = hy1 , . . . , yn i

Then
I Case 1: xm = yn
(a) zk = xm = yn and
(b) Zk−1 = hz1 , z2 , . . . , zk−1 i = LCS(Xm−1 , Yn−1 )
I Case 2: xm 6= yn
(a) zk 6= xm =⇒ Zk = LCS(Xm−1 , Yn ) and
(b) zk 6= yn =⇒ Zk = LCS(Xm , Yn−1 )

In words, the optimal solution to the (whole) problem contains within it the
otpimal solutions to subproblems = the optimal substructure property

138 / 278
LCS
DP – step 2: recursively define the value of an optimal solution
I Define
c[i, j] = length of LCS(Xi , Yj )
for i = 0, 1, . . . , m and j = 0, 1, . . . , n
I c[m, n] = length of LCS(Xm , Yn )
I initialization: c[i, 0] = c[0, j] = 0

I By the optimal structure property of Case 1: xi = yj

(a) z` = xi = yj and
(b) Z`−1 = hz1 , z2 , . . . , z`−1 i = LCS(Xi−1 , Yj−1 ),
we have
c[i, j] = c[i − 1, j − 1] + 1
I By the optimal structure property of Case 2: xi 6= yj
(a) z` 6= xi =⇒ Z` = LCS(Xi−1 , Yj ) and
6 yj =⇒ Z` = LCS(Xi , Yj−1 ),
(b) z` =
we have
c[i, j] = max{c[i, j − 1], c[i − 1, j]}

139 / 278
LCS
I In summary
for i = 0, 1, . . . , m and j = 0, 1, . . . , n,


 0 if i = 0 or j = 0 (initials)

c[i, j] = c[i − 1, j − 1] + 1 if x[i] = y[j] (Case 1)


max{c[i, j − 1], c[i − 1, j]} if x[i] = 6 y[j] (Case 2)


I Meanwhile, create b[i, j] to record the optimal subproblem solution

chosen when computing c[i, j]

140 / 278
LCS
DP – step 3: compute c[i, j] (and b[i, j]) in a bottom-up approach
I Compute c[i, j] and b[i, j] in a bottom-up approach, see pseudocode.
I c[i, j] is the length of LCS(Xi , Yj )
I b[i, j] shows how to construct the corresponding LCS(Xi , Yj )

I Cost:
I Running time: Θ(mn)
I Space: Θ(mn)

141 / 278
LCS
LCS-length(X,Y)
set c[i,0] = 0 for i = 0,1,...,m and c[0,j] = 0 for j = 0,1,...,n
for i = 1 to m // Row-major order to compute c and b tables
for j = 1 to n
if X(i) = Y(j)
c[i,j] = c[i-1,j-1] + 1
b[i,j] = ’Diag’ // go to up diagonal
elseif c[i-1,j] >= c[i,j-1]
c[i,j] = c[i-1,j]
b[i,j] = ’Up’ // go up
else
c[i,j] = c[i,j-1]
b[i,j] = ’Left’ // go left
endif
endfor
endfor
return c and b

142 / 278
LCS
DP – step 4: construct an optimal solution from computed information

143 / 278
LCS
15.4 Longest common subsequence
Example: X7 = hA, B, C, B, D, A, Bi and Y6 = hB, D, C, A, B, Ai

c[·, ·] + b[·, ·] : j 0 1 2 3 4 5 6

i yj B D C A B A

0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 1 1 1
2 B 0 1 1 1 1 2 2
3 C 0 1 1 2 2 2 2
4 B 0 1 1 2 2 3 3
5 D 0 1 2 2 2 3 3
6 A 0 1 2 2 3 3 4
7 B 0 1 2 2 3 4 4

(1) Length of LCS = c[7,6] = 4

Figure 15.8 The c and b tables computed by LCS-L ENGTH on the sequences X
(2) By the b-table (“↑, ←, -”), the LCS is B C B A
D; A; Bi and Y D hB; D; C; A; B; Ai. The square in row i and column j contains th
and the appropriate arrow for the value of bŒi; j . The entry 4 in cŒ7; 6—the144lower
/ 278
r
Knapsack problem revisited
Problem statement:
Input: n items {1, 2, . . . , n}
Item i is worth vi and weight wi
Total weight W

Output: a subset S ⊆ {1, 2, . . . , n} such that

X X
wi ≤ W and vi is maximized
i∈S i∈S

Equivalently, the problem can be cast as follows:

n
X
maxxi ∈{0,1} vi x i
i=1
Xn
s.t. wi xi ≤ W
i=1

145 / 278
Knapsack problem revisited
Greedy solution strategy: three possible greedy approaches:

1. Greedy by highest value vi

2. Greedy by least weight wi

vi
3. Greedy by largest value density
wi

All three appraches generate feasible solutions. However, cannot guarantee

to always generate an optimal solution!

146 / 278
Knapsack problem revisited
Example 1:
i vi wi vi /wi
1 6 1 6
2 10 2 5
3 12 3 4
Total weight W = 5
Greedy by value density vi /wi :
I take items 1 and 2.
I value = 16, weight = 3
I Leftover capacity = 2
Optimal solution – by inspection
I take items 2 and 3.
I value = 22, weight = 5
I no leftover capacity
See Homework 4 for a large example.
147 / 278
Knapsack problem revisited
The knapsack problem exhibits the optimal substructure property:

Let ik be the highest-numberd item in an optimal solution

S = {i1 , . . . , ik−1 , ik },

Then
1. S 0 = S − {ik } is an optimal solution for weight W − wik
and items {i1 , . . . , ik−1 }
2. the value of the optimal solution S is

vik + the value of the subproblem solution S 0

148 / 278
Knapsack problem revisited
I Define
c[i, w] = value of an optimal solution for items {1, . . . , i}
and maximum weight w.
I Then we have the following two cases for the item i > 0:
I Case 1 (wi > w): the weight of item i is larger than the weight limit
w, then item i cannot be included, and

c[i, w] = c[i − 1, w]
I Case 2 (wi ≤ w): we have two choices:
I choice 1: includes item i, in which case it is vi plus a subproblem
solution for i − 1 items and the weight excluding wi :
I choice 2: does not include item i, in which case it is a subproblem
solution of i − 1 items and the same weight:

The better of these two choices should be made:

n o
c[i, w] = max vi + c[i − 1, w − wi ], c[i − 1, w]
| {z } | {z }
choice 1 choice 2
149 / 278
Knapsack problem revisited
I In summary, for i = 0, 1, . . . , n and w = 0, 1, . . . , W , the (i, w) entries
of c-table:


 0 if i = 0 or w = 0

c[i, w] = c[i − 1, w] if i > 0 and wi > w


max {vi + c[i − 1, w − wi ], c[i − 1, w]} if i > 0 and wi ≤ w


I The value of an optimal solution = c[n, W ].

150 / 278
Knapsack problem revisited
I The set of items to take can be deduced from the c-table by starting
at c[n, W ] and tracing where the optimal values came from as follows:
I If c[i, w] = c[i − 1, w], item i is not part of the solution, and we
continue tracing with c[i − 1, w].
I If c[i, w] 6= c[i − 1, w], item i is part of the solution, and we continue
tracing with c[i − 1, w − wi ].

I Running time: Θ(nW ):

I Θ(nW ) to fill in the c-table
(n + 1)(W + 1) entries each requiring Θ(1) time
I O(n) time to trace the solution
starts in row n and moves up 1 row at each step.

151 / 278
Knapsack problem revisited
Example 1.
i vi wi vi /wi
1 6 1 6
2 10 2 5
3 12 3 4
Total weight W = 5
By dynamic programming, we generate the following c-table:
i\w 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 6 6 6 6 6
2 0 6 10 16 16 16
3 0 6 10 16 18 22
By the c-table, we have
I Optimal value = c[3, 5] = 22.
I The optimal solution (the items to take): S = {3, 2}

152 / 278
Knapsack problem revisited
Example 2: We have n = 9 items with
I value = v = [2, 3, 3, 4, 4, 5, 7, 8, 8]
I weight = w = [3, 5, 7, 4, 3, 9, 2, 11, 5]
I Total allowable weight W = 15

Dynamics Programming generates the following c-table:

i/w 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2
2 0 0 0 2 2 3 3 3 5 5 5 5 5 5 5 5
3 0 0 0 2 2 3 3 3 5 5 5 5 6 6 6 8
4 0 0 0 2 4 4 4 6 6 7 7 7 9 9 9 9
5 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13
6 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13
7 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18
8 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18
9 0 0 7 7 7 11 11 15 15 15 19 19 19 21 23 23

By the c-table, we have

I Optimal value = c[9, 15] = 23.
I The set of items to take S = {9, 7, 5, 4}.

153 / 278
Dynamic Programming – Summary
I Not a specific algorithm, but a technique
(like Divide-and-Conquer and Greedy algorithms)
I Four-step (two-phase) technique:
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

154 / 278
Dynamic Programming – Summary
Three Key Elements of DP:
1. Optimal substructure:
the optimal solution to the problem contains optimal solutions to
subprograms =⇒ recursive algorithm
Example: Recursive formulation of LCS

2. Overlapping subproblems:
There are few subproblems in total, and many recurring instances
of each. (unlike divide-and-conquer, where subproblems are inde-
pendent)
Example: mn distinct subproblems of LCS

3. Memoization:
after computing solutions to subproblems, store in table, subse-
quent calls do table lookup.
Example: Θ(mn) running time for finding LCS

155 / 278
VII. Graph Algorithms

156 / 278
Graph algorithms – Outline
Part I

1. Notion of graphs
2. Breadth-first search
3. Depth-first search
4. Topological sort

Part II

1. Minimum spanning tree

2. Single source shortest path

157 / 278
Notion of graphs
I Graph G = (V, E):
I V = {vi } = set of vertices
I E = set of edges = a subset of V × V = {(vi , vj )}

I |E| = O(|V |2 )
I dense graph: |E| ≈ |V |2
I sparse graph: |E| ≈ |V |
I If G is connected, then |E| ≥ |V | − 1.

I Some variants
I undirected: edge (u, v) = edge (v, u)
I directed: (u, v) is an edge from u to v.
I weighted: weight on either edge or vertex
I multigraph: multiple edges between vertices

158 / 278
Notion of graphs
Representing a graph G by an Adjacency List
I For each vertex vi

Adj[vi ] = { vertices adjacent to vi }

I Storage: Θ(|V | + |E|) – “sparse representation”

I Variation: could also keep second list of edges coming into vertex

159 / 278
Notion of graphs
Example 1: undirected graph

Example 2: directed graph

160 / 278
Notion of graphs
Representing a graph G by an Adjacency Matrix A
I A = (aij ) is a |V | × |V | matrix, where

1, if (vi , vj ) ∈ E
aij =
0, otherwise

I If G is undirected, A is symmetric, i.e., AT = A.

I A is typically very sparse, use a sparse storage scheme in practice

161 / 278
Notion of graphs
Representing a graph G with no self-loops by an Incidence Matrix B
I If G is undirected, B = (bij ) is a |V | × |E| matrix,

1, if edge ej is incident with vertex vi
bij =
0, otherwise

I If G is directed, B = (bij ) is a |V | × |E| matrix, where


 1, if edge ej enters vertex vi
bij = −1, if edge ej leaves vertex vi
0, otherwise


162 / 278
Notion of graphs
Degree of a vertex
I undirected graph:
I The degree of a vertex = the number of incident edges
I The handshaking theorem:
X
degree(v) = 2|E|
v∈V

= total number of items in the adjacency list

I directed graph (digraph):

I The out-degree of a vertex = the number of edges leaves
I The in-degree of a vertex = the number of edges enters
X X
I out-degree(v) = in-degree(v) = |E|
v∈V v∈V

163 / 278
Breadth-First Search (BFS)
I For searching a graph
I An archetype for many important graph algorithms

I Input: G = (V, E) and a source vertex s,

Output: d[v] = distance from s to v for all v ∈ V .
I distance = fewest number of edges (= shortest path)

I BFS basic idea:

I discovers all vertices at distance k from the source vertex before
discovering any vertices at distance k + 1
I expanding frontier – “greedy” – propagate a wave 1 edge-distance at a
time.

164 / 278
Review: queue and stack data structure
I Queues and stacks are dynamic sets in which the elements removed
from the set is prescribed.
I The queue implements a First-In-First-Out (FIFO) policy.
The stack implements a Last-In-First-Out (LIFO) policy.
I Queue supports the following operations:
I Enqueue(Q,v): insert element v into the queue Q
I Dequeue(Q): delete the head element from the queue Q
I Stack supports the following operations:
I Push(S,x): insert element x into the stack S
I Pop(S): delete the most recently inserted element the stack S

I There are several efficient ways to implement queues and stacks, take
O(1) time.

165 / 278
Breadth-First Search (BFS)
Example 1.
BFS(G,s)
for each vertex u in V-{s}
d[u] = +infty
endfor
d[s] = 0
Q = empty //create FIFO queue
Enqueue(Q, s)
while Q not empty
u = Dequeue(Q)
for each v in Adj[u]
if d[v] = +infty
d[v] = d[u] + 1
Enqueue(Q, v)
endif
endfor
endwhile
return d

166 / 278
Breadth-First Search (BFS)
Example 2.
BFS(G,s)
for each vertex u in V-{s}
d[u] = +infty
endfor
d[s] = 0
Q = empty //create FIFO queue
Enqueue(Q, s)
while Q not empty
u = Dequeue(Q)
for each v in Adj[u]
if d[v] = +infty
d[v] = d[u] + 1
Enqueue(Q, v)
endif
endfor
endwhile
return d

167 / 278
Breadth-First Search (BFS)
Example 3.
BFS(G,s)
for each vertex u in V-{s}
d[u] = +infty
endfor
d[s] = 0
Q = empty //create FIFO queue
Enqueue(Q, s)
while Q not empty
u = Dequeue(Q)
for each v in Adj[u]
if d[v] = +infty
d[v] = d[u] + 1
Enqueue(Q, v)
endif
endfor
endwhile
return d

168 / 278
Breadth-First Search (BFS)
I Breadth-first spanning tree

I Running time: O(|V | + |E|)

I O(|V |): every vertex enqueued at most once
I O(|E|): every vertex dequeued at most once and we examine (u, v)
only when u is dequeued at most once if directed, at most twice if
undirected.

Note: not Θ(|V | + |E|)

I Correctness of BFS
I shortest path proof
I similar with weighted edges – Dijkstra’s algorithm – to be discussed

169 / 278
Depth-First Search (DFS)
I Another archetype for many important graph algorithms

I Methodically explore every vertex and every edge

I Input: G = (V, E)
Output: (1) two timestamps for every v ∈ V
d[v] = when v is first discovered.
f [v] = when v is finished.
(2) classification of edges

170 / 278
DFS
I Basic idea:
I go as deep as possible, then “back up”,
I edges are explored out of the most recently discovered vertex v that
still have unexplored edges leaving,
I when all of v’s edges have been explored, the search “backtracks” to
explore edges leaving the vertex from which v was discoverd.

I Three-color code for search status of vertices

I White = a vertex is undiscovered
I Gray = a vertex is discovered, but its processing is incomplete
I Black = a vertex is discovered, and its processing is complete

171 / 278
DFS
DFS(G) // main routine : DFS-Visit(u) // subroutine
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1; d[u] = time
endfor : for each v in Adj[u]
time = 0 : if color[v] = ‘‘white’’
for each vertex u in V : DFS-Visit(v)
if color[u] = ‘‘white’’ : endif
DFS-Visit(u) : end for
endif : color[u] = ‘‘black’’
endfor : time = time + 1; f[u] = time
Example 1.

172 / 278
DFS
DFS(G) // main routine : DFS-Visit(u) // subroutine
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1; d[u] = time
endfor : for each v in Adj[u]
time = 0 : if color[v] = ‘‘white’’
for each vertex u in V : DFS-Visit(v)
if color[u] = ‘‘white’’ : endif
DFS-Visit(u) : end for
endif : color[u] = ‘‘black’’
endfor : time = time + 1; f[u] = time
Example 2.

173 / 278
DFS
DFS(G) // main routine : DFS-Visit(u) // subroutine
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1; d[u] = time
endfor : for each v in Adj[u]
time = 0 : if color[v] = ‘‘white’’
for each vertex u in V : DFS-Visit(v)
if color[u] = ‘‘white’’ : endif
DFS-Visit(u) : end for
endif : color[u] = ‘‘black’’
endfor : time = time + 1; f[u] = time
Example 3.

174 / 278
DFS
Remarks:
I Vertices, from which exploration is incomplete, are proceessed in a
LIFO stack.
I Running time: Θ(|V | + |E|)
not big-O since guaranteed to examine every vertex and edge.

175 / 278
DFS
Classification of edges:
I T = Tree edge = encounter new vertex (gray to white)

I B = Back edge = from descendant to ancestor (gray to gray)

I F = Forward edge = from ancestor to descendant (gray to black)

I C = Cross edge = any other edges (between trees and subtrees)

(gray to black)

Note: In an undirected graph, there may be some ambiguity since edge

(u,v) and (v,u) are the same edge. Classify by the first type that matches.

176 / 278
DFS Classification of edges
DFS(G) // main routine : DFS-Visit(u) // subroutine T = Tree edge = encounter new vertex (gray to white)
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1 B = Back edge = from descendant to ancestor (gray to gray)
endfor : d[u] = time F = Forward edge = from ancestor to descendant (gray to
time = 0 : for each v in Adj[u] black)
for each vertex u in V : if color[v] = ‘‘white’’
if color[u] = ‘‘white’’ : DFS-Visit(v) C = Cross edge = any other edges (between trees and
DFS-Visit(u) : end if subtrees) (gray to black)
endif : end for
endfor : color[u] = ‘‘black’’
// end of main routine : time = time + 1
: f[u] = time
: // end of subroutine

Example 1.

177 / 278
DFS Classification of edges
DFS(G) // main routine : DFS-Visit(u) // subroutine T = Tree edge = encounter new vertex (gray to white)
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1 B = Back edge = from descendant to ancestor (gray to gray)
endfor : d[u] = time F = Forward edge = from ancestor to descendant (gray to
time = 0 : for each v in Adj[u] black)
for each vertex u in V : if color[v] = ‘‘white’’
if color[u] = ‘‘white’’ : DFS-Visit(v) C = Cross edge = any other edges (between trees and
DFS-Visit(u) : end if subtrees) (gray to black)
endif : end for
endfor : color[u] = ‘‘black’’
// end of main routine : time = time + 1
: f[u] = time
: // end of subroutine

Example 2.

178 / 278
DFS Classification of edges
DFS(G) // main routine : DFS-Visit(u) // subroutine T = Tree edge = encounter new vertex (gray to white)
for each vertex u in V : color[u] = ‘‘gray’’
color[u] = ‘‘white’’ : time = time + 1 B = Back edge = from descendant to ancestor (gray to gray)
endfor : d[u] = time F = Forward edge = from ancestor to descendant (gray to
time = 0 : for each v in Adj[u] black)
for each vertex u in V : if color[v] = ‘‘white’’
if color[u] = ‘‘white’’ : DFS-Visit(v) C = Cross edge = any other edges (between trees and
DFS-Visit(u) : end if subtrees) (gray to black)
endif : end for
endfor : color[u] = ‘‘black’’
// end of main routine : time = time + 1
: f[u] = time
: // end of subroutine

Example 3.

179 / 278
DFS vs. BFS
1. DFS: vertices from which the exploring is incomplete are processed in
a LIFO order (stack)
BFS: vertices to be explored are organized in a FIFO order (queue)

2. DFS contains two processing opportunities for each vertex v, when it

is “discovered” and when it is “finished”
BFS contains only one processing opportunity for each vertex v, and
then it is dequeued

180 / 278
Applications of DFS
1. For a undirected graph,
(a) a DFS produces only Tree and Back edges
(b) Acyclic iff a DFS yeilds no Back edges

2. A directed graph is acyclic iff a DFS yields no back edges, i.e.,

DAG (directed acyclic graph) ⇔ no back edges

3. Topological sort of a DAG – next

4. Connected components of a undirected graph

5. Strongly connected components of a drected graph

181 / 278
Topological sort
I A topological sort (TS) of a DAG G = (V, E) is a linear ordering of all
its vertices such that if (u, v) ∈ E, then u appears before v in the
ordering.
Example: given a DAG

TS (=linear ordering):

I A TS is not possible if G has a cycle.

I The ordering is not necessarily unique.

182 / 278
Topological sort
Applications: call-graph

183 / 278
Topological sort
Applications: call-graph of an integrated water flow model of California
Department of Water Resources
EXPLANATION
Redding
Element
Lake
Major River
Secondary River
Canal

Sacramento

San Francisco

Fresno

Bakersfield

184 / 278
Topological sort
I TS algorithm

1. run DFS(G) to compute finishing times f [v] for all v ∈ V

2. output vertices in the order of decreasing finishing times

I Running time: Θ(|V | + |E|)

185 / 278
Topological sort
Example: TS of “getting-dressed-graph”
22.4 Topological sort 613
1. DFS
22.4 Topological sort 613

11/16 undershorts socks 17/18

11/16 undershorts socks 17/18 watch 9/10
12/15 pants shoes 13/14 watch 9/10
12/15 pants shirt 1/8 shoes 13/14
belt shirt 1/8
(a) 6/7
(a) 6/7 belt tie 2/5
tie 2/5

jacket 3/4
jacket 3/4

2. Output vertices in the order of decreasing finishing times

(b) socks undershorts pants shoes watch shirt belt tie jacket
(b) socks
17/18
undershorts
11/16
pants
12/15
shoes
13/14
watch
9/10
shirt
1/8
belt
6/7
tie
2/5
jacket
3/4
17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4

Figure 22.7 (a) Professor Bumstead topologically sorts his clothing when getting dressed. Each
Figure
directed22.7 (a) /
edge .u; Professor Bumstead
means that garment topologically
u must be sorts
put on hisbefore
clothing when .
garment getting
The dressed.
discoveryEach
and
finishing times.u;
directed edge / ameans
from that garment
depth-first search areu must
shownbenext
put to
oneach
before garment
vertex. . The
(b) The samediscovery and
graph shown
finishing timessorted,
topologically from with
a depth-first search
its vertices are shown
arranged nexttotoright
from left eachinvertex.
order of(b) The samefinishing
decreasing graph shown
time.
topologically sorted,
All directed edges gowith
fromitsleft
vertices arranged from left to right in order of decreasing finishing time.
to right. 186 / 278
Topological sort
Theorem (correctness of the algorithm):
TS(G) produces a toplogical sort of a DAG G.
Proof: Just need to show that if (u, v) ∈ E, then f [v] < f [u] .
When we explore edge (u, v), u is gray, what’s the color of v?
I Is v gray too?
no, because then v would be ancestor of u, edge (u, v) is a back edge,
a contradiction of a DAG.
I Is v white?
yes, then v is descendant of u, by DFS, d[u] < d[v] < f [v] < f [u]
I Is v black?
yes, then v is already finished. Since we’re exploring (u, v), we have
not yet finished u, therefore f [v] < f [u]

187 / 278
Minimum Spanning Tree (MST)
I Undirected connected weighted graph G = (V, E, w)
I Weight function w : E −→ R
I Spanning tree: a tree that connects all vertices
Example

I T : Minimum Spanning Tree (MST)

X
w(T ) = w(u, v) is minimized
(u,v)∈T

Example: w(T ) = 37.

I MST is not necessarily unique.
For simplicity in theory, assume all edge weight distinct, and therefore,
has a unique MST.
188 / 278
MST
Basic idea of constructing (“growing”) a MST:
I successively select edges to include in the tree
I meanwhile, guarantee that after the inclusion of each new selected
edge, it forms a subset of some MST.

One of the most famous greedy algorithms, along with Huffman coding

189 / 278
MST
Two basic properties:
1. Optimal substructure: optimal tree contains optimal subtrees.
Let T be a MST of G = (V, E). Removing (u, v) of T partitions T
into two trees T1 and T2 . Then T1 is a MST of G1 = (V1 , E1 ) and T2
is a MST of G2 = (V2 , E2 ).5

Proof. Note that

w(T ) = w(T1 ) + w(u, v) + w(T2 ).

There cannot be a better subtree than T1 or T2 , otherwise T would be

suboptimal.

5 The subgraph G is induced by vertices in T , i.e., V = {vertices in T } and

1 1 1 1
E1 = {(x, y) ∈ E; x, y ∈ V1 }. Similarly for G2 .
190 / 278
MST
2. Greedy-choice property:
Let T be a MST of G = (V, E), A ⊆ T be a subtree of T , and (u, v)
be min-weight edge in G connecting A and V − A. Then (u, v) ∈ T .6

Proof. If (u, v) 6∈ T , then

I (u, v) ∪ T forms a cycle,
I replace one of edges of T by (u, v) form a new tree T
I this is contradiction to T is MST

6 Note: there is an abuse of notation here that we will view A as being both edges

and vertices.
191 / 278
MST
Prim’s algorithm
I Basic idea:
I starts from an arbitrary root r
I builds one tree, so that A is always a tree
I at each step, find the next lightest edge crossing cut (A, V − A) and
add this edge to A (“greedy choice”)

I How to find the next lightest edge quickly?

Answer: use a priority queue

192 / 278
Review: Priority Queue
A priority queue maintains a set S of elements, each with an associated
value called a “key”, and supports the following operations:
I Search(S,k):
returns x in S with key[x] = k
I Insert(S, x)/Delete(S, x):
inserts/deletes the element x into the set S
I Maximum(S)/Minimum(S):
returns x in S with largest/smallest key
I Extract-max(S)/Extract-min(S):
removes and returns x in S with largest/smallest key
I Increase-key(S, x, k)/Decrease-key(S, x, k):
increases/decreases the value of element x’s key to the new value k

Recall that the priority queue has been used in Huffman coding.

193 / 278
MST
MST-Prim(G, w, r)
Q = empty
for each vertex u in V
key[u] = infty // min. weight of any edge (w,u) and w in A
pi[u] = nil // parent of u
Insert(Q, u)
endfor
Decrease-key(Q,r,0)
while Q not empty
u = Extract-Min(Q)
for each v in Adj[u]
if (v in Q) and (w(u,v) < key[v])
Decrease-key(Q, v, w(u,v))
pi[v] = u // parent of v
endif
endfor
endwhile
return A = { (v, pi[v]): v in V-{r} } // MST

194 / 278
MST Example 1. Run and illustrate
MST-Prim(G, w, r)
Q = empty
for each vertex u in V
key[u] = infty
pi[u] = nil
Insert(Q, u)
endfor
Decrease-key(Q,r,0)
while Q not empty
u = Extract-Min(Q)
for each v in Adj[u]
if (v in Q) and (w(u,v) < key[v])
Decrease-key(Q, v, w(u,v))
pi[v] = u // parent of v
endif
endfor
endwhile
return A = { (v, pi[v]): v in V-{r} }

195 / 278
MST Example 2. Run and illustrate
MST-Prim(G, w, r)
Q = empty
for each vertex u in V
key[u] = infty
pi[u] = nil
Insert(Q, u)
endfor
Decrease-key(Q,r,0)
while Q not empty
u = Extract-Min(Q)
for each v in Adj[u]
if (v in Q) and (w(u,v) < key[v])
Decrease-key(Q, v, w(u,v))
pi[v] = u // parent of v
endif
endfor
endwhile
return A = { (v, pi[v]): v in V-{r} }

196 / 278
MST
Running time of Prim’s algorithm
1. depends on how the priorty queue Q is implemented
2. Suppose Q is a binary heap (see Section 6.1)
I Initialize Q and the first for loop: O(|V | lg |V |)
I Decrease key of root r: O(lg |V |)
I While-loop:
a) |V | Extract-Min calls: O(|V | lg |V |)
b) ≤ |E| Decrease-Key calls: O(|E| lg |E|)
3. Total: O(|E| lg |V |)
4. Note: G is connected, lg |E| = Θ(lg |V |)

197 / 278
MST
Kruskal’s algorithm
I Basic idea:
I scan edges in increasing of weight
I put edge in the final MST T if no loop created

I Why does this result in MST?

Answer: min-weight edge is always in MST (the greedy-choice
property).
I How to make sure “no loop created”?
Answer: use “disjoint-set” data structure

198 / 278
Review: Disjoint-Set
Disjoint-Set maintains a collection of S = {S1 , S2 , ...Sk } of disjoint
dynamic sets. Each set is identified by a representative, which is some
member of the set.
A disjoint-set data structure supports the following operations:
I Make-set(x):
creates a new set whose only member (and thus representative) is x.
I Union(x, y):
unites the sets that contain x and y, say Sx and Sy , into a new set
that is the union of these two sets: Sx ∪ Sy . The representative is any
member of Sx ∪ Sy .
I Find-set(x):
returns (a pointer to) the representative of the (unique) set containing
x.

199 / 278
MST
MST-Kruskal(G, w)
A = emtpy
for each vertex v in V
Make-set(v)
endfor
Sort the edges E in nondecreasing order by w
for each edge (u,v) in E, taken in nondecreasing order by w
if Find-set(u) \= Find-set(v)
A = A U {(u,v)}
Union(u,v)
endif
endfor
return A

200 / 278
MST Example 1. Run and illustrate
MST-Kruskal(G, w)
A = emtpy
for each vertex v in V
Make-set(v)
endfor
Sort the edges E in nondecreasing order by w
for each edge (u,v) in E, taken in nondecreasing order by w
if Find-set(u) \= Find-set(v)
A = A U {(u,v)}
Union(u,v)
endif
endfor
return A

201 / 278
MST
Running time of Kruskal’s algorithm
1. depends on the implementation of the disjoint-set
I |V | Make-Set ops
I 2|E| Find-Set ops
I |V | − 1 Union ops
2. Sort: Θ(|E| lg |E|)
3. Total: O(|E| lg |V |)
4. Note: G is connected, lg |E| = Θ(lg |V |)

202 / 278
Shortest paths – Intro
I Generalization of BFS to handle weighted graphs

I Directed weighted graph G = (V, E, w)

I Weight function w : E −→ R

I Weight of path p = v0 → v1 → · · · → vk

k
X
w(p) = w(vi−1 , vi )
i=1

I Shortest-path weight u ; v

min{w(p) : u ; v} if there exists a path p = u ; v


δ(u, v) =
∞ otherwise

203 / 278
Shortest paths – Intro
I Shortest-path u ; v:
any path p such that w(p) = δ(u, v)

I Example:

(a) A weighted, directed graph, source s

(b) The shaded edges form a shortest-path tree rooted at s
(c) Another shortest-path tree with the same root, therefore, shortest path
is not necessarily unique.

204 / 278
Shortest paths – Intro
I Single-source shortest path problem (SSSP):
find shortest-paths from a given source vertex s ∈ V to every vertex
v∈V
I Basic SSSP algorithm: Bellman-Ford algorithm (discussed next)

I Variants:
I Single-destination: find shortest-path to a given destination vertex
(reverse the direction of each edge to become the single-source
problem)
I Single-pair: given u and v, find shortest-path from u to v
(no way know that’s better in worst case than solving single-source)
I All-pairs: find shortest-paths from u to v for all u, v ∈ V .
(By running Bellman-Ford once for each vertex, cost
O(V 2 E) = O(V 4 ) on dense graph. Can do better.

205 / 278
Shortest paths – Intro
Well-definedness
I Negative-weight edges are OK, as long as no negative-weight cycles
reachable from the source. Otherwise, can always get a shorter path
by going around the cycle again.
I The shortest path problem is ill-posed in graph with negative-weight
cycle
I Bellman-Ford algorithm can detect and report the existence of
negative-weight cycle

206 / 278
Shortest paths – Intro
I Optimal substructure property of SSSP:
subpaths of shortest-paths are shortest-paths.

Proof. If some subpath were not a shortest path, could substitute it

and create a shorter total path.

I Thus, will see greedy and dynamical programming algorithms.

207 / 278
Shortest paths – Intro
I Notation:
d[v]: shortest-path estimate
π[v]: predecessor of v

I Output of SSSP algorithms

d[v] = δ(s, v) = shortest-path weight s ; v
π[v] = predecessor of v on a shortest path from s.

208 / 278
Shortest paths – Intro
Two key components of shortest-path algorithms:
I Initialization
for every vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0 // s = source vertex
I Relaxing an edge (u, v) : can we improve the shortest-path estimate
d[v] by going through u and taking the edge (u, v)?
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endif

209 / 278
Shortest paths – Intro
Basic properties:
1. Triangular inequality
for all (u, v) ∈ E, δ(u, v) ≤ δ(u, x) + δ(x, v)

2. Upper-bound property
Always have d[v] ≥ δ(s, v) for all v.
Once d[v] = δ(s, v), it never changes

3. No-path property
If δ(s, v) = ∞, then d[v] = ∞ always

4. Convergence property
If s ; u → v is a shortest-path, and d[u] = δ(s, u). Then after “Relax
u → v”, d[v] = δ(s, v)

5. Path relaxation property

Let p = v0 → v1 → · · · → vk be a shortest-path. If we relax in order,
(v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ), even intermixed with other
relaxations, then d[vk ] = δ(v0 , vk )

210 / 278
Shortest paths – Algorithms
The Bellman-Ford algorithm
I Most basic algorithm for the shortest-path problem.

I Allow negative-weight edges.

I Compute d[v] and π[v] for all v ∈ V :

I d[v] = δ(s, v): the shortest-path weight from the source s to v.
I π[v]: the parent (predecessor) of v.

I Return
I TRUE if no negative-weight cycles reachable from source s
I FALSE otherwise.

211 / 278
Shortest paths – Algorithms
Bellman-Ford(G, w, s)
for each vertex v in V // initialization
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
for i = 1 to |V|-1 // |V|-1 passes
for each edge (u,v) in E // in a prescribed order
if d[v] > d[u] + w(u,v) // relax if necessary
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endfor
for each edge (u,v) in E // final check pass
if d[v] > d[u] + w(u,v)
return FALSE
endfor
return TRUE, d, pi

212 / 278
Shortest paths – Algorithms
Bellman-Ford(G, w, s) Example 1: run and illustrate
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
for i = 1 to |V|-1
for each edge (u,v) in E
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endfor
for each edge (u,v) in E
if d[v] > d[u] + w(u,v)
return FALSE
endfor
return TRUE, d, pi

213 / 278
Shortest paths – Algorithms
Bellman-Ford(G, w, s) Example 2: run and illustrate
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
for i = 1 to |V|-1
for each edge (u,v) in E
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endfor
for each edge (u,v) in E
if d[v] > d[u] + w(u,v)
return FALSE
endfor
return TRUE, d, pi

214 / 278
Shortest paths – Algorithms
The Bellman-Ford algorithm
I Running time: Θ(|V | · |E|).

I Values you get on each pass and how quickly it converges depends on
order of relaxation (processing edges). But guaranteed to converge
after |V | − 1 passes, assuming no negative-weight cycles.

215 / 278
Shortest paths – Algorithms
Dijkstra’s algorithm
I No negative weight edges

I Like BFS. If all weights = 1, use BFS.

I Use Q = priority queue keyed by d[v]

(vs. BFS uses FIFO queue)

216 / 278
Shortest paths – Algorithms
Dijkstra(G, w, s)
for each vertex v in V // Initialization
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
Q = V // priority queue keyed by d[v]
while Q is not empty
u = Extract-Min(Q)
for all edge (u,v) in E
if d[v] > d[u] + w(u,v) // Relax if necessary
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endwhile
return d, pi

217 / 278
Shortest paths – Algorithms
Dijkstra(G, w, s) Example 1. run and illustrate
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
Q = V
while Q is not empty
u = Extract-Min(Q)
for all edge (u,v) in E
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endwhile
return d, pi

218 / 278
Shortest paths – Algorithms
Dijkstra(G, w, s) Example 2. run and illustrate
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
Q = V
while Q is not empty
u = Extract-Min(Q)
for all edge (u,v) in E
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endwhile
return d, pi

219 / 278
Shortest paths – Algorithms
Dijkstra’s algorithm
I Running time: O(|E| lg |V |) (binary heap)

I Similar to the BFS and MST-algorithms, Dijkstra’s algorithm is a

greedy algorithm. It always chooses the “lightest” or “closest” vertex
in V − S to insert into S, where S is the set of vertices whose final
shortest-path weights are determined.

220 / 278
Shortest paths – Algorithms
The SSSP in DAG
I DAG: can have negative-weight edges, but no negative-weight cycle.

I How fast can do it?

Answer: O(|V | + |E|), instead of Θ(|V | · |E|) by Bellman-Ford

221 / 278
Shortest paths – Algorithms
DAG-Shortest-Path(G, w, s)
Topological sort (TS) of vertices of G
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
for each vertex u taken in TS order
for each vertex v in Adj[u]
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endfor
return d, pi

222 / 278
Shortest paths – Algorithms
DAG-Shortest-Path(G, w, s) Example. run and illustrate
TS of G
for each vertex v in V
d[v] = infty
pi[v] = nil
endfor
d[s] = 0
for each vertex u in TS order
for each vertex v in Adj[u]
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
pi[v] = u
endfor
endfor
return d, pi

223 / 278
Shortest-paths – Proofs
I Weight of path p = v0 → v1 → · · · → vk :

k
X
w(p) = w(vi−1 , vi )
i=1

I Shortest-path weight u ; v
p
min{w(p) : u ; v} if there exists a path u ; v

δ(u, v) =
∞ otherwise

I Shortest-path u ; v
any path p such that w(p) = δ(u, v)

224 / 278
Shortest-paths – Proofs
Triangular inequality:
for all (u, v) ∈ E, δ(u, v) ≤ δ(u, x) + δ(x, v).

Proof: Note that

Weight of shortest path s ; v ≤ weight of any path s ; v

The path s ; u → v is a path s ; v, and if we use a shortest

path s ; u, its weight is δ(u, x) + δ(x, v).

225 / 278
Shortest-paths – Proofs
Upper-bound property:
1) Always have d[v] ≥ δ(s, v) for all v.
2) Once d[v] = δ(s, v), it never changes.
Proof. For item 1). Initially true since d[v] = ∞. By contradiction, suppose
there exists a vertex such that d[v] < δ(s, v). Without loss of generality, v
is first vertex for which this happens. Let u be the vertex that causes d[v]
change. Then d[v] = d[u] + w(u, v). So

d[v] < δ(s, v)

≤ δ(s, u) + w(u, v)
≤ d[u] + w(u, v)

which implies d[v] < d[u] + w(u, v). Contradicts d[v] = d[u] + w(u, v).
This completes the proof of item 1).
For item 2), once d[v] reaches δ(s, v), it never goes lower. It also never
goes up, since relaxations only lower shortest-path weights.

226 / 278
Shortest-paths – Proofs
No-path property:
If δ(s, v) = ∞, then d[v] = ∞ always.
Proof. The upper bound property d[v] ≥ δ(s, v) and δ(s, v) = ∞ imply
that d[v] = ∞.

227 / 278
Shortest-paths – Proofs
Convergence property:
If s ; u → v is a shortest-path, and d[u] = δ(s, u). Then after
“Relax u → v”, d[v] = δ(s, v).
Proof. After relaxation

d[v] ≤ d[u] + w(u, v)

= δ(s, u) + w(u, v)
= δ(s, v)

On the other hand, by the upper bound property, we have d[v] ≥ δ(s, v).
Therefore, it must have d[v] = δ(s, v).

228 / 278
Shortest-paths – Proofs
Path relaxation property
Let p = v0 → v1 → · · · → vk be a shortest-path. If we relax in
order, (v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ), even intermixed with other
relaxations, then d[vk ] = δ(v0 , vk ).
Proof. We use the induction to show d[vi ] = δ(s, vi ) after (vi−1 , vi ) is
relaxed.
I Basis step: i = 0. Initially d[v0 ] = δ(s, v0 ) = δ(s, s)
I Inductive step: Assume d[vi−1 ] = δ(s, vi−1 ). Relax (vi−1 , vi ). By the
convergence property, d[vi ] = δ(s, vi ) afterward and d[vi ] never
changes.

229 / 278
Shortest-paths – Proofs
Correctness of the Bellman-Ford algorithm
It is guaranteed to converge after |V | − 1 passes, assuming no
negative-weight cycles.
Proof. Use the path-relaxation property.
Let v be reachable from s, and let p = v0 → v1 → · · · → vk be the shortest
path from s to v, where v0 = s and vk = v.
Since p is acyclic, the number of edges of p has ≤ |V | − 1 edges, so that
k ≤ |V | − 1.
Each iteration of the for loop realxes all edges:
I First iteration relaxes (v0 , v1 )
I Second iteration relaxes (v1 , v2 )
I ...
I kth iteration relaxes (vk−1 , vk )
By the path-relaxation property, d[v] = d[vk ] = δ(s, vk ) = δ(s, v).

230 / 278
Shortest-paths – Proofs
Correctness of Dijkstra’s algorithm
Show that d[u] = δ(s, u) when u is added to S in each iteration.
Proof:
I We prove by contradiction. Suppose there exists u such that
d[u] 6= δ(s, u). Without loss of generality, let u be the first vertex for
which d[u] 6= δ(s, u) when u is added to S in each iteration.
I Observation:
I u 6= s, since d[s] = δ(s, s) = 0.
I Therefore, s ∈ S and S 6= ∅
I There must have be some path s ; u, since otherwise
d[u] = δ(s, u) = ∞ by no-path property.
p
So, there is a path s ; u. Then there is a shortest path s ; u.
I Just before u is added to S, path p connects a vertex in S (i.e., s) to
a vertex in V − S (i.e., u). Let y be first vertex along p that’s in
V − S and and let x be y’s predecessor.
I Decompose p into
p1 p2
s;x→y;u
(could have x = s or y = u, so that p1 or p2 may have no edges.)
231 / 278
Shortest-paths – Proofs
Correctness of Dijkstra’s algorithm, cont’d
I Claim:7 d[y] = δ(s, y) when u is added to S.
I Now we can get a contradiction to d[u] 6= δ(s, u):
y is on shortest path s ; u, and all edge weights are nonnegative
⇓
δ(s, y) ≤ δ(s, u)
⇓
d[y] = δ(s, y) ≤ δ(s, u) ≤ d[u] (upper bound property)
Also, both y and u were in Q when we chose u, so that

d[u] ≤ d[y]

Therefore, d[y] = δ(s, y) = δ(s, u) = d[u]. Contradicts assumption

that d[u] 6= δ(s, u).
I Hence, Dijkstra’s algorithm is correct.

7 Proof. x ∈ S and u is the first vertex such that d[u] = δ(s, u) when u is added to S

⇒ d[x] = δ(s, x) when x is added to S. Relaxed (x, y) at that time, so by the

convergence property, d[y] = δ(s, y).
232 / 278
VIII. NP-completeness

233 / 278
NP-Completeness – overview
1. Introduction

2. P and NP

3. NP-complete (NPC): formal definition

4. How to prove a problem is NPC

5. How to solve a NPC problem: approximate algorithms

234 / 278
1. Introduction
(a) Tractable and intractable problems
I Problems that are solvable by polynomial-time algorithms are tractable

I Problems that require superpolynomial time are intractable.

Almost all the algorithms we have studied thus far have been
polynomial-time algorithms on inputs of size n, their worst-case running
time is O(nk ) for some constant k.

235 / 278
1. Introduction
(b) NP-complete (NPC) problems: an informal definition
A large class of very diverse problems share the following properties:
1. We only know how to solve those problems in time much larger than
polynomial, namely exponential time.

2. If we could solve one NPC porblem in polynomial time, then there is a

way to solve every NPC problem in polynomial time.

236 / 278
1. Introduction
(c) Reasons to study NPC porblems – practical
I There is a large class of very diverse intractable problems, and the
difference between tractable and intractable may appear “only
slightly” – examples later;
I you can use a known algorithm for an intractable problem, and accept
that it will take a long long time to solve; or
I you can settle for approximating the solution, e.g., finding a nearly
best solution rather than the optimum; or
I you can change your problem formulation so that it is solvable in
polynomial time.

237 / 278
1. Introduction
(c) Reasons to study NPC porblems – theoretical
I We stated above that “We only know” how to solve those problems in
time much larger than polynomial, Not that we have proven that these
problems require exponential time.
I Indeed, this is one of the most famous problems in computer science:

?
P = NP

namely

Whether NPC problems have polynomial solutions?

I First posed in 1971

[Link]

238 / 278
1. Introduction
(d) P-vs-NP examples
Example 1.
I Shortest path:
finding the shortest path from a single source in a directed graph.
I Longest path:
finding the longest simple path between two vertices in a directed
graph.

The first one is solvable in polynomial time (the Bellman-Ford algorithm),

and the second is NPC, but the difference appears to be slight.

239 / 278
1. Introduction
(d) P-vs-NP examples
Example 2.
I Euler tour:
given a connected, directed graph G, is there a cycle that visits each
edge exactly once (although it is allowed to visit each vertex more
than once)?
I Hamiltonian cycle:
given a connected directed graph G, is there a simple cycle that visits
each vertex exactly once?

The first one is solvable in polynomial time8 , and the second is NPC, but
the difference appears to be slight

8 Euler cycle of G = (V, E) iff in-degree(v) = out-degree(v) for ∀v ∈ V .

240 / 278
1. Introduction
(d) P-vs-NP examples
Example 3.
I Minimum spanning tree (MST):
given a weighted graph and an integer k, is there a spanning tree
whose total weight is k or less?
I Traveling salesperson problem (TSP):
given a weighted graph and an integer k, is there a cycle that visits all
vertices exactly once whose total weight is k or less?

The first one is solvable in polynomial time (Prim’s and Kruskal’s

algorithms), and the second is NPC, but the difference appears to be slight

241 / 278
1. Introduction
Traveling salesperson problem (TSP)

242 / 278
1. Introduction
(d) P-vs-NP examples
Example 4.
I Circuit value:
given a Boolean formula and its input, is the output True?
I Circuit satisfiability (SAT):
given a Boolean formula, is there a way to set the inputs so that the
output is True?

The first one is solvable in polynomial time, and the second is NPC, but
the difference appears to be slight.

243 / 278
1. Introduction
(e) Optimization problems and Decision problems
I Most of problems occur naturally as optimization problems,

I but they can also be formulated as decision problems, that is, problems
for which the output is a simple Yes or No answer for each input.

Remarks:
I To simplify discussion, we can consider only decision problems, rather
than optimization problems.
I The optimization problems are at least as hard to solve as the related
decision problems, we have not lost anything essential by doing so.

244 / 278
1. Introduction
(e) Optimization problems and Decision problems
Example 1
Graph coloring: A coloring of a graph G = (V, E) is a mapping
C:V →S
where S is a finite set of “colors”, such that
(u, v) ∈ E ⇒ C(u) 6= C(v)
I optimization problem: given G, determine the smallest number of
colors needed.
I decision problem: given G and a positive integer k, is there a coloring
of G using at most k colors?

245 / 278
1. Introduction
(e) Optimization problems and Decision problems
Example 2.
Hamiltonian cycle: A Hamiltonian cycle is cycle that passes through
every vertex exactly once.

I decision problem: Does a given graph have a Hamiltonian cycle?

I optimization problem: Give a list of vertices of a Hamiltonian cycle.

246 / 278
1. Introduction
(e) Optimization problems and Decision problems
Example 3.
TSP (Traveling Salesperson Problem): given a weighted graph and
an integer k, is there a cycle that visits all vertices exactly once
(Hamiltonian cycle) whose total weight is k or less?

I optimization problem: given a weighted graph, find a minimum

Hamiltonian cycle.
I decision problem: given a weighted graph and an integer k, is there a
Hamiltonian cycle with total weight at most k?

247 / 278
1. Introduction – recap
(a) Tractable and intractable problems
polynomial-boundness: O(nk )
(b) NP-complete problems – informal definition
(c) Reasons to study NPC problems
Practical and theoretical
(d) P and NP examples
difference may appear “only slightly”
(e) Optimization problems and decision problems

248 / 278
2. P and NP
(a) P: formal definition
I An algorithm is said to be polynomial bounded if its worst-case
complexity T (n) is bounded by a polynomial function of the
input size n:
T (n) = O(nk ).

I Polynomial bounded algorithms for LCS, MST, shortest path, ...

I P = the class of decision problems that can be solved in polynomial

time, i.e., they are polynomial bounded

249 / 278
2. P and NP
(b) NP: formal definition
I NP = the class of decision problems that are verifiable in polynomial
time.
i.e., if we were given a “certificate” (= a solution), then we could
verify that whether the certificate (the solution) is correct in
polynomial time.
I Examples:
I Circuit-SAT
I Hamiltonian cycle
I Graph coloring

I NP stands for “Nondeterministic Polynomial time”.

250 / 278
2. P and NP
(c) P = NP ?
I P ⊆ NP
since if a problem is in P, then we can solve it in polynomial time
without even being given a certificate.

I Open problem:9
Does P ⊂ NP or P = NP ?
i.e., whether or not P is a proper subset of NP.

9 [Link]
251 / 278
2. P and NP
(d) P or NP
I The size of the input can change the classification of P or NP.
I Examples:
I Prime-testing problem:

n=10m
O(n) −→ O(10m )

I Knapsack problem

W =10m
O(nW ) −→ O(n · 10m )

I Knowing the effect on complexity of the size of the input is important.

I Unfortunately, even with strong restrictions on the inputs, many NPC
problems are still NPC.
Example: 3-CNF SAT problem10

10 CNF = Conjunctive Normal Form: a sequence of clauses separated by AND (∧)

operator. A clause is a sequence of Boolean varilables separated by the Boolean OR (∨)

operator.
252 / 278
2. P and NP – recap
(a) P: formal definitions
(b) NP: formal definitions
(c) P = NP ?
(d) P or NP
The size of the input can change the classification of P or NP
However, even with strong restrictions on the inputs, many NPC
problems are still NPC.

253 / 278
3. NP-complete
(a) Introduction
I NP-complete (NPC) is the term used to describe decision problems
that are the hardest ones in NP in the following sense:
If there were a polynomial-bounded algorithm for an NPC problem,
then there would be a polynomial-bounded time for each problem
in NP.

254 / 278
3. NP-complete
(b) NPC: formal definition
I Decision problem A is NP-complete (NPC) if

(1) A ∈ NP and
(2) every other problems B in NP is polynomially reducible to A.

If a problem satisfies the property (2), but not necessarily the property (1),
we say the problem is NP-hard.11

11 Note: “NP-hard” does not mean “in NP and hard”. It means “at least as hard as

any problem in NP”. Thus a problem can be NP-hard and not be in NP.
255 / 278
3. NP-complete
(c) Polynomial reduction
I Let A and B be two decision problems, B is polynomially reducible to
A, if there is a poly-time computable transformation T such that
iff
Yes-instance of A ⇐⇒ Yes-instance of B

I Notation: B ≤T A

256 / 278
3. NP-complete
(c) Polynomial reduction
Example:
directed HC ≤T undirected HC

1. Let G = (V, E) be a directed graph.

2. Define the transformation T from the directed G to an undirected
graph G0 = (V 0 , E 0 ) as follows:
I v∈V −→ v 1 , v 2 , v 3 ∈ V 0 and (v 1 , v 2 ), (v 2 , v 3 ) ∈ E 0
I (u, v) ∈ E −→ (u3 , v 1 ) ∈ E 0

3. The transformation T is polynomial-time computable.

257 / 278
3. NP-complete
(c) Polynomial reduction
Example, cont’d:

4. We now show that under the transformation T ,

G has a HC ⇐⇒ G0 has a HC.

5. “⇒” Suppose that G has a directed HC: v1 , v2 , . . . , vn , v1 Then

v11 , v12 , v13 , v21 , v22 , v23 , . . . , vn1 , vn2 , vn3 , v11

is an undirected HC for G0 .

258 / 278
3. NP-complete
(c) Polynomial reduction
Example, cont’d:
6. “⇐”
I Suppose that G0 has an undirected HC, the three vertices v 1 , v 2 , v 3
that correspond to one vertex from G must be traversed consecutively
in the order v 1 , v 2 , v 3 or v 3 , v 2 , v 1 , since v 2 cannot be reached from
any other vertex in G0 .
I Since the other edges in G0 connect vertices with superscripts 1 or 3, if
for any one triple the order of the superscripts is 1-2-3, then the order
is 1-2-3 for all triples. Otherwise, it is 3-2-1 for all triples.
I Therefore, we may assume that the undirected HC of G0 is

vi11 , vi21 , vi31 , vi12 , vi22 , vi32 , . . . , vi1n , vi2n , vi3n , vi11 .

Then vi1 , vi2 , . . . , vin , vi1 is a directed HC for G.

7. Therefore, directed HC ≤T undirected HC. 2

259 / 278
3. NP-complete
(d) Cook’s theorem and examples of known NPC problems
I Cook’s theorem (1971):12
Circuit-SAT is NPC.
I Known NPC problems:
I Graph coloring
I Hamiltonian cycle
I TSP
I Knapsack
I ... see next page for more.

12 First result deomonstrating that a specific problem is NPC.

260 / 278
3. NP-complete
(d) Cook’s theorem and examples of known NPC problems
I Known NPC problems — more
I Subset sum:
Given a positive integer c, and a set S = {s1P , s2 , . . . , sn } of positive
n
P that i=1 si ≥ c. Is there a
integers si for i = 1, 2, . . . , n. Assume
subset J ⊆ {1, 2, . . . , n} such that i∈J si = c.
I Bin packing problem:
Suppose we have an unlimited number of bins, each of capacity 1, and
n objects with sizes s1 , s2 , . . . , sn , where 0 < si ≤ 1. Determine the
smallest number of bins into which objects can be packed.
I Vertex cover problem:
A vertex-cover of an undirected graph G = (V, E) is a subset V 0 ⊆ V
such that if (u, v) ∈ E, then u ∈ V 0 or v ∈ V 0 . The vertex-cover
optimization problem is to find a vertex cover of minimum size.
I Clique problem:
A clique in an undirected graph G = (V, E) is a subset V 0 ⊆ V such
that each pair of V 0 is connected by an edge in E. The clique
optimization problem is to find a clique of maximum size.
261 / 278
3. NP-complete
(e) P, NP and NPC:
I How most theoretical computer scientists view the relationships
among P, NP and NPC:
I Both P and NPC are wholely contained within NP
I P
T
NPC = ∅

NP

P
NPC

262 / 278
3. NP-complete – Recap
(a) Introduction
(b) NPC: formal definition
(c) Polynomial reduction
(d) Cook’s theorem and examples of known NPC problems
(e) P, NP and NPC

263 / 278
4. How to prove a problem is NPC
I The reducibility relation “≤T ” is transitive, i.e,

A ≤T B and B ≤T C imply A ≤T C

I Therefore, to prove that a problem A is NPC, we need to

(1) show that A ∈ NP
(2) choose some known NPC problem B, i.e., B ∈ NPC,
define a polynomial transformation T from B to A
show that B ≤T A

264 / 278
4. How to prove a problem is NPC
I Why sufficient? the logic is as follows:
Since B is NPC, all problems in NP is reducible to B.
Show B is reducible to A.
Then all problems in NP is reducible to A.
Therefore, A is NPC

265 / 278
4. How to prove a problem is NPC
Example 1.
The directed HC is known to be NPC. Use this fact to prove that
Undirected HC is NPC.
Proof:
(1) By direct verification, we know that undirected HC is in NP.
(2)
Step A: Define a transformation T
Step B: Show that

directed HC ≤T undirected HC

I By (1) and (2), we conclude that the undirected HC is NPC.

266 / 278
4. How to prove a problem is NP-complete
Example 1, cont’d:
We now show that

directed HC ≤T undirected HC

Step A
I Define transformation T :
Let G = (V, E) be a directed graph. Define G to the
undirected graph G0 = (V 0 , E 0 ) by the following
transformation T :
I v∈V −→ v 1 , v 2 , v 3 ∈ V 0 and (v 1 , v 2 ), (v 2 , v 3 ) ∈ E 0
I (u, v) ∈ E −→ (u3 , v 1 ) ∈ E 0

I T is polynomial-time computable.

267 / 278
4. How to prove a problem is NP-complete
Example 1, cont’d:

An illustration of such transformation T :

268 / 278
4. How to prove a problem is NPC
Example 1, cont’d
Step B: We show that
G has a HC ⇐⇒ G0 has a HC.
“⇒” Suppose that G has a directed HC: v1 , v2 , . . . , vn , v1 Then

v11 , v12 , v13 , v21 , v22 , v23 , . . . , vn1 , vn2 , vn3 , v11

is an undirected HC for G0 .

269 / 278
4. How to prove a problem is NPC
Example 1, cont’d
Step B: We show that
G has a HC ⇐⇒ G0 has a HC.
“⇒” Suppose that G has a directed HC: v1 , v2 , . . . , vn , v1 Then

v11 , v12 , v13 , v21 , v22 , v23 , . . . , vn1 , vn2 , vn3 , v11

is an undirected HC for G0 .
“⇐” 1. Suppose that G0 has an undirected HC, the three vertices v 1 , v 2 , v 3
that correspond to one vertex from G must be traversed consecutively
in the order v 1 , v 2 , v 3 or v 3 , v 2 , v 1 , since v 2 cannot be reached from
any other vertex in G0 .
2. Since the other edges in G0 connect vertices with superscripts 1 or 3, if
for any one triple the order of the superscripts is 1, 2, 3, then the order
is 1, 2, 3 for all triples. Otherwise, it is 3, 2, 1 for all triples.
3. Therefore, we may assume that the undirected HC of G0 is

vi11 , vi21 , vi31 , vi12 , vi22 , vi32 , . . . , vi1n , vi2n , vi3n , vi11 .

Then vi1 , vi2 , . . . , vin , vi1 is a directed HC for G. 2

269 / 278
4. How to prove a problem is NPC
Example 2: Show that
Subset-Sum ≤T Set-Partition
Since Subset-Sum is known to be NPC, the above reduction implies that
Set-Partition is also NPC.

Subset-Sum decision problem:

Given a positive integer c, and a set S = {s1 , s2 , . . . , sn } of positive
integers si for i = 1, 2, . . . , n. Is there a J ⊆ {1, 2, . . . , n} such
X Xn
that si = c? assume that w = si ≥ c.
i∈J i=1

Set-Partition decision problem:

Given a set S of numbers. XCan S be
Xpartitioned into two sets A
and Ā = S − A such that x= x?
x∈A x∈Ā

270 / 278
4. How to prove a problem is NPC
Example 2, cont’d
X
I Let S be an instance of Subset-Sum with w = si and the target c.
si ∈S
I Define the set S 0 (i.e., the transformation T from S to S 0 ) as follows:

S 0 = S ∪ {u, v}, where u = 2w − c, v = w + c.

I Next to show that

Yes of Subset-Sum of S ⇐⇒ Yes of Set-Partition of S 0

271 / 278
4. How to prove a problem is NPC
Example 2, cont’d
=⇒ Let J ⊆ S and the elements in J sum to c. Then J ∪ {u} sum to 2w.
Note that the elements in J = S − J sum to w − c. Hence, J ∪ {v} also
sums to 2w. Therefore, S 0 can be partioned into J ∪ {u} and J ∪ {v}
where both partitions sum to 2w. Thus, Yes of Subset-Sum transforms to a
Yes of Set-Partition.

272 / 278
4. How to prove a problem is NPC
Example 2, cont’d
⇐= Assume S 0 can be partitioned into two sets, T and T = S 0 − T , such
that X X
x= x. (4)
x∈T x∈T

Since w + u + v = 4w, the sum of the elements in both sets must be equal
to 2w. Therefore, u must be in one set and v must be in the other because
u + v = 3w. Without loss of generality, let u ∈ T . Then
X X X
2w = x=u+ x = 2w − c + x.
x∈T x∈T −u x∈T −u

It implies that X
x=c
x∈T −u

Thus, Yes of Set-Partition transforms to Yes of Subset-Sum. 2

273 / 278
5. How to solve a NPC problem
Example 1: Bin Packing problem
Suppose we have an unlimited number of bins, each of capacity 1,
and n objects with sizes s1 , s2 , . . . , sn , where 0 < si ≤ 1.
I Optimization problem: Determine the smallest number of bins into
which objects can be packed and find an optimal packing.
I Decision problem: Do the objects fit in k bins?

Theorem. Bin Packing problem is NPC

Proof. reduced from the subset sum.

274 / 278
5. How to solve a NP-complete problem
Approximate algorithm for the Bin Packing
I First-fit strategy (greedy):
places an object in the first bin into which it fits.
I Example: Objects = {0.8, 0.5, 0.4, 0.4, 0.3, 0.2, 0.2, 0.2}
I First-fit strategy solution:

B1 B2 B3 B4
0.2
0.2 0.4 0.3
0.8 0.5 0.4 0.2

I Optimal packing:

B1 B2 B3
0.2 0.2
0.2 0.3 0.4
0.8 0.5 0.4

275 / 278
5. How to solve a NP-complete problem
n
X
Theorem. Let S = si .
i=1
1. The optimal number of bins required is at least dSe
2. The number of bins used by the first-fit strategy is never more than
d2Se.

276 / 278
5. How to solve a NP-complete problem
The vertex-cover problem:
I A vertex-cover of an undirected graph G = (V, E) is a subset set of
V 0 ⊆ V such that if (u, v) ∈ E, then u ∈ V 0 (inclusive) or v ∈ V 0 .
I In other words, each vertex “covers” its incident edges, and a vertex
cover for G is a set of vertices that covers all edges in E.
I The size of a vertex cover is the number of vertices in it.
I Decision problem: determine whether a graph has a vertex cover of a
given size k
I Optimization problem: find a vertex cover of minimum size.
I Theorem. The vertex-cover problem is NPC.

277 / 278
5. How to solve a NP-complete problem
The vertex-cover problem:
I An approximate algorithm
C=∅
E0 = E
while E 0 6= ∅
let (u, v) be an arbitrary edge of E 0
C = C ∪ {u, v}
remove from E 0 every edge incident on either u or v.
endwhile
return C
I Theorem. The size of the vertex-cover is no more than twice the size
of an optimal vertex cover.

278 / 278