Skip to main content

Cumulative Review: Semesters 0, 1, and 2

World-Class Evidence Integration

Include one transfer question from the World-Class Strand that connects current work to the previous semester and two semesters back.

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