Dynamic Programming

Question 1

What are the two basics of dynamic programming?

Answer 1

Optimal substructure and overlapping subproblems.

Question 2

Explain what is meant by optimal substructure.

Answer 2

An optimal substructure is a smaller problem which we have an optimal solution for. These smaller problems are later on merged or used in order to solve our bigger problem.

Question 3

Explain what is meant by overlapping subproblems.

Answer 3

Overlapping subproblems are subproblems which we can use to optimally solve more than one bigger problem.

Question 4

List 5 algorithms which makes use of optimal substructure.

Answer 4

Sorting, reversing a string, merging two arrays, shortest paths, minimum spanning tree.

Question 5

One mathematical example that makes use of overlapping subproblems.

Answer 5

Fibonacci.

Question 6

Difference between dynamic programming and divide-and-conquer algorithms.

Answer 6

Dynamic programming makes use of both optimal substructures and overlapping subproblems while divide-and-conquer algorithms only use optimal substructures.

Question 7

List the basic dynamic programming strategies.

Answer 7

Bottom up dynamic programming, directed acyclic graph and topological sort, and top down dynamic programming.

Question 8

Explain the bottom up dynamic programming.

Answer 8

Start at the lowest subproblems and solve them. Recurse a step upwards by combining the smaller problems. Continue to recurse until you reach the root. Solve the root problem.

Question 9

Explain the directed acyclic graph and topological sort approach.

Answer 9

We can picture a dynamic programming problem to be a directed acyclic graph and therefore we can come up with a topological way of sorting the subproblems. Once we have the problems sorted topologically, we start at the last element and continue to recurse from the end to the front.

Question 10

Explain the top down dynamic programming.

Answer 10

Start at the root and recurse downwards. Continue to recurse until we have reach the base case (smallest subproblem). Now solve the smallest subproblems and memoize (important for overlapping subproblems).

Question 11

Explain the algorithm to solve Longest Increasing Subsequence for an input array of integers.

Answer 11

There are two strategies:

1. Use DAG and topo-sort. Nodes represent the integers in the array and are sorted based on its order in the input array. A directed edge connect a node to another node if the other node is strictly larger than it and is to the right of this node. Find longest path for each node. Return the longest path’s size of the node with the greatest longest path.
2. Solve subproblems. The longest subsequence for the first element is 1. The next element’s longest subsequence is the max longest subsequence before it plus 1 since we’re on the next element now.

Question 12

Explain the algorithm to solve Prize Collecting problem given an input directed, weighted graph G and k, max number of edges to cross.

Answer 12

There are two strategies:

1. Use DAG and topo-sort. Create a directed acyclic graph using G. Make k copies of all the vertices in G where the vertices in each layer are connected to the next layer if there is an edge corresponding to this connection in G. Find the longest path in this DAG. We can create a super node which connects to all of the vertices in the first layer. Then we perform our longest path algorithm on this super node. O(kE)
2. Solve subproblems. Take P[v, k] = maximum prize that you can collect starting at v and taking EXACTLY k steps. The subproblem of this is P[w, k - 1] where w is the neighbours of v. We. can take the maximum from all of the neighbours plus the weight of the edge that connects the respective neighbour to v. This leaves us with the correct answer to P[v, k]. Running time: there are k rows and E edges for each row (if we picture it using a table approach). This means that to solve everything, we need O(kE).

Question 13

Explain the algorithm to solve Vertex Cover On A Tree problem for an undirected, unweighted tree.

Answer 13

First, identify the subproblems of the graph. Given a root V, we can either to choose to cover V or not. We can designate S[V, 0] as not covering V and S[V, 1] as covering V. Realise that if we do not cover V, that means we have to cover ALL its children. And if we cover V, we may or may not cover ALL its children. Our subproblem is the children. If we say that S[W, 0] and S[W, 1] is the problem for our children, we can easily solve the problem for S[V, 0] and S[V, 1].
For S[V, 0]:
This means that we have to cover all of the children. S[V, 0] = S[W1, 1] + S[W2, 1] + …
For S[V, 1]:
This means that we can either cover or uncover the children, depending which costs lesser.
S[V, 1] = 1 + min {S[W1, 0], S[W1, 1]} + min {S[W2, 0], S[W2, 1]} + …
Running time: O(V) because there are V - 1 edges in the tree and each edge is explored once. Each subproblem involves exploring children edges.

Question 14

Explain the algorithm to solve All Pairs Shortest Paths.

Answer 14

We can run Dijkstra on every pair of vertices and then whenever a query is asked, we can just return from the array we store our distances between all pairs of vertices but this takes O(VElogV).
Dynamic Programming Way:
If P is the shortest path (u to v to w), then P contains the shortest path from u to v and from v to w.
Let S[v, w, P] be the shortest path from v to w that only uses intermediate notes only in the set P, where set P can be an empty set.
S[v, w, P8] = min {S[v, w, P7], S[v, 8, P7] + S[8, w, P7]]