Part A: Difference between Dynamic Programming and Memoization

Aspect	Dynamic Programming (DP)	Memoization
Approach	Bottom-up approach	Top-down approach
Direction	Solves smaller subproblems first, builds up to larger ones	Starts from the main problem, breaks down recursively
Table Filling	Fills the entire table iteratively	Fills table entries only when needed (on demand)
Recursion	No recursion; uses iteration (loops)	Uses recursion with caching
Efficiency	May solve subproblems that are not needed	Solves only required subproblems
Space	Uses a table/array (iterative)	Uses a table/array + recursion stack
Control	Programmer controls the order of computation	Order determined by recursive calls
Overhead	No function call overhead	Has recursive function call overhead

---

Part B: Floyd-Warshall Algorithm — Shortest Path Between Every Pair

Edges from the graph:

• A → B = 4
• B → A = 1
• B → C = 2
• A → C = 7
• C → A = 6

Initial Distance Matrix ($D^0$):

Using nodes: A, B, C (indexed as 1, 2, 3)

$$D^0 = \begin{bmatrix} 0 & 4 & 7 \\ 1 & 0 & 2 \\ 6 & \infty & 0 \end{bmatrix}$$

Floyd-Warshall Formula:

$$D^k[i][j] = \min(D^{k-1}[i][j], \; D^{k-1}[i][k] + D^{k-1}[k][j])$$

---

Iteration k = 1 (Intermediate vertex: A)

For each pair (i, j), check if going through A is shorter:

• $D^1[2][3] = \min(D^0[2][3], \; D^0[2][1] + D^0[1][3]) = \min(2, \; 1+7) = \min(2, 8) = 2$
• $D^1[3][2] = \min(D^0[3][2], \; D^0[3][1] + D^0[1][2]) = \min(\infty, \; 6+4) = 10$
• $D^1[3][1] = \min(6, \; 6+0) = 6$ (no change)
• $D^1[2][1] = \min(1, \; 1+0) = 1$ (no change)

$$D^1 = \begin{bmatrix} 0 & 4 & 7 \\ 1 & 0 & 2 \\ 6 & 10 & 0 \end{bmatrix}$$

---

Iteration k = 2 (Intermediate vertex: B)

• $D^2[1][3] = \min(D^1[1][3], \; D^1[1][2] + D^1[2][3]) = \min(7, \; 4+2) = \min(7, 6) = 6$
• $D^2[3][1] = \min(D^1[3][1], \; D^1[3][2] + D^1[2][1]) = \min(6, \; 10+1) = \min(6, 11) = 6$
• $D^2[1][2] = \min(4, \; 4+0) = 4$ (no change)
• $D^2[3][2] = \min(10, \; 10+0) = 10$ (no change)

$$D^2 = \begin{bmatrix} 0 & 4 & 6 \\ 1 & 0 & 2 \\ 6 & 10 & 0 \end{bmatrix}$$

---

Iteration k = 3 (Intermediate vertex: C)

• $D^3[1][2] = \min(D^2[1][2], \; D^2[1][3] + D^2[3][2]) = \min(4, \; 6+10) = \min(4, 16) = 4$
• $D^3[2][1] = \min(D^2[2][1], \; D^2[2][3] + D^2[3][1]) = \min(1, \; 2+6) = \min(1, 8) = 1$
• $D^3[1][3] = \min(6, \; 6+0) = 6$ (no change)
• $D^3[3][2] = \min(10, \; 0+10) = 10$ (no change)

$$D^3 = \begin{bmatrix} 0 & 4 & 6 \\ 1 & 0 & 2 \\ 6 & 10 & 0 \end{bmatrix}$$

---

Final Shortest Path Matrix

$$D = \begin{bmatrix} 0 & 4 & 6 \\ 1 & 0 & 2 \\ 6 & 10 & 0 \end{bmatrix}$$

From\To	A	B	C
A	0	4	6
B	1	0	2
C	6	10	0

---

Conclusion: The Floyd-Warshall algorithm computes all-pairs shortest paths in $O(n^3)$ time using dynamic programming by systematically considering each vertex as an intermediate node.