CS-251 DESIGN & ANALYSIS OF ALGORITHMS

Credit Hours: 3+0

Semester Spring 2025

Course Instructor: Dr. Samra Kanwal

engr.skanwal@gmail.com

Military College of Signals

National University of Science and Technology (NUST)
Department of Computer Software Engineering
Table of Contents

Introduction to Dynamic Programming

Tabulation vs. Memoization
WHAT IS DYNAMIC PROGRAMMING?
01 02 03
Optimization Dynamic vs. Recursive
Problems Greedy Methods Formulas
Dynamic Unlike greedy Dynamic
programming solves methods with programming often
optimization predefined optimal uses recursive
problems requiring procedures, formulas,
minimum or maximum dynamic implemented
results by programming iteratively for
evaluating all explores all efficiency.
possible feasible solutions
solutions. to find the best
one.
 PRINCIPLE OF OPTIMALITY

Sequence of Decisions
The principle states that optimal solutions are achieved through
a sequence of interconnected decisions.

Stage-Wise Decisions
Dynamic programming differs from greedy methods by making
decisions at every stage of the problem-solving process.
 02
TABULATION VS. MEMOIZATION
FIBONACCI SEQUENCE EXAMPLE

0 Recursive Definition
1 Illustrates the recursive
nature of Fibonacci numbers,
where each term is the sum of
the two preceding ones.

0 Inefficient Recursive
Calls
2 Naive recursion leads to
redundant calculations,
significantly increasing time
complexity.
FIBONACCI NUMBERS

• Recall definition of Fibonacci numbers:

F(n) = F(n-1) + F(n-2)

F(0) = 0
F(1) = 1
th
• Computing the n Fibonacci number recursively
(top-down):

F(n)

F(n-1) + F(n-2)

F(n-2) + F(n-3) F(n-3) + F(n-4)

7
MEMOIZATION (TOP-DOWN)

01 02 03

Storing Top-Down
Results Reduced Time Approach
Complexity

Memoization optimizes Storing and reusing Memoization starts

recursive solutions previously computed with the main
by storing results to values dramatically problem and
avoid recomputation. reduces function recursively breaks
calls and execution it down, storing
time. the results along
the way.
TABULATION (BOTTOM-UP)

02

01 03

Iterative Table Bottom-Up Iterative

Filling Approach Function
Tabulation uses loops Tabulation starts Illustrates iterative

to build a table of with base cases and functions with loops

solutions from the iteratively computes to compute the

smallest subproblems solutions for larger fibonacci sequence;

to the larger ones. subproblems. efficient.

EXAMPLE 1: FIBONACCI NUMBERS (CONT.)

Computing the nth Fibonacci number using bottom-up iteration

and recording results:

F(0) = 0
F(1) = 1
F(2) = 1+0 = 1
…
F(n-2) =
F(n-1) =
F(n) = F(n-1) + F(n-2)

Efficiency:
- time
- space 10
MATRIX-CHAIN MULTIPLICATION

Problem: given a sequence 〈A1, A2, …, An〉,

compute the product:
A1 ⋅ A2 ⋅⋅⋅ An

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

11
 MATRIX-CHAIN MULTIPLICATION

◼ In what order should we multiply the matrices?

A1 ⋅ A2 ⋅⋅⋅ An
◼ Parenthesize the product to get the order in which
matrices are multiplied
◼ E.g.: A1 ⋅ A2 ⋅ A3 = ((A1 ⋅ A2) ⋅ A3)
= (A1 ⋅ (A2 ⋅ A3))
◼ Which one of these orderings should we choose?
◼ The order in which we multiply the matrices has a significant
impact on the cost of evaluating the product
12
 EXAMPLE

A1 ⋅ A2 ⋅ A3
◼ A1: 10 x 100
◼ A2: 100 x 5
◼ A3: 5 x 50
1. ((A1 ⋅ A2) ⋅ A3): A1 ⋅ A2 = 10 x 100 x 5 = 5,000 (10 x 5)
((A1 ⋅ A2) ⋅ A3) = 10 x 5 x 50 = 2,500
Total: 7,500 scalar multiplications
2. (A1 ⋅ (A2 ⋅ A3)): A2 ⋅ A3 = 100 x 5 x 50 = 25,000 (100 x 50)
(A1 ⋅ (A2 ⋅ A3)) = 10 x 100 x 50 = 50,000
Total: 75,000 scalar multiplications
one order of magnitude difference!!
13
 MATRIX-CHAIN MULTIPLICATION:
◼PROBLEM
Given a chain of matrices 〈A1, A2, …, An〉,
STATEMENT
where Ai has dimensions pi-1x pi, fully
parenthesize the product A1 ⋅ A2 ⋅⋅⋅ An in a
way that minimizes the number of scalar
multiplications.

A1 ⋅ A2 ⋅⋅⋅ Ai ⋅ Ai+1 ⋅⋅⋅ An

p0 x p 1 p 1 x p 2 pi-1 x pi pi x pi+1 pn-1 x pn

14
WHAT IS THE NUMBER OF POSSIBLE
PARENTHESIZATIONS?

◼Exhaustively checking all possible

parenthesizations is not efficient!
◼It can be shown that the number of
parenthesizations grows exponentially

15
1. THE STRUCTURE OF AN OPTIMAL
PARENTHESIZATION
◼ Notation:
Ai…j = Ai Ai+1 ⋅⋅⋅ Aj, i ≤ j

◼ Suppose that an optimal parenthesization of Ai…j

splits the product between Ak and Ak+1, where i
≤k<j

Ai…j = Ai Ai+1 ⋅⋅⋅ Aj

= Ai Ai+1 ⋅⋅⋅ Ak Ak+1 ⋅⋅⋅ Aj
= Ai…k Ak+1…j
16
OPTIMAL SUBSTRUCTURE
Ai…j = Ai…k Ak+1…j

◼The parenthesization of the “prefix” Ai…k must

be an optimal parentesization
◼If there were a less costly way to parenthesize
Ai…k, we could substitute that one in the
parenthesization of Ai…j and produce a
parenthesization with a lower cost than the
optimum ⇒ contradiction!
◼An optimal solution to an instance of the
matrix-chain multiplication contains within it
optimal solutions to subproblems
17
2. A RECURSIVE SOLUTION
◼Subproblem:

determine the minimum cost of

parenthesizing Ai…j = Ai Ai+1 ⋅⋅⋅ Aj for 1 ≤ i
≤j≤n
◼Let m[i, j] = the minimum number of
multiplications needed to compute Ai…j
◼ full problem (A1..n): m[1, n] 0, for i = 1, 2, …, n

◼ i = j: Ai…i = Ai ⇒ m[i, i] =
18
2. A RECURSIVE SOLUTION
◼Consider the subproblem of parenthesizing
Ai…j = Ai Ai+1 ⋅⋅⋅ Aj for 1 ≤ i ≤ j ≤ n

= Ai…k Ak+1…jpi-1pkp for i ≤ k < j

j

m[i, k] m[k+1,j]
◼Assume that the optimal parenthesization
splits the product Ai Ai+1 ⋅⋅⋅ Aj at k (i ≤ k < j)
m[i, j] =
m[i, k] + m[k+1, j] +
pi-1pkpj
min # of min # of # of multiplications
multiplications multiplications to compute Ai…kAk…j
to compute Ai…k to compute Ak+1…j 19
 2. A RECURSIVE SOLUTION (CONT.)

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

◼We do not know the value of k
◼ There are j – i possible values for k: k = i, i+1, …, j-1
◼Minimizing the cost of parenthesizing the
product Ai Ai+1 ⋅⋅⋅ Aj becomes:
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
i≤k<j

20
3. COMPUTING THE OPTIMAL COSTS

0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
i≤k<j

◼ Computing the optimal solution recursively takes

exponential time! 1 2 3 n
◼ How many subproblems? n
⇒Θ
2
(n )
◼ Parenthesize A i…j
for 1 ≤ i ≤ j ≤ n j
3
◼ One problem for each
2
choice of i and j
1
i 21
3. COMPUTING THE OPTIMAL COSTS (CONT.)

0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
i≤k<j

◼ How do we fill in the tables m[1..n, 1..n]?

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

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

◼ Subproblems’ size is one less than the original size

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

increasing length
22
3. COMPUTING THE OPTIMAL COSTS (CONT.)

0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j

o n
c s
1 2 3 sen fir
d t
n
m[1, n] gives the
optimal
solution to the problem
i≤k<j j
3
◼ Length = 1: i = j, i = 1, 2, …, n
2
◼ Length = 2: j = i + 1, i = 1, 2, …, n-1
Compute rows from bottom to 1
top and from left to right
i 23
 m[2, 2]
EXAMPLE: MIN {M[I, K] + M[K+1, J] +
+ m[3,
PI-1PKP5]
J
}+
p1p2p5 k=2

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

p1p3p5 k=4
m[2, 4] + m[5, 5] +
p1p14p52 3 4 5 6
6
5
• Values m[i, j] depend only
4
j on values that have been
3 previously computed
2
1

i
24
EXAMPLE MIN {M[I, K] + M[K+1, J] + PI-1PKPJ}
Compute A1 ⋅ A2 ⋅ A3 1 2 3
2 2
◼ A1: 10 x 100 (p0 x p1) 3 750 2500 0
1 0 0
◼ A2: 100 x 5 (p1 x p2) 2 500 0
◼ A3: 5 x 50 (p2 x p3) 0
1 0
m[i, i] = 0 for i = 1, 2, 3
m[1, 2] = m[1, 1] + m[2, 2] + p0p1p2 (A1A2)
= 0 + 0 + 10 *100* 5 = 5,000
m[2, 3] = m[2, 2] + m[3, 3] + p1p2p3 (A2A3)
= 0 + 0 + 100 * 5 * 50 = 25,000
m[1, 3] = min m[1, 1] + m[2, 3] + p0p1p3 = 75,000 (A1(A2A3))
m[1, 2] + m[3, 3] + p0p2p3 = 7,500 ((A1A2)A3)
25
MATRIX-CHAIN-ORDER(P)

O(N3)

26