Mock final & how to attack the exam

Attacking an open-book, invigilated final

Because it is open-book, memorization earns little — the paper tests whether you can apply a technique to a problem you have not seen. Tactics:

• Do not read during the exam what you should already know. Have the reference sheet (Lesson 12.1) automatic; use the book only for a specific lemma or constant.
• Budget by marks. The final is 40% of the grade. Spend minutes proportional to marks; a 4-mark recurrence should not eat the time a 15-mark DP design needs.
• For 'design an algorithm' questions, always deliver the full package: the idea, the pseudocode/recurrence, a correctness argument (invariant / exchange / cut-and-paste), and the running-time analysis. Partial packages lose the analysis and correctness marks even when the algorithm is right.
• For 'prove correct': name the technique first (loop invariant, exchange, cut-and-paste, reduction), then execute its template. Graders reward the recognizable structure.
• State assumptions and edge cases (empty input, negative weights, ties) — they are often where the marks hide.

What a full-marks proof looks like

• Recurrence: state the method (tree/substitution/master), show the watershed or the induction with a fixed constant, give the Θ bound.
• Greedy optimal: 'By an exchange argument: let OPT be any optimal solution; swap its first choice for the greedy choice; show the result is feasible and no worse; conclude the greedy choice is in some optimum, then induct.'
• NP-complete: the two-step template, with the reduction FROM a named known-NPC problem and both directions of the equivalence.
• DP: the four steps — optimal substructure (cut-and-paste), recurrence + base cases, table order + running time, reconstruction.

Mock final (attempt cold, then check)

The recall questions below are a full mock spanning every AU unit. Attempt each on paper before revealing the answer — that retrieval effort is what builds durable memory. Sit them in one 90-minute block to simulate the real thing.