M6: Dynamic Programming & Greed Algorithms

Question 1

Define dynamic programming.

Answer 1

A problem-solving technique that solves complex problems by breaking them into simpler overlapping subproblems.

Stores results of subproblems to avoid redundant computations (memoization or tabulation)

Question 2

Write pseudocode for the Longest Common Subsequence.

Answer 2

Recursive Formula:
c[i][j] = 0 if i == 0 or j == 0
c[i][j] = c[i-1][j-1] + 1 if X[i] == Y[j]
c[i][j] = max(c[i-1][j], c[i][j-1]) otherwise

Base Case:
c[0][j] = 0, c[i][0] = 0

Question 3

Write code for the Longest Common Subsequence.

Answer 3

A Naive recursive implementation of LCS problem

Returns length of LCS for s1[0..m-1], s2[0..n-1]
def lcsRec(s1, s2, m, n):

# Base case: If either string is empty, the length of LCS is 0
if m == 0 or n == 0:
    return 0

# If the last characters of both substrings match
if s1[m - 1] == s2[n - 1]:

    # Include this character in LCS and recur for remaining substrings
    return 1 + lcsRec(s1, s2, m - 1, n - 1)

else:
    # If the last characters do not match
    # Recur for two cases:
    # 1. Exclude the last character of S1 
    # 2. Exclude the last character of S2 
    # Take the maximum of these two recursive calls
    return max(lcsRec(s1, s2, m, n - 1), lcsRec(s1, s2, m - 1, n))

def lcs(s1,s2):
m = len(s1)
n = len(s2)
return lcsRec(s1,s2,m,n)

if __name__ == “__main__”:
s1 = “AGGTAB”
s2 = “GXTXAYB”
print(lcs(s1, s2))

Question 4

Define the 0-1 Knapsack problem.

Answer 4

Given n items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.

Question 5

Write pseudocode for the 0-1 Knapsack problem.

Answer 5

Define: B[i][w] = max benefit for first i items and total weight w

Recursive Formula:
B[0][w] = 0 for all w
B[i][0] = 0 for all i
If w[i] <= w:
B[i][w] = max(B[i-1][w], B[i-1][w - w[i]] + b[i])
Else:
B[i][w] = B[i-1][w]

Question 6

What’s the time complexity for the dynamic programming solution to the 0-1 knapsack problem vs the brute force?

Answer 6

Dynamic Solution: O(n * W)
Brute Force: O(2^(n))

Question 7

What’s the time complexity for the dynamic programming solution to the Longest Common Subsequence (LCS) problem vs the brute force?

Answer 7

Dynamic Solution: O(m * n)
Brute Force: O(n * 2^(m))

Question 8

Write code for the 0-1 knapsack problem.

Answer 8

Returns the maximum value that
# can be put in a knapsack of capacity W
def knapsackRec(W, val, wt, n):

# Base Case
if n == 0 or W == 0:
    return 0

pick = 0

# Pick nth item if it does not exceed the capacity of knapsack
if wt[n - 1] <= W:
    pick = val[n - 1] + knapsackRec(W - wt[n - 1], val, wt, n - 1)

# Don't pick the nth item
notPick = knapsackRec(W, val, wt, n - 1)
 
return max(pick, notPick)

def knapsack(W, val, wt):
n = len(val)
return knapsackRec(W, val, wt, n)

if __name__ == “__main__”:
val = [1, 2, 3]
wt = [4, 5, 1]
W = 4

print(knapsack(W, val, wt))

Question 9

Define a greedy algorithm

Answer 9

An algorithm that makes the locally optimal choice at each step with the hope that this will lead to a globally optimal solution. However, this is not always the case!

Question 10

Define Huffman coding.

Answer 10

Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. Reduces size of data by 20%-90%. Used for .mp3 and .jpg.

Question 11

Explain the Greedy Strategy for the Fractional Knapsack Problem

Answer 11

Pick items with the maximum value per pound, until you cannot fit them into the knapsack.

Running time if sorted: O(n)
Running time if un-sorted: O(nlog(n))