A-I 305 · Exam 2
Wed Nov 4 · 8–10 pm · 103 ECoRE · closed book, no notes, no calculator, no cheat sheet
What's on it (from your notes)
| Part | Count | Priority | Lesson |
|---|---|---|---|
| Ch 4 · shortest paths | 2 problems | top | 2 · Shortest paths |
| Ch 5 · greedy | 2 problems | top | 3 · Greedy |
| Ch 6 · dynamic programming | 2 problems | top | 4 · DP |
| Ch 3 · DFS | 1 problem | medium | 1 · DFS / SCC |
| MCQs | 15 | medium | 5 · MCQ concepts · drill bank |
| HW3 + HW4 | in scope | top (repeats likely) | HW solutions |
Ch 4, 5 and 6 are 6 of the 7 problems. Spend most of your time there. Ch 3 is one problem, and it's almost always a hand trace.
What Exam 1 taught us
The real Exam 1 didn't look like the posted practice exam. The practice exam was mostly prove/disprove questions. The real one was:
- DPV end-of-chapter exercises, nearly word for word. Q7 was DPV 3.3 exactly: the topological sort graph, "alphabetically first", pre/post table, and count the orderings. Q5 was DPV's matrix-squaring exercise. Q1 was the Fibonacci bound from Ch 0.
- A homework repeat. Q3 was HW1 Problem 7, and the solution even says "Same as HW1 Problem 7."
- Exercises solved in lecture. MCQ 15 was DPV 1.20, solved in Lecture 13.
- MCQs: about half were Poole–Mackworth definitions, the rest quick DPV facts.
So for Exam 2, the best targets are, in order: (1) HW3/HW4 problems, (2) DPV Ch 3–6 hand traces with alphabetical tie-breaks (3.4, 4.1, 4.2, 5.1, 5.2, 5.13/5.14), (3) exercises the professor solved in class (4.3, 4.8, 4.15, 4.18, Quiz 6, knapsack table, edit distance, weighted intervals), (4) MCQs from the professor's review decks and the Poole–Mackworth ch 4–5 slides.
Most likely problems, ranked
| Slot | Most likely | Also prepare |
|---|---|---|
| Ch 3 (1) | DPV 3.4 SCC trace: run DFS on GR, give the order SCCs are found, source/sink SCCs, metagraph, edges to add. Exam 1 already used 3.3, so this is the next one. | DPV 3.2 edge classification (tree/forward/back/cross), 3.1; HW3 P1, P3, P4 |
| Ch 4 (2) | A Dijkstra table (DPV 4.1, solved in Lecture 18) + a "modify Dijkstra" design (4.15 usp, 4.18 best, count shortest paths) | Bellman–Ford table (4.2), Quiz 6 (3-vertex graph where Dijkstra fails), 4.8 (adding a constant fails), 4.3 squares, HW3 P6 (time-dependent), HW3 P7 (currency, −log r) |
| Ch 5 (2) | An MST trace (DPV 5.1: cost, # MSTs, Kruskal order + cuts; or 5.2: Prim table) + Huffman or a greedy proof | HW4 P2 (is e in the MST?), P3 (D&C MST counterexample), P4 (greedy party counterexample), P5 (40% ⇒ 1-bit code); 5.9 true/false; fractional knapsack exchange argument; Horn formulas |
| Ch 6 (2) | Fill a DP table (0/1 knapsack as in Lecture 28, or edit distance/LCS) + design a DP (subproblem, recurrence, order, runtime) | HW4 P6 (rod cutting with cut cost), HW4 P7 (hotels = DPV 6.2), 6.1 max contiguous sum, 6.3 Yuckdonald's, weighted interval scheduling, LIS |
| 15 MCQs | Poole–Mackworth ch 4 (CSPs, arc consistency) and ch 5 (propositions, bottom-up/top-down proofs) | Heaps, hash tables, union-find, greedy vs DP facts, DFS/BFS/Dijkstra facts |
Plan for Wednesday
Check items off as you go (saved in this browser). Times are for a full day; for the short version, do only the ★ items.
- 1★ Shortest paths: do DPV 4.1 and 4.2 by hand before opening the answers. Then 4.15, 4.18, Quiz 6. 75 min
- 2★ Greedy: 5.1 and 5.2 by hand, Huffman 5.13/5.14, the cut property proof, 5.9 true/false. 75 min
- 3★ DP: the 5-step recipe, then fill the knapsack and edit distance tables yourself. 75 min
- 4★ HW3 + HW4 solutions: for each problem, say the technique out loud before reading. 45 min
- 5★ DFS / SCC: DPV 3.4(i) and (ii) by hand. 30 min
- 6MCQ concepts, then 50-question drill at 30 s each. 45 min
- 7★ Mock Exam 2, timed, on paper. Then grade it with the key and reread the weak topics. 2 h + 30 min
- 8★ Last-hour sheet right before you leave. 20 min
Exam technique
- Traces: follow the tie-break rule exactly ("alphabetically first"), and write the full table even when it seems obvious. The marks are in the table.
- Design questions: name the base algorithm ("modified Dijkstra", "DP over prefixes"), give pseudocode, give one sentence on why it's correct, and state the running time. Points come from all four.
- DP questions: define the subproblem in words first. That's usually worth half the credit.
- Greedy questions: if it says "show it may fail", give a concrete small counterexample with numbers, then show greedy's answer next to the optimum.
- MCQs: 15 × about ⅓ point. Don't spend more than a minute on any one.
Sources: Canvas lecture notes, review decks, HW3/HW4, Exam 1 and its solutions, DPV ch 3–6. Trace answers were computed by a script, not by hand.