Week 3 (Dynamic Programming)

Question 1

How does Dynamic Programming work?

Answer 1

Dynamic programming builds a solution using sub-problems and reduces recursive calls by storing previously calculated values in an array.

Question 2

What is memorisation of recursion?

Answer 2

Where we store each value in an array when it is first found to read later, reducing the number of recursions

Question 3

What are the steps for any dynamic programming problem?

Answer 3

1) Explain what is being stored in the array / table
2) State the base case and final product
3) Explain the recurrence (correctness) and how it is built consistently
4) Explain computation for each entry and overall running time which is entries x computational cost

Question 4

How do we solve the weighted interval scheduling problem using dynamic programming?

Answer 4

• Order request in increasing finish time (O(nlogn))
• For each request j, we define Last(j) to be the last compatible request with j
• M[j] = value of the set of requests of maximum weight chosen for the sub-instance containing requests {1,…,j}
• Base case: M[1] = weight(1), final case: M[n]
• M[j] = max{weight(j) + M[last(j)]; M[j-1]}
• M[j] operations are constant time, two lookups, one max, one addition
  Overall complexity is O(nlogn)+O(n)

Question 5

What is the Bellman-Ford algorithm using dynamic programming?

Answer 5

We maintain an n ⇒ n table indexed by 0 <= i <= (n - 1) and v ∈ V where OPT[i, v] stores the length of shortest s -> v path which uses at most i edges.
Define OPT[0, s] = 0 and OPT[0, v] = infinity for each v ∈ V, v != s
for i = 1, 2, . . . , n - 1 do
for each v ∈ V do
OPT[i, v] = min{OPT[i - 1, v] , min w∈V (length(w, v) + OPT[i - 1, w])}
end for
end for
return OPT[n - 1, v] for each v ∈ V

Running time = O(n^2) entries x O(n) min and add computations => O(n^3) total

Question 6

Why cant we convert all edge-lengths to be non-negative for shortest path problem?

Answer 6

Adding a large positive constant can change the identity of the shortest path

Question 7

What is the theorem for shortest path?

Answer 7

For any two vertices s and t, the shortest s->t path has at most n-1 edges

Proof: if a vertex x repeats on a shortest path P with fewest edges, delete x->x. This decreases the number of edges but the length cannot due to no negative cycles

Question 8

What do we assume with the Bellman-Ford algorithm?

Answer 8

We assume there are no negative cycles

Question 9

What is the subset problem?

Answer 9

Given a set (1,…,n} of n items with weights Weight(1),…,Weight(n) and a bound W, find a set S of items such that ∑ Weight(i) is maximised subject to the constraint ∑ Weight(i) <= W

Question 10

What is the dynamic programming algorithm for subset problem?

Answer 10

OPT[i] denotes the max weight of choosing items from {1,..,i} such that ∑ weight(i) is maximised
Base case: OPT[1] = Weight(1) if Weight(1) <= W, else 0
Recurrence = OPT[i,z] = max{OPT[i-1, z]; weight(i) + OPT[i-1,z-weight(i)]}
OPT has O(n.W) entries, filling up the table looks up two existing entries and other constant time operations.
Running time = O(n.W)