CSC645 – ALGORITHM ANALYSIS
& DESIGN
CHAPTER 4.4 – Algorithm Design Technique (ADT): DYNAMIC
PROGRAMMING
Nur Azmina Mohamad Zamani
Chapter Overview
Introduction to Dynamic Programming
Transitive Closure
Warshall’s Algorithm
All-pairs Shortest Path
Floyd’s Algorithm
Coin-Changing Problem
Knapsack Problem
Dynamic Programming
Dynamic Programming is a general algorithm design
technique for solving problems defined by recurrences with
overlapping subproblems.
Main idea:
set up a recurrence relating a solution to a larger instance to
solutions of some smaller instances
solve smaller instances once
record solutions in a table
extract solution to the initial instance from that table
Similarity between Dynamic Programming and Brute Force is
that both needs to go through all possible solution.
Dynamic Programming is the intelligent version of Brute
Force.
Transitive Closure:
Warshall’s Algorithm
The transitive closure of a directed graph with n vertices
can be defined as the n-by-n boolean matrix T = {tij}, in
which the element in the ith row (1 ≤ i ≤ n) and the jth
column (1 ≤ j ≤ n) is 1 if there exists a nontrivial directed
path from the ith vertex to the jth vertex; otherwise, tij is
0.
Recurrence relating elements R(k) to elements of
R(k-1) is:
R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j])
It implies the following rules for generating R(k)
from R(k-1):
Time efficiency: Θ(n3)
Rule 1 If an element in row i and column j is 1 in R(k-1),
it remains 1 in R(k) Space efficiency: Matrices can be written
over their predecessors
Rule 2 If an element in row i and column j is 0 in R(k-1),
it has to be changed to 1 in R(k) if and only if
the element in its row i and column k and the
element in its column j and row k are
both 1’s in R(k-1)
Transitive Closure: Warshall’s
Algorithm (EXAMPLE)
3
1
4
2
All-Pairs Shortest
Path: Floyd’s
Algorithm
Problem: In a weighted
(di)graph, find shortest paths
between every pair of
vertices.
Same idea: construct solution Time efficiency: Θ(n3)
through series of matrices
D(0), …,D (n) using increasing Space efficiency: Matrices can be written
subsets of the vertices over their predecessors
allowed as intermediate.
All-Pairs Shortest Path: Floyd’s
Algorithm (EXAMPLE)
2
1 2
3 6 7
3 1 4
Change-making Problem
If Amount >= Coin EXAMPLE:
Then Amount =
12
change[Amount] = change[Amount] +
Coin = 1, 2,
change[Amount-Coin]
5
change[Amount]
COI
0 1 2 3 4 5 6 7 8 9 10 11 12
N
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4 4 5 5 6 6 7
5 1 1 2 2 3 4 5 6 7 8 10 11 13
Reference video:
[Link]
Dynamic Programming: Knapsack
Problem
Given n items of
integer weights: w1 w2 … w n
values: v1 v2 … v n
a knapsack of integer capacity W
Find most valuable subset of the items that fit into the
knapsack
The recurrence formula to compute the problem is as
follows:
Dynamic Programming: Knapsack
Problem (EXAMPLE)
MAX CAPACITY = 5
Item Weight Value
1 2 3
5 7 ANSWER:
2 3 4 Item 1 and Item 2 are selected
3 4 5 with the total weight of 5 and
4 5 6 value of 7.
CAPACITY
0 1 2 3 4 5
0 0 0 0 0 0 0
Value same? No – Item 1 TAKEN (2 –
1 0 0 3 2 =30) 3 3
ITEM
2 0 0 3 4 4 7 Value same? No – Item 2 TAKEN (5 – 3
= 2)
3 0 0 3 4 5 7 Value same? Yes – Item 3 NOT
taken same? Yes – Item 4 NOT taken
Value
4 0 0 3 4 5 7
Reference
A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd
ed., Ch. 8 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All
Rights Reserved.
EXERCISES