Dynamic Programming

• Dynamic Programming is ano algorithmic approach for efficiently solving problems with repeates sub-problems by storing and re-using their solutions.

• Main idea:

  1. Set up a recurrence relating a solution to a larger instance to solutions of some smaller instances
  2. Solve the smaller instances
  3. Record solutions in a table
  4. Extract solution to the initial instance from that table

• Example: Fibonacci numbers

  

Binomial Coefficient

• Binomial Coefficients are coefficients of the binomial formula $(a+b)^n = C(n, 0)a^nb^0+...+C(n,k)a^{n-k}b^k + ... + C(n, m)a^0b^n$

• Recurrence: $C(n,k) = C(n-1, k) + C(n-1, k-1) \text{ fot n>k>0} \\ C(n, 0) = 1, C(n, n) = 1 \text{ for n} \ge 0$

• The value of C(n, k) can be computed by filling a table

  

  PROCEDURE Binomial(n, k)
  	for i <- 0 to n do:
  		for j <- 0 to min(i, k) do:
  			if j=0 or j=1:
  				C[i, j] <- 1
  			else C[i, j] = C[i-1, j] + C[i-1, j-1]
  		return C[n, k]
  

• Time and space complexity are both O(nk)

Knapsack Problem

• To design a dynamic programming algorithm, we need to derive a recurrence relation that expresses a solution to an instance of the knapsack problem in terms of solutions to its smaller sub-instances.

• Consider the smaller knapsack problem where the number of items is i (i≤n), and the knapsack capacity is j (j≤W)

  • $F(i, j) = max\{F(i-1,j), v_i+F(i-1, j-w_i)\}, \text { if } j-w_i \ge 0 \\ F(i, j) = F(i-1,j), \text { if } j-w_i \lt 0$

• See the table thing in slides

• Space and time complexity: O(nW)

• Time to compose optimal solution: O(n)

  PROCEDURE MFKnapsack(i, j)
  	// memory function dynamic programming
  	// i indicates number of items, and j indicates knapsack capacity
  	
  	if F[i, j] < 0:
  		if j < Weights[i]:
  			value <- MFKnapsack(i-1, j)
  		else:
  			value <- max(MFKnapsack(i-1, j), Values[i]+MFKnapsack(i-1, j-Weights[i]))
  		F[i, j] <- value
  	return F[i, j]
  

Warshall’s Algorithm

• Used to compute the transitive closure of a relation.

• Transitive closure indicates if there is a path between every pair of vertices in the graph.

• Transitive closure of G is a new directed graph G* = (V, E*) such that there is an edge (u, v) in E* if and only if there is a path from vertex u to vertex v in the original graph G.

• Warshall’s algorithm builds the transitive closure (T) through a sequence of n matrices, starting with the adjacency matrix $R^{(0)}$ = A and progressing to $R^{(n)} = T$. Each intermediate matrix $R^{(k)}$ indicates the rachability between vertices i and j using only the first k vertices as potential intermediate stops on the path. In the kth step, $R^{(k)}_{[i, j]}$ = 1 if there is a path from i to k, and then from k to j. Otherwise, it retains the value from the previous step.