Difficulty: Advanced | Prerequisites: Recurrence relations (see Part 1 notes), basic proof techniques
This set of notes covers Euclid's GCD algorithm, greedy algorithm correctness proofs via exchange arguments, dynamic programming recurrence formulation, and Turing reduction proofs of undecidability. These topics account for roughly 40-50 points of the EECS 376 midterm and include the two 10-point long-answer questions, so they carry significant weight.
Euclid's algorithm
A method for computing the greatest common divisor (GCD) of two non-negative integers. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller: gcd(a, b) = gcd(b, a mod b), with base case gcd(a, 0) = a.
In simple terms, keep dividing and taking remainders until one number hits zero.
Greedy algorithm
An algorithm that builds a solution step by step, making the locally optimal choice at each step without reconsidering earlier choices. Greedy algorithms are fast but do not always produce optimal solutions. When they do, you need a proof.
Exchange argument
A proof technique for showing a greedy algorithm is optimal. You assume an optimal solution OPT exists, find the first place where it differs from the greedy solution ALG, and show you can swap OPT's choice for ALG's choice without making things worse. Repeating this exchange transforms OPT into ALG, proving ALG is optimal.
Dynamic programming (DP)
An algorithm design technique for optimisation problems with overlapping subproblems and optimal substructure. You define a recurrence that expresses the answer for a problem in terms of answers to smaller subproblems, solve the subproblems bottom-up (or top-down with memoisation), and avoid redundant computation.
Think of it as "recursion plus a table to avoid redoing work."
Turing reduction
A reduction from problem A to problem B that shows: if B is decidable, then A is decidable (equivalently, if A is undecidable, then B is undecidable). The reduction is an algorithm that solves A by calling a subroutine (oracle) for B. To prove B is undecidable, you reduce a known undecidable problem to B.
In simple terms, "if I could solve B, I could solve A" means B is at least as hard as A.
The algorithm computes gcd(a, b) by the rule: gcd(a, b) = gcd(b, a mod b), stopping when the second argument is 0.
Worked example (Exam Q9): gcd(132, 36)
gcd(132, 36): 132 mod 36 = 132 - 3(36) = 132 - 108 = 24. So gcd(132, 36) = gcd(36, 24).
gcd(36, 24): 36 mod 24 = 12. So gcd(36, 24) = gcd(24, 12).
gcd(24, 12): 24 mod 12 = 0. So gcd(24, 12) = gcd(12, 0).
gcd(12, 0) = 12.
Recursive calls: gcd(132, 36) -> gcd(36, 24) -> gcd(24, 12) -> gcd(12, 0).
Final answer: 12.
Tips for the exam
The question asks you to list every recursive call with its arguments. Write them out in a chain. Double-check your modular arithmetic: a mod b = a - b * floor(a/b). A common error is computing the quotient wrong on the first step.
The exchange argument is the standard way to prove a greedy algorithm is optimal on the EECS 376 midterm. The template has four parts.
The template
Let ALG be the greedy solution and OPT be any optimal solution, both in some canonical order.
Find the first position r where they differ.
Show you can swap OPT's choice at position r for ALG's choice without reducing the solution quality.
Repeat until OPT matches ALG entirely. Since OPT started optimal and never got worse, ALG must also be optimal.
Worked example (Exam Q11): server-application matching
You have n applications (sorted by minimum throughput A[1] <= ... <= A[n]) and m servers (sorted by throughput S[1] <= ... <= S[m]). The greedy algorithm assigns each application to the smallest available server that meets its requirement.
The proof fills in three blanks:
(a) Show A[ALG[r]] <= A[OPT[r]]
The greedy algorithm processes applications in order of increasing index and always picks the smallest feasible server. At position r, the first mismatch, ALG chose a different application than OPT. Since ALG processes applications in increasing index order and greedily picks the earliest feasible one, ALG[r] <= OPT[r] as indices. Because the array A is sorted in non-decreasing order, A[ALG[r]] <= A[OPT[r]].
(b) Show ALG[r] is not in OPT
ALG[r] < OPT[r] (as indices, since they agree on positions 1 through r-1 and ALG greedily picks the smallest-index feasible application). If ALG[r] were in OPT at some later position, say OPT[s] = ALG[r] for s > r, then OPT would contain ALG[r] at position s and some other application at position r with a higher index. But OPT is listed in increasing order of application index, so OPT[r] < OPT[s] = ALG[r], contradicting ALG[r] < OPT[r]. So ALG[r] is not in OPT.
(c) Why can server k (serving OPT[r]) serve ALG[r] instead?
Server k satisfies S[k] >= A[OPT[r]] (since it serves OPT[r] in the valid solution OPT). From part (a), A[ALG[r]] <= A[OPT[r]]. Therefore S[k] >= A[OPT[r]] >= A[ALG[r]], so server k meets ALG[r]'s throughput requirement. The assignment is valid.
DP problems on the exam ask you to define a recurrence, state base cases, and analyse the runtime of the resulting bottom-up algorithm.
Worked example (Exam Q13): AJ the squirrel
AJ jumps from tree to tree along a line of n trees. At tree i, he drops y_i acorns. From tree i he can jump to tree i+1 or tree i+2. He must end at tree n and can start at tree 1 or tree 2. Minimise total acorns dropped.
Define D(i) = minimum acorns dropped to reach tree i.
Base cases:
D(1) = y_1 (land on tree 1, pay y_1).
D(2) = y_2 (jump directly to tree 2, pay y_2).
Recurrence (for i >= 3):
D(i) = y_i + min(D(i-1), D(i-2)).
To reach tree i, AJ must have come from tree i-1 or tree i-2. He picks whichever gave a lower total, then adds the cost y_i of landing on tree i.
Final answer: D(n).
Justification
This recurrence has optimal substructure: the best path to tree i must contain the best path to either tree i-1 or tree i-2 (otherwise you could improve it by swapping in a better sub-path). It also has overlapping subproblems: D(i-1) and D(i-2) are reused when computing D(i) and D(i+1).
Runtime analysis (part b)
The bottom-up DP fills a table of n entries. Each entry takes O(1) time to compute (one addition, one min of two values). Total runtime: O(n).
This is justified because the recurrence has a constant number of terms (two), each involving a single table lookup. No nested loops, no variable-length sums.
The long-answer section tests your ability to prove a language is undecidable by reducing a known undecidable language to it.
The reduction template
State what you are reducing from (e.g. L_HALT) and to (e.g. L_Even-Halt).
Assume for contradiction that L_Even-Halt is decidable, i.e. some TM R decides it.
Use R as a subroutine to build a decider for L_HALT.
Since L_HALT is known to be undecidable, you have a contradiction, so R cannot exist.
Worked example (Exam Q14): L_Even-Halt
L_Even-Halt = {⟨M⟩ : M(x) halts if and only if |x| is even}.
We reduce from L_HALT = {(⟨M⟩, x) : M halts on x}.
Assume R decides L_Even-Halt. Given input (⟨M⟩, x) for L_HALT, construct a new TM M' as follows:
M'(w):
If |w| is even, simulate M on x. If M halts, then M' halts. If M loops, then M' loops.
If |w| is odd, loop forever.
Now consider what R says about M':
If M halts on x: then M'(w) halts when |w| is even (because the simulation of M terminates) and loops when |w| is odd. So M' halts if and only if |w| is even. Therefore ⟨M'⟩ is in L_Even-Halt, and R accepts ⟨M'⟩.
If M does not halt on x: then M'(w) loops on all inputs (even-length inputs loop because the simulation of M never finishes; odd-length inputs loop by construction). So M' does not halt if and only if |w| is even. Therefore ⟨M'⟩ is not in L_Even-Halt, and R rejects ⟨M'⟩.
So R(⟨M'⟩) tells us exactly whether M halts on x. This gives a decider for L_HALT, which is a contradiction. Therefore L_Even-Halt is undecidable.
Worked example (Exam Q15): closure of decidable languages under star
A star B = {x : x in A-complement or x in B}. This is the same as A-complement union B, which in logic is the same as A implies B (x in A implies x in B, loosely).
Prove: for all decidable A and B, A star B is decidable.
Proof: Since A is decidable, there exists a TM M_A that decides A. Since B is decidable, there exists a TM M_B that decides B.
Construct a TM M_star for A star B:
M_star(x):
Run M_A on x.
If M_A rejects x, then x is in A-complement, so x is in A star B. Accept.
If M_A accepts x, run M_B on x.
If M_B accepts x, then x is in B, so x is in A star B. Accept.
If M_B rejects x, then x is not in A-complement (since M_A accepted) and not in B. Reject.
M_star always halts because both M_A and M_B always halt (they are deciders). M_star accepts exactly the strings in A-complement union B. So A star B is decidable.
Students sometimes try to prove a greedy algorithm is optimal by showing it works on a few examples. That is not a proof. The exchange argument is the expected method.
In DP, the recurrence must capture all possible last moves. Forgetting that AJ can start at tree 1 or tree 2 would give wrong base cases.
When constructing a Turing reduction, students often forget to show the reduction works in both directions. You need: if M halts on x, then your constructed machine is in the target language; and if M does not halt on x, then it is not in the target language. Missing either direction makes the proof incomplete.
Students sometimes confuse "Turing reduction" with "mapping reduction." A Turing reduction uses the target language as an oracle (subroutine). A mapping reduction transforms inputs. On this exam, Turing reductions are the expected tool.
For the star operation (Q15), students may overthink it. The operation is just set complement of A, union with B. Both operations preserve decidability, so the proof is straightforward.
⚠️ The two long-answer questions (Q14, Q15) are worth 10 points each, the highest-value questions on the exam. Budget your time accordingly.
⚠️ For the Turing reduction (Q14), the exam explicitly tells you which language to reduce from (L_HALT or L_ACC). Use one of those. Do not try to reduce from some other language.
⚠️ The DP question (Q13) asks for both the recurrence and the runtime. The runtime is easy points if you state it correctly: count the number of subproblems times the cost per subproblem.
⚠️ Euclid's algorithm (Q9) is 6 free points if you can do modular arithmetic. Write out every step clearly. Do not skip intermediate calls.
⚠️ The exchange argument (Q11) has three fill-in-the-blank parts. Each blank expects 1-2 sentences. Keep it concise and precise.
Fill in the blank: gcd(48, 18) = gcd(18, ____). (12, since 48 mod 18 = 12)
True or False: In an exchange argument, you must show that swapping OPT's choice for ALG's choice strictly improves the solution. (False: you only need to show it does not make it worse. "At least as good" is sufficient.)
Fill in the blank: A DP recurrence for a path problem where you can move +1 or +2 from position i has the form D(i) = y_i + ______. (min(D(i-1), D(i-2)))
True or False: To prove L is undecidable via Turing reduction, you assume L is decidable and derive a contradiction. (True.)
True or False: The complement of a decidable language is always decidable. (True.)
Q: Compute gcd(252, 105) using Euclid's algorithm. List all recursive calls.
A: gcd(252, 105) -> gcd(105, 42) -> gcd(42, 21) -> gcd(21, 0). Answer: 21.
Q: You are scheduling jobs on a single machine. Each job has a deadline and a profit earned if completed by its deadline. The greedy strategy is to schedule jobs in decreasing order of profit, skipping any that would miss their deadline. What proof technique would you use to show this is optimal?
A: The exchange argument. Assume an optimal schedule OPT differs from the greedy schedule ALG at some position. Show you can swap OPT's job at that position for ALG's (higher-profit) job without reducing total profit.
Q: AJ the squirrel can now jump +1, +2, or +3 trees. Write the new recurrence for D(i), the minimum acorns dropped to reach tree i.
A: D(i) = y_i + min(D(i-1), D(i-2), D(i-3)) for i >= 4. Base cases: D(1) = y_1, D(2) = y_2, D(3) = y_3. The runtime remains O(n) because each entry still takes O(1) (min of three values).
Q: Prove that L = {⟨M⟩ : M accepts at least one even-length string} is undecidable, reducing from L_ACC.
A: Assume decider R for L. Given (⟨M⟩, x), construct M'(w): ignore w, simulate M on x, and if M accepts x, accept. Then M' accepts every string (including even-length ones) iff M accepts x. Run R on ⟨M'⟩: if R accepts, then M' accepts some even-length string, meaning M accepts x; if R rejects, M does not accept x. This decides L_ACC, contradiction.
Euclid's algorithm connects to the analysis of algorithms: its runtime is O(log(min(a,b))), which you can prove using the fact that the remainder drops by at least half every two steps. This is a potential-function argument in disguise.
The exchange argument for greedy algorithms is structurally similar to induction: you show a base case (ALG and OPT agree) and an inductive step (if they agree up to position r-1, you can make them agree at position r). Recognising this pattern makes the proof easier to write under time pressure.
DP recurrences are the same formalism as the counting recurrences in Part 1, but applied to optimisation (min or max) instead of counting (sum). If you can set up a counting recurrence, you can set up a DP recurrence with the same structure.
Turing reductions are the undecidability analogue of NP-hardness reductions, which you will encounter later in EECS 376 if the course covers complexity theory.
Related Terms / Search Tags
Euclid's algorithm, GCD, greatest common divisor, modular arithmetic, greedy algorithm, exchange argument, greedy stays ahead, optimal substructure, dynamic programming, DP, recurrence, bottom-up, memoisation, Turing reduction, oracle, undecidability, L_HALT, halting problem, L_ACC, acceptance problem, decidable closure properties, complement, union, EECS 376, Foundations of Computer Science, University of Michigan, Winter 2026 midterm