Department of Computer Science & Engineering

Unit-2:
Dynamic Programming
and Greedy Method
DAA
Nupur Choudhary
Dynamic Programming (DP)

Dynamic Programming is an algorithmic technique for solving problems with overlapping

subproblems and optimal substructure by breaking them down into simpler subproblems and
storing their solutions to avoid recomputation.

Key Features:
• Breaks problem into smaller subproblems.
• Uses memoization or tabulation to store results.
• Guarantees an optimal solution if problem has optimal substructure.
• Usually slower but more accurate than greedy algorithms.
• Suitable for problems like 0/1 knapsack, LCS, matrix chain multiplication.

Algorithmic Pattern:
1. Identify subproblems.
2. Define recursion relation or state transition.
3. Solve subproblems bottom-up or top-down with memoization.
4. Use stored results to solve bigger problems.
Greedy Method

Greedy algorithms construct a solution by choosing the locally optimal option at each step, hoping
to find a global optimum.

Key Features:
• Makes best (greedy) choice at each step.
• Does not reconsider choices once made.
• Usually faster and simpler but does not guarantee optimality for all problems.
• Effective when problems have the greedy choice property and optimal substructure.
• Suitable for problems like fractional knapsack, Huffman coding, and minimum spanning tree.

Algorithmic Pattern:
1. Sort elements based on a criterion (e.g., ratio, frequency).
2. Iteratively pick the best available choice.
3. Continue until the problem is solved or constraints are met.
Huffman Tree Construction

Concept:
Huffman coding is a greedy algorithm for lossless data compression. It builds an optimal
prefix code based on symbol frequencies.

Algorithm:
1. Create a leaf node for each symbol and build a min-heap of all nodes based on
frequencies.
2. Extract two nodes with the lowest frequencies.
3. Create a new internal node with frequency equal to the sum of the two nodes.
4. Insert the new node back into the min-heap.
5. Repeat until only one node (the root) remains.
Algorithm:
BuildHuffmanTree(symbols, freq):
Q = MinHeap of nodes with (symbol, freq)
while Q.size > 1:
left = Q.extractMin()
right = Q.extractMin()
merged = Node(freq = left.freq + right.freq)
merged.left = left
merged.right = right
Q.insert(merged)
return Q.extractMin() # root
Knapsack Problem

Fractional Knapsack Problem (Greedy)

Concept:
Take items with the best value-to-weight ratio first. Items can be broken to fill the
knapsack.

Algorithm:
1. Calculate value/weight ratio for each item.
2. Sort items descending by ratio.
3. Take items fully until capacity is reached, then take fractional part of next item.
Algorithm:
FractionalKnapsack(items, capacity):
for each item in items:
compute ratio = value/weight
sort items by ratio descending
totalValue = 0
for item in items:
if capacity >= item.weight:
capacity -= item.weight
totalValue += item.value
else:
totalValue += item.value * (capacity / item.weight)
break
return totalValue
0/1 Knapsack Problem (Dynamic Programming)
Concept:
Each item can either be included or excluded fully.

Algorithm:
1. Use a 2D DP table where:
2. dp[i][w]dp[i][w] = max value using first i items with capacity w.

Recurrence:
Algorithm:

ZeroOneKnapsack(values, weights, n, W):

create dp[n+1][W+1] initialized to 0
for i in 1 to n:
for w in 1 to W:
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
Longest Common Subsequence (Dynamic Programming)
Concept:
Find longest sequence in common between two strings (not necessarily contiguous).

Algorithm:
Let strings be X and Y of lengths m, n.
Algorithm:

LCS(X, Y):
m = length of X
n = length of Y
create LCS[m+1][n+1] initialized to 0
for i=1 to m:
for j=1 to n:
if X[i-1] == Y[j-1]:
LCS[i][j] = LCS[i-1][j-1] +1
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
return LCS[m][n]
Matrix Chain Multiplication (Dynamic Programming)
Concept:
Find optimal parenthesization to minimize scalar multiplications.

Algorithm:
Let matrix dimensions be p0,p1,...,pnp0,p1,...,pn.
Algorithm:

MatrixChainOrder(p):
n = length(p) - 1
create m[n+1][n+1] initialized to 0
for length = 2 to n:
for i = 1 to n-length+1:
j = i + length - 1
m[i][j] = +∞
for k = i to j-1:
cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
if cost < m[i][j]:
m[i][j] = cost
return m[1][n]
Backtracking: 4-Queen Problem
Concept:
Place 4 queens on 4x4 board so no two attack.

Algorithm:
1. Place queen in first row, first column.
2. For next rows, place queen in a safe column (no attack).
3. If no safe position, backtrack.
Algorithm:

solveNQueen(board, row):
if row >= N:
print(board) # solution found
return True
for col in 0 to N-1:
if isSafe(board, row, col):
board[row][col] = 1
if solveNQueen(board, row + 1):
return True
board[row][col] = 0 # backtrack
return False
Branch and Bound
Concept:
Systematic search with bounding to prune suboptimal branches.

Algorithm Steps:
1. Initialize queue with root node representing no decisions.
2. While queue not empty:
• Extract node.
• If it can lead to better solution, branch into subproblems.
• Calculate bounds to prune.
3. Select best feasible solution found.

Example:
Used in knapsack, traveling salesperson, etc.