Quiz · Hard
Master theorem, dynamic programming, negative edges, MST variants, quickselect and heuristic search at exam difficulty.
Solve T(n) = 2T(n/2) + n² using the master theorem.

Θ(n log n)
Θ(n² log n)
Θ(n²)
Θ(n³)
n^{log₂2} = n is polynomially smaller than f(n) = n², so case 3: Θ(n²). Image of the theorem: Ahmadnnb, CC BY-SA 4.0, via Wikimedia Commons.
Solve T(n) = 3T(n/2) + n.
Θ(n^(log₂3)) ≈ Θ(n^1.585)
Θ(n log n)
Θ(n²)
Θ(n)
n^{log₂3} ≈ n^1.585 grows faster than f(n) = n, so case 1 gives Θ(n^{log₂ 3}). This is Karatsuba multiplication.
Solve T(n) = 4T(n/2) + n² log n using the Master theorem. (Hint: does it fit the three basic cases?)
Θ(n²)
Θ(n² log n)
Θ(n² log² n)
The basic master theorem does not apply directly
Here n^{log₂4} = n² and f(n) = n² log n is larger by only a log factor, not polynomially. It falls between cases 2 and 3, so the basic theorem does not apply. The extended version gives Θ(n² log² n).
The coin system is {1, 3, 4} and the target amount is 6. What is the minimum number of coins, and what does greedy give?
Minimum 3, greedy 2
Minimum 2, greedy 3
Both 2
Both 3
The optimum is 3 + 3 = two coins. Greedy takes 4 first and then 1 + 1, for three coins. This is why coin change needs DP unless the system is canonical.
The longest common subsequence of 'ABCBDAB' and 'BDCABA' has length:
3
5
4
6
One LCS is 'BCBA' (length 4). Several LCSs of length 4 exist, e.g. 'BDAB'; none has length 5.
What is the edit distance between 'kitten' and 'sitting'?
3
2
4
5
Substitute k → s, substitute e → i, insert g at the end: 3 operations.
Running Bellman-Ford on a graph, a V-th relaxation pass still improves some distance. What does that mean?
The graph is disconnected
The graph is a DAG
The source has no outgoing edges
A negative cycle is reachable from the source
Without negative cycles all shortest paths have at most V − 1 edges, so V − 1 passes are enough. Further improvement signals a negative cycle.
A directed graph has edges 0→1, 1→2, 2→0, 2→3. Which statement is true?
It has a valid topological order
It contains a cycle, so no topological order exists
Kahn's algorithm outputs 0, 1, 2, 3
It is a tree
0 → 1 → 2 → 0 is a cycle, so no topological ordering exists. Kahn's algorithm would find no vertex with in-degree zero among 0, 1, 2 and stop early.
You must find the k-th smallest of n unsorted numbers in expected O(n). Which algorithm?
Heap sort then index
Merge sort then index
Quickselect
Binary search
Quickselect partitions around a pivot and recurses on only one side: expected O(n). Sorting would cost O(n log n).
Prim's algorithm using an adjacency matrix and no heap has which running time?
O(V²)
O(E log V)
O(V + E)
O(V³)
Each of V steps scans all vertices to find the cheapest crossing edge, which is O(V²). With a binary heap and adjacency lists it is O(E log V).
What is the time complexity of Floyd-Warshall for all-pairs shortest paths?
O(V²)
O(V² log V)
O(VE log V)
O(V³)
Three nested loops over k, i and j give O(V³).
An algorithm has T(n) = T(n − 1) + n. What is its complexity?
O(n)
O(n²)
O(n log n)
O(2ⁿ)
Unrolling gives n + (n−1) + … + 1 = n(n+1)/2 = Θ(n²). Master theorem does not apply to this subtract-one form.
Which of these is NOT a requirement for a greedy algorithm to give an optimal answer?
Greedy-choice property
Optimal substructure
Overlapping subproblems
A proof, often by exchange argument
Overlapping subproblems characterize dynamic programming. Greedy needs the greedy-choice property and optimal substructure, usually proved with an exchange argument.
Why does the A* algorithm need an admissible heuristic?
So it never overestimates the remaining cost and the path found is optimal
To run in O(1)
To work with negative weights
So it can use BFS
If h(n) never exceeds the true remaining cost, A* cannot skip a cheaper route. An overestimating heuristic can make it return a suboptimal path.
What is the main trade-off between top-down memoization and bottom-up tabulation?
Different asymptotic time
Memoization needs no extra memory
Tabulation cannot handle two-dimensional tables
Recursion overhead and depth limits versus computing only the needed states
Memoization only computes the states that are actually reached but uses recursion (stack depth limits). Tabulation fills every state in a chosen order with no recursion. Both have the same asymptotic time for full tables.
In the Huffman tree with total frequency 36 (the picture), the fixed-length 4-bit code uses 144 bits for the whole text. How many bits does the Huffman code use?

108
135
120
144
Sum of frequency × code length over the 16 leaves: 135 bits, saving 9 bits over the fixed-length code. Frequent symbols (space 7, e 4, a 4) have 3-bit codes.