What is the maximum number of nodes at level L in a binary tree (where root is at level 0)?
At level 0 there is $2^0$ = 1 node; level 1 has $2^1$ = 2; and level L has at most $2^L$ nodes.
What is the worst-case space complexity of storing a sparse graph with V vertices and E edges using an Adjacency Matrix?
An Adjacency Matrix requires a 2D V x V array regardless of the number of edges E, resulting in O($V^2)$ space complexity.
Which tree transformation is performed when an AVL tree node has a Left-Right (LR) imbalance?
An LR imbalance is fixed by first performing a Left Rotation on the left child, turning it into an LL imbalance, followed by a Right Rotation on the parent node.
In the 0/1 Knapsack problem with N items and weight capacity W, what is the Dynamic Programming time complexity?
The standard DP table has dimensions (N+1) x (W+1) with state transition dp[i][w] computed in O(1), giving O(N * W) pseudo-polynomial time.
What is Kadane's Algorithm used for?
Kadane's algorithm computes the maximum contiguous subarray sum in a 1D array in single-pass O(N) time using dynamic programming.