Skip to main content

Semester 2 Exam

Required Output Classification​

Required outputClassificationPublic/private guidance
Timed written answers, diagrams, code snippets, and design responsesCheckpoint evidenceKeep raw exam work private so it remains useful for assessment and retake calibration.
Post-exam review notes, missed-answer repairs, and Feynman explanationsPractice artifactUse for spaced review; publish only rewritten explanations that no longer reveal exam solutions wholesale.
Capstone-defense or architecture-defense packets created from exam promptsPortfolio candidatePolish publicly only when they are original to your project, sanitized, and framed as engineering rationale rather than exam answers.
tip

Take this as a two-hour written assessment. Closed notes is ideal. A one-page handwritten formula sheet is acceptable if that matches your study contract.

Format​

SectionDurationPoints
Analysis, recurrence, and correctness reasoning30 minutes25
Sorting, searching, and structure tradeoffs25 minutes20
Graph algorithms25 minutes20
Dynamic programming and greedy judgment20 minutes20
Advanced structures and amortized analysis20 minutes15

Total: 100 points

Coverage map​

  • Module 1: Asymptotics, recurrences, proof sketches, divide-and-conquer reasoning
  • Module 2: Sorting/searching behavior, heaps, hash-backed vs ordered structures
  • Module 3: Traversals, shortest paths, spanning trees, graph representation choices
  • Module 4: DP state design, memoization/tabulation, greedy-vs-DP tradeoffs
  • Module 5: Balanced trees, union-find, amortized reasoning, operation-cost comparisons

Exam paper​

Section A: Analysis and correctness​

  1. A recursive algorithm splits the input into two equal halves, solves both, and spends linear time merging results. Write the recurrence, solve it, and name a concrete algorithm from this semester with the same shape.
  2. Compare O(n log n) and O(n^2) sorting behavior for n = 10^3 and n = 10^6. You do not need exact counts; give order-of-growth reasoning and the engineering consequence.
  3. Write a short correctness argument for binary search or merge sort. Your answer must name the invariant or structural idea doing the real work.

Section B: Sorting, searching, and structures​

  1. Compare merge sort, quicksort, and heap sort on stability, extra memory, worst-case runtime, and when you would choose each in practice.
  2. You need repeated insertion plus frequent access to the current minimum item. Choose a structure, justify the choice, and explain what operation becomes weak compared with a balanced tree.
  3. A team wants a hash table because "lookup is constant time." List the assumptions hidden inside that statement and one case where an ordered structure is the better choice.

Section C: Graph algorithms​

  1. A graph models cities connected by weighted roads. Explain when BFS is correct, when Dijkstra is required, and when a minimum spanning tree algorithm is solving the wrong problem.
  2. Compare adjacency lists and adjacency matrices for sparse and dense graphs. Include both storage and traversal implications.
  3. A social graph question asks whether two users are connected within at most three hops. Choose an algorithm, show the stopping logic, and explain why it fits better than DFS for this task.

Section D: Dynamic programming and greedy choice​

  1. Define overlapping subproblems and optimal substructure. Then describe a problem from this semester where both are present.
  2. Start from a recursive solution to a classic DP problem of your choice. Show how you would convert it into memoization and then tabulation.
  3. Give one example where a greedy strategy works and one where it fails. For each, explain the property that makes the conclusion valid.

Section E: Advanced structures and amortized analysis​

  1. Explain union-find, the operations it supports, and one concrete workflow where it is the natural tool.
  2. Compare balanced search trees with hash tables for ordered iteration, range queries, and worst-case guarantees.
  3. Explain amortized analysis using either dynamic arrays, path compression, or another structure from the semester. The answer must distinguish amortized cost from average-case cost.

Performance standard​

  • 85-100: ready to advance
  • 70-84: pass, but revisit the missed module before Semester 3 deep work
  • 60-69: weak pass only if the project and checkpoint evidence are strong
  • Below 60: repair gaps and retake

Reflection after grading​

Write a short post-exam note with:

  • the two questions you solved confidently
  • the two questions that exposed weak pattern recognition
  • the one module you need to keep alive during Semester 3

Added Implementation-Reasoning Prompts​

Use these prompts when the exam needs more evidence than final answers:

  1. Analyze three loop snippets, including one additive and one multiplicative nested loop. Give exact counts for small n and asymptotic bounds.
  2. Given a list problem, choose between sorting, hashing, two pointers, or brute force. Defend the choice with runtime, memory, and correctness reasoning.
  3. Implement BFS path reconstruction in pseudocode and state which data structure guarantees FIFO behavior.
  4. Convert a recurrence into a DP state, then state whether memoization or tabulation fits the problem constraints better.
  5. Compare a heap and a hash table for one workload where each is the right tool.

Mastery Rubric​

LevelEvidence
Beginner passCan answer direct questions and complete familiar exercises with light notes.
Solid passCan solve new variants, explain choices, and connect the work to Semester 1 Mathematical and CS Foundations.
Strong passCan defend tradeoffs, identify failure modes, and produce clean evidence in the portfolio artifact.
Not readyRelies on copied solutions, cannot explain mistakes, or lacks durable artifacts.

Retake and Repair Rule​

If a section is weak, do not only reread. Repair it by producing new evidence: a corrected solution, a fresh implementation, a rewritten proof, a benchmark, a diagram, a runbook, or a short teaching note.

Answer-Quality Examples​

Use these examples when grading written answers or spoken explanations.

QualityExample pattern
WeakNames a concept but gives no example, constraint, or failure case.
AcceptableDefines the concept and applies it to a familiar exercise.
StrongApplies the concept to a new variant and explains why an alternative would fail.
Portfolio-readyConnects the concept to Semester 1 Mathematical and CS Foundations, current project evidence, and a future capstone decision.

Interleaving Prompt​

For any missed answer, add one sentence starting with: This depends on an earlier skill because...​

Calibration Materials​

Use these learner-visible calibration materials before self-grading or requesting review: