Skip to main content

Cumulative Review: Semesters 0, 1, and 2

Learning Technique

Use this as an interleaved review set. Mix retrieval from orientation, math foundations, and algorithms instead of restudying one topic at a time.

Instructions​

  • Work under a 90-minute limit.
  • Use paper first for traces, recurrences, and proof sketches.
  • Do not open notes until the first full pass is done.
  • Mark each question with one of three statuses: clear, slow, or missed.
  • After grading, turn every slow or missed answer into either a flashcard, a code kata, or a short written explanation.

Questions​

  1. [S0 + S2] A function scans an array once and then sorts it with merge sort. Write the overall asymptotic runtime and explain which part dominates.
  2. [S1 + S2] Give a short proof sketch that binary search is correct. State the invariant you rely on.
  3. [S2M1] Solve the recurrence T(n) = 2T(n/2) + n and explain what algorithm shape usually produces it.
  4. [S2M1] Compare divide-and-conquer and dynamic programming. What shared structure do they have, and what key difference changes the implementation strategy?
  5. [S1 + S2] Why is logarithmic growth dramatically different from linear growth in practice? Give a concrete example involving search.
  6. [S2M2] Compare merge sort, quicksort, and heap sort on stability, memory use, and worst-case runtime.
  7. [S2M2] Explain when a heap is a better fit than a sorted array and when it is worse.
  8. [S0 + S2M2] A programmer uses linear search on a sorted list because the list is "not that large." What follow-up questions should you ask before accepting that choice?
  9. [S2M2] Describe average-case hash-table lookup and the main assumptions that make it fast in practice.
  10. [S2M3] Explain the difference between BFS and DFS using both traversal behavior and typical use cases.
  11. [S2M3] Why does Dijkstra's algorithm fail with negative-weight edges?
  12. [S2M3] Compare adjacency lists and adjacency matrices in terms of storage cost and the operations each makes efficient.
  13. [S1 + S2M3] A graph problem asks whether two users are connected within three introductions. Which representation and traversal would you reach for first, and why?
  14. [S2M3] Distinguish shortest-path problems from minimum-spanning-tree problems. Why is using one algorithm family for the other a category error?
  15. [S2M4] Define overlapping subproblems and optimal substructure in your own words.
  16. [S2M4] Convert a recursive Fibonacci-style solution into memoized and tabulated forms. What changes in runtime and why?
  17. [S2M4] Give one example where a greedy strategy is correct and explain the property that makes it safe.
  18. [S2M4] Give one example where a greedy-looking choice fails and dynamic programming is needed instead.
  19. [S1 + S2M4] Why does writing the recurrence carefully often expose the actual state you need for dynamic programming?
  20. [S2M5] Explain amortized analysis using dynamic array growth or another concrete example.
  21. [S2M5] What problem does union-find solve, and why is it especially useful in connectivity-heavy workflows?
  22. [S2M5] Compare balanced search trees with hash tables when you need ordering, range queries, or predictable worst-case behavior.
  23. [S0 + S1 + S2] When you benchmark two implementations and the faster result contradicts your asymptotic expectation, what are the first three things you should inspect?
  24. [S2 Integrated] A problem requires frequent "find minimum," repeated inserts, and occasional deletes. Which structure would you choose first, and what alternative would you evaluate if ordering queries later become necessary?
  25. [S2 Integrated] Pick one algorithm from each module and explain how the semester builds from analysis to implementation to tradeoff judgment.

Scoring guide​

  • 22-25 clear: ready for the exam and checkpoint gate
  • 18-21 clear: acceptable, but revisit slow areas before moving on
  • 14-17 clear: repeat the review after focused remediation
  • 0-13 clear: do not treat Semester 2 as complete

Error log​

Use this after grading.

Q#StatusWhat failedFix action
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25