What is the recurrence relation for the Merge Sort algorithm?
Merge Sort divides the array into 2 halves (2T(n/2)) and merges them in linear time (O(n)), solving to O(n log n).
Which of the following problems has a standard dynamic-programming solution?
All three are classic dynamic-programming problems. LCS and Matrix Chain Multiplication have polynomial-time algorithms; the standard O(NW) algorithm for 0/1 Knapsack is pseudo-polynomial because it depends on the numeric capacity W.
What is the time complexity of Bellman-Ford shortest path algorithm on a graph with V vertices and E edges?
Bellman-Ford relaxes all E edges V-1 times, resulting in O(V * E) time complexity, and can detect negative weight cycles.
In Kruskal's MST algorithm, which data structure provides near-constant O($\alpha(V)) time$ for edge union and find operations?
DSU equipped with Path Compression and Union by Rank achieves inverse Ackermann amortized time O($\alpha(V)) per operation$.
In an AVL tree with height h, what is the maximum balance factor allowed for any node?
An AVL tree requires the balance factor of every node, defined as height(left) - height(right), to be -1, 0, or +1. Therefore, the maximum allowed absolute balance factor is 1.