What is the cost recurrence for Edit Distance E[i][j] when S1[i-1] != S2[j-1]?
E[i-1][j] is delete, E[i][j-1] is insert, E[i-1][j-1] is replace. We take 1 + min of the three.
What is the space complexity of standard Edit Distance DP table for strings of length m and n?
The full table size is (m+1) x (n+1) = O(m * n) space.
Which algorithm solves Single-Source Shortest Paths on arbitrary graphs (including negative edge weights) in O(V * E) time?
Bellman-Ford uses Dynamic Programming / Edge Relaxation across V-1 passes.
How many iterations of edge relaxation are performed in the main loop of Bellman-Ford for V vertices?
Shortest simple paths contain at most V-1 edges, so V-1 passes suffice.
In Floyd-Warshall algorithm, what is the outer loop variable k representing?
k iterates from 1 to V, incrementally allowing vertex k as an intermediate node.