Skip to main content

Quiz

Twenty questions total: fifteen on this module, five interleaved from semester 1 (probability, asymptotics, proof technique). Answer from memory first; remediate against the tiers at the bottom.

Current Module (15)​

1. Red-Black invariants​

List the five red-black invariants. Which single invariant, together with the root being black, forces height to be O(log n)?

2. Rotations​

Starting from a BST with nodes [10, 20, 30] arranged as a right-leaning zig (10 root, 20 right child, 30 right-right grandchild), show the tree after a left rotation about 10. State how many pointers are updated.

3. AVL balance factor​

Define the AVL balance factor bf(x) = h(x.right) - h(x.left). If after insert a node has bf = +2 and its right child has bf = -1, which rotation pattern fixes it: single or double?

4. Skip list height​

Show that the expected height of a skip list built with p = 1/2 and n keys is O(log n). State the argument, not just the result.

5. Union-find naive cost​

A sequence of n-1 unions on initially singleton sets using the linked-list representation without union by rank has what worst-case total cost? Give both the count and the asymptotic class.

6. Path compression derivation​

Given union by rank plus path compression, state the amortized cost per operation and the function class that governs it. Name the function and give its value at n = 2^65536.

7. Kruskal correctness​

Explain in two sentences why Kruskal's MST algorithm is correct. Which union-find property does the cycle-avoidance check rely on?

8. Binomial heap insert​

Starting from an empty binomial heap, insert 8 keys one at a time. After all 8 inserts, what is the resulting forest structure?

9. Fibonacci-heap potential​

Write the Fibonacci-heap potential function Phi. Compute Delta Phi for an insert that adds one root to a heap with t roots and m marks.

10. Amortized decrease-key​

Explain why decrease-key in a Fibonacci heap is O(1) amortized but not O(1) worst-case. Which operation absorbs the worst-case spike?

11. Aggregate method - dynamic array (derivation)​

A dynamic array supports append with doubling resize. Use the aggregate method to show the amortized cost of append is O(1). Show:

  1. the total cost T(n) for the first n appends
  2. the amortized cost T(n) / n
  3. why a growth factor of 1 (constant-size increment) fails the same argument

12. Accounting method - stack with multipop​

A stack supports push, pop, multipop(k) (pop up to k items). Using the accounting method, assign a charge to push that pays for future pop and multipop work. Show that an arbitrary sequence of n operations costs O(n) total.

13. Potential method - two-stack queue (derivation)​

A queue is implemented with two stacks In and Out. enqueue pushes onto In; dequeue pops from Out if non-empty, otherwise moves every element from In to Out then pops. Let Phi = |In|. Derive the amortized cost for both operations using amortized_i = actual_i + Delta Phi_i, and conclude that n operations cost O(n) total.

14. Bloom filter sizing​

A service needs a Bloom filter for n = 1,000,000 keys at target false-positive rate p = 0.01. Compute m (bit array size) and k (optimal hash count), using m = -n ln(p) / (ln 2)^2 and k = (m/n) ln 2. Round to sensible integers.

15. Segment vs Fenwick tree​

A problem requires both point update and range max-query. Which of segment tree and Fenwick tree is suitable, and why is the other one not?

Interleaved from Semester 1 (5)​

16. Asymptotics refresher​

Rank by asymptotic growth: alpha(n), log* n, log log n, log n. Where does alpha(n) sit for any input you will ever run?

17. Recurrence​

Solve T(n) = 2 T(n/2) + O(n) by recursion tree or master theorem. How does this bound tell you about the cost of a single segment-tree update that touches O(log n) nodes?

18. Probability - expected skip-list height​

A skip list assigns node level L by flipping coins with P(L >= k) = 2^{-k}. Show that E[max_{i in [n]} L_i] = O(log n) using the union bound.

19. Proof-technique​

State whether the following is a valid argument: "On inputs of size n, operation A costs at most c n^2 for some c > 0; therefore operation A is Theta(n^2)." If invalid, fix it with the correct asymptotic symbol.

20. Discrete - binomial identity​

Using the identity sum_{k=0}^{n} C(n, k) = 2^n, explain why a binomial heap storing n items has exactly popcount(n) trees.

Answers and Walkthroughs​

1.​

The five red-black invariants are: every node is red or black; the root is black; every NIL leaf is black; a red node has black children; every root-to-leaf path has the same black-height. The equal black-height invariant, together with the no-two-reds rule, forces height <= 2 log2(n+1), hence O(log n).

2.​

A left rotation about 10 pulls 20 up to the root with 10 becoming its left child and 30 remaining the right child of 20. Three parent pointers update: 20.parent (was 10, now old parent of 10); 10.parent (now 20); and the parent link from the grandparent to the new subtree root.

3.​

bf = +2 with the right child's bf = -1 is a right-left zig-zag. The fix is a double rotation: first right on the right child to straighten, then left on x.

4.​

Each node's height L_i is geometric with P(L_i >= k) = 2^{-k}. By union bound, P(max_i L_i >= k) <= n * 2^{-k}. For k = 2 log2 n, this is 1/n, so E[max_i L_i] = O(log n).

5.​

n-1 unions with linked lists each scanning up to O(n) elements give a worst-case sequence of cost O(n^2).

6.​

Amortized O(alpha(n)) per operation, where alpha is the inverse Ackermann function. For any n that will ever arise physically, alpha(n) <= 4 and at 2^65536 it is about 4.

7.​

Kruskal picks the lightest edge that does not create a cycle; the cut property guarantees this edge is in some MST. The cycle check reduces to find(u) == find(v) in a union-find instance over vertices; after each accepted edge a union(u, v) is performed.

8.​

After 8 inserts, n = 8 = 1000_2, so the forest contains exactly one B_3 (a single 8-node binomial tree); all lower-order trees have cascaded-linked away.

9.​

Phi(H) = t(H) + 2 m(H). An insert adds one root and no marks, so Delta Phi = +1. Actual cost is O(1), amortized = O(1) + 1 = O(1).

10.​

decrease-key may trigger a cascading cut chain that walks up the tree for O(log n) levels in the worst case. The stored potential from prior insert/consolidate pays for the cuts, and the Delta Phi turns the worst-case chain into O(1) amortized. extract-min absorbs the deferred consolidation work; each extract-min is O(log n) amortized.

11.​

  1. Costs are 1, 2, 1, 4, 1, 1, 1, 8, .... Copy cost sums as 2 + 4 + 8 + ... + 2^{floor(log2 n)} < 2n, plus n constant-time pieces. So T(n) < 3n.
  2. T(n)/n < 3 = O(1).
  3. With constant-size increment c, a resize occurs every c inserts and copies the full current array; total work is sum_{i=0}^{n/c} i c = O(n^2), giving amortized O(n) rather than O(1).

12.​

Charge each push $2: $1 for its own cost, $1 stored on the item. pop and each item popped inside multipop cost $1, paid by the stored credit on that item. Since every item pushed is popped at most once, total cost <= 2n, hence O(n).

13.​

Let Phi = |In|.

  • enqueue: actual 1, Delta Phi = +1, amortized = 1 + 1 = 2 = O(1).
  • dequeue with non-empty Out: actual 1, Delta Phi = 0, amortized = 1.
  • dequeue that transfers k items from In to Out and pops one: actual = k + 1, Delta Phi = -k, amortized = (k+1) - k = 1 = O(1).

All operations are O(1) amortized; n operations cost O(n).

14.​

m = -10^6 * ln(0.01) / (ln 2)^2 = 10^6 * 4.605 / 0.4805 approx 9.585 * 10^6 bits, about 1.2 MB. k = (m/n) ln 2 approx 9.585 * 0.6931 approx 6.64, round to k = 7.

15.​

Segment tree supports range-max because each internal node stores the max over its sub-range. Fenwick tree's low-bit decomposition only works for invertible operations (sum, xor) because range queries are differences; max is not invertible so Fenwick cannot support range-max in O(log n).

16.​

alpha(n) < log* n < log log n < log n. alpha(n) <= 4 for every n <= 2^(2^65536), i.e., for any input that can exist.

17.​

Master theorem case 2: f(n) = O(n), a = 2, b = 2, log_b a = 1, so T(n) = Theta(n log n). A single segment-tree update descends O(log n) levels with O(1) work per level, O(log n) total.

18.​

P(L_i >= k) = 2^{-k}. Union bound: P(max_i L_i >= k) <= n 2^{-k}. Pick k = c log2 n; for c > 1 this is < 1/n, so the tail beyond c log2 n contributes O(1) to expectation and E[max_i L_i] = O(log n).

19.​

Invalid. The claim bounds A from above only, giving A = O(n^2), not Theta(n^2). Theta requires a matching lower bound.

20.​

A binomial heap of n elements has one B_k for each bit set in n's binary representation. The number of 1 bits is popcount(n).

Remediation Tiers​

If you missed:

  • 1, 2: Reread concepts/cluster-01-balanced-binary-search-trees/02-red-black-trees-*.
  • 3: Reread concepts/cluster-01-balanced-binary-search-trees/03-avl-trees-*.
  • 4, 18: Reread concepts/cluster-01-balanced-binary-search-trees/04-skip-lists-* and concepts/cluster-05-randomized-persistent-and-succinct-structures/15-randomized-data-structures-*.
  • 5, 6: Reread concepts/cluster-02-union-find-and-disjoint-set-structures/05-* and 06-*.
  • 7: Reread concepts/cluster-02-union-find-and-disjoint-set-structures/07-applications-*.
  • 8, 20: Reread concepts/cluster-03-advanced-heaps-and-meldable-structures/08-binomial-heaps-*.
  • 9, 10: Reread concepts/cluster-03-advanced-heaps-and-meldable-structures/09-fibonacci-heaps-*.
  • 11-13: Reread concepts/cluster-04-amortized-analysis/ (all four pages). Redo practice 02 Part B.
  • 14: Reread concepts/cluster-05-randomized-persistent-and-succinct-structures/16-bloom-filters-*.
  • 15: Reread concepts/cluster-05-randomized-persistent-and-succinct-structures/17-segment-trees-and-fenwick-trees-*.
  • 16, 17, 19: Refresh semester 1 asymptotics (semester-01/module-01-02) and discrete math chapters.