This material covers the core algorithm-design toolkit tested on the EECS 376 midterm: how to write and solve recurrence relations, when the Master Theorem applies (and when it does not), how Karatsuba multiplication improves on naive multiplication, and how to identify whether a problem calls for divide-and-conquer, greedy, or dynamic programming. You also need to know how potential functions prove termination and how to analyse correctness via proof by contradiction.
Difficulty: Intermediate
Prerequisites: comfort with Big-O notation, basic proof techniques (induction, contradiction), and elementary graph concepts (vertices, edges, weights). If you are unsure about asymptotic notation, review that material first.
EECS 376 (Foundations of Computer Science) asks you to reason formally about algorithms: not just run them, but prove they terminate, prove they are correct, and characterise how their running time scales. The algorithms-and-recurrences portion of the midterm ties together three threads. First, you need fluency with specific algorithms (Euclidean GCD, Karatsuba multiplication, MajorityElement). Second, you need to translate an algorithm's recursive structure into a recurrence relation and, where possible, solve it with the Master Theorem. Third, you need to classify algorithms by paradigm (divide-and-conquer, greedy, dynamic programming) and argue about termination using potential functions.
If you can write a recurrence from pseudocode, decide whether the Master Theorem applies, identify an algorithm's paradigm from its structure, and prove correctness by contradiction, you are well placed for the exam.
Euclidean Algorithm
A method for computing the greatest common divisor (GCD) of two integers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. In simple terms, you keep taking remainders until one side hits zero, and the other side is your GCD.
Karatsuba Algorithm
A divide-and-conquer multiplication algorithm that splits each n-digit number into two halves and computes the product using three recursive multiplications instead of four, giving a running time of O(n^(log_2 3)) rather than the naive O(n^2). Think of it as a clever trick that trades one multiplication for a few additions and subtractions.
Recurrence Relation
An equation that defines a function T(n) in terms of T on smaller inputs, describing the time complexity of a recursive algorithm. In simple terms, it is a formula that says "the cost of a problem of size n equals some combination of costs for smaller problems plus some extra work."
Master Theorem
A theorem that gives a closed-form solution for recurrences of the form T(n) = k * T(n/b) + O(n^d), where k is the number of subproblems, b is the factor by which the input shrinks, and d is the exponent of the combine step. Think of it as a look-up rule: compare log_b(k) with d, and the answer falls into one of three cases.
Potential Function
A function of the algorithm's state that is bounded and changes monotonically with each iteration, used to prove that an algorithm terminates. In simple terms, it is a quantity that always goes up (or always goes down) and cannot do so forever, so the algorithm must stop.
Divide and Conquer
An algorithm paradigm that breaks a problem into smaller subproblems, solves each recursively, and combines the solutions. Think of it as: split, solve the pieces, merge.
Greedy Algorithm
An algorithm paradigm that builds a solution step by step, making the locally optimal choice at each stage without reconsidering previous choices. In simple terms, at each step you pick whatever looks best right now and never go back.
Dynamic Programming (DP)
An algorithm paradigm for optimisation problems that exhibit optimal substructure and overlapping subproblems; it solves each subproblem once and stores the result. Think of it as "recursion plus a memo pad" so you never redo work.
Slowsort
A deliberately inefficient recursive sorting algorithm used in EECS 376 as a pedagogical example. It sorts both halves, floats the maximum to the end, then recursively sorts n - 1 elements, yielding the recurrence T(n) = 2T(n/2) + T(n - 1) + O(1).
MajorityElement
A divide-and-conquer algorithm that finds the element appearing strictly more than n/2 times in an array (if one exists) by recursively finding majority candidates in each half and then verifying them against the full array.
The algorithm computes gcd(a, b) by repeatedly setting (a, b) := (b, a mod b) until b = 0.
The number of iterations depends on how slowly the remainder shrinks. Consecutive Fibonacci-like numbers (e.g. 29, 18) produce the most steps because each remainder is only slightly smaller than the previous one.
Worked comparison from the exam:
gcd(800, 300): 4 steps
gcd(100, 55): 5 steps
gcd(29, 18): 6 steps (the most)
gcd(1000, 999): 2 steps
gcd(19, 11): 5 steps
The potential function s_i = x_i + y_i proves termination (it strictly decreases each iteration with a lower bound of 1). An alternative potential function p_i = x_i * y_i also works, since y_i mod x_i is strictly less than x_i at each step.
To multiply two n-digit numbers, split each into high and low halves: x = a * 10^(n/2) + b, y = c * 10^(n/2) + d.
Compute three products instead of four:
M1 = a * c
M2 = b * d
M3 = (a + b) * (c + d)
Result: M1 * 10^n + (M3 - M2 - M1) * 10^(n/2) + M2.
When the digits are single-digit, return the ordinary product (base case).
Recurrence: T(n) = 3T(n/2) + O(n), giving T(n) = O(n^(log_2 3)), roughly O(n^1.585).
Worked example (59 x 55): 59 = 510 + 9, 55 = 510 + 5. M1 = 25, M2 = 45, M3 = Karatsuba(10, 14) = 140. Final: 2500 + 700 + 45 = 3245.
Applies to recurrences of the form T(n) = k * T(n/b) + O(n^d).
Three cases:
If d > log_b(k): T(n) = O(n^d)
If d = log_b(k): T(n) = O(n^d * log n)
If d < log_b(k): T(n) = O(n^(log_b k))
The theorem is unusable when the recurrence contains terms that do not fit this form, such as T(n - 1). For example, Slowsort's recurrence T(n) = 2T(n/2) + T(n - 1) + O(1) cannot be solved by the Master Theorem because of the T(n - 1) term.
For recurrences like T(n) = 2T(n^(1/4)) + O(log n), a change of variable can bring it into Master Theorem form.
Let S(n) = T(2^n). Then T(2^n) = 2T(2^(n/4)) + O(n), so S(n) = 2S(n/4) + O(n).
By the Master Theorem (k = 2, b = 4, d = 1): S(n) = O(n).
Since S(n) = T(2^n), we get T(2^n) = O(n), and letting n = log m: T(m) = O(log m).
Divide and conquer: the problem is split into subproblems, each solved recursively, and results combined. Example: the matrix multiplication algorithm that partitions into n/2 x n/2 sub-matrices.
Greedy: at each step, make the locally optimal choice without reconsidering. Example: assigning students to the nearest unoccupied chair.
Dynamic programming: the problem has optimal substructure and overlapping subproblems; a table is filled bottom-up. A bottom-up DP algorithm filling an n x m table runs in at least Omega(nm) time (each entry must be filled), though filling a single entry is not always O(1).
A potential function proves an algorithm terminates by showing some quantity strictly increases (or decreases) at each step and is bounded.
For the Euclidean algorithm, both s_i = x_i + y_i and p_i = x_i * y_i serve as valid potential functions.
Not every algorithm has a potential function. The function ALG(a, b) that halves one argument and doubles the other oscillates (e.g. inputs 4, 8 cycle back to 4, 8 after two iterations), so no monotonic potential function exists and the algorithm does not terminate on those inputs.
Recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem (k = 2, b = 2, d = 1): T(n) = O(n log n).
Correctness proof (by contradiction): if z is a majority element of the whole array, it must be a majority in at least one half. Suppose it is a majority in neither half. Then z appears at most n/4 times in each half, so at most n/2 times total, contradicting the requirement that it appears strictly more than n/2 times.
Master Theorem standard form
T(n) = k * T(n/b) + O(n^d)
Case 1 (d > log_b k): T(n) = O(n^d) Case 2 (d = log_b k): T(n) = O(n^d log n) Case 3 (d < log_b k): T(n) = O(n^(log_b k))
Karatsuba recombination
Given x = a * B + b and y = c * B + d (where B = 10^(n/2)): x * y = M1 * B^2 + (M3 - M1 - M2) * B + M2 where M1 = ac, M2 = bd, M3 = (a+b)*(c+d).
Key recurrences from the exam
Slowsort: T(n) = 2T(n/2) + T(n - 1) + O(1). Master Theorem is unusable.
MajorityElement: T(n) = 2T(n/2) + O(n). Master Theorem gives O(n log n).
Substitution example: T(n) = 2T(n^(1/4)) + O(log n) solves to T(n) = O(log n).
Bottom-up DP on an n x m table: at least Omega(nm).
Students often assume the Master Theorem can handle any recurrence. It cannot. The T(n - 1) term in Slowsort's recurrence breaks the required form, and no amount of algebra will fix that.
A common error is confusing Omega(nm) with Theta(nm) for a DP table. Filling the table is at least Omega(nm), but if filling a single cell costs more than O(1), the overall bound is not Theta(nm).
Students sometimes identify an algorithm as divide-and-conquer simply because it uses recursion. Recursion alone is not sufficient; the problem must be partitioned into independent subproblems whose solutions are combined. A greedy algorithm can also be expressed recursively.
When using Karatsuba, students frequently forget to recurse on M3 when (a + b) or (c + d) has more than one digit. M3 is not always a base-case multiplication.
On potential functions: students try to find a potential function for every algorithm. Some algorithms (like the cycling ALG(a, b) example) genuinely have no potential function because they do not terminate.
Expect to trace through the Euclidean algorithm on specific inputs and count iterations. Fibonacci-adjacent pairs are the classic worst case.
Karatsuba is tested both as a worked computation (show all recursive calls) and as a recurrence-writing exercise.
The Master Theorem appears in multiple forms: straightforward application, recognising when it is unusable, and applying a substitution to bring a non-standard recurrence into the required form.
You will be asked to identify algorithm paradigms from a prose description of an algorithm, not from its name. Read the description for: subproblem structure (D&C), local-choice-without-backtracking (greedy), or table-filling with reuse (DP).
Potential function questions may ask you to verify a proposed function or explain why no function exists.
MajorityElement correctness is a proof-by-contradiction question. Know the structure: assume the majority element is not a majority in either half, bound the total count, reach a contradiction.
True or False: The Master Theorem can solve T(n) = 2T(n/2) + T(n - 1) + O(1).
Fill in the blank: Karatsuba multiplication uses ___ recursive multiplications of half-sized inputs.
True or False: A bottom-up DP algorithm that fills an n x m table always runs in Theta(nm) time.
Fill in the blank: A potential function must be ___ and change ___ at each iteration.
True or False: The pair (29, 18) produces more Euclidean algorithm steps than (1000, 999).
Answers: 1. False (unusable). 2. Three. 3. False (at least Omega(nm), but not necessarily Theta). 4. Bounded, monotonically (strictly). 5. True.
Q: You are given the recurrence T(n) = 2T(n/2) + O(n). What does the Master Theorem give?
A: k = 2, b = 2, d = 1. Since d = log_b(k) = 1, we are in Case 2: T(n) = O(n log n).
Q: Why is the Master Theorem unusable for Slowsort's recurrence T(n) = 2T(n/2) + T(n - 1) + O(1)?
A: The Master Theorem requires the form T(n) = k * T(n/b) + O(n^d). The T(n - 1) term does not fit this template because it is not T applied to n divided by a constant.
Q: Describe how to prove that MajorityElement correctly identifies a majority element when one exists.
A: By contradiction. Assume the majority element z of the full array is not a majority in either half. Then z appears at most n/4 times in each half, so at most n/2 times total. This contradicts z being a majority (strictly more than n/2 occurrences). Therefore z must be a majority in at least one half, and the algorithm will find and verify it.
Q: Use Karatsuba to multiply 38 and 29. Show the recursive calls.
A: 38 = 310 + 8, 29 = 210 + 9. M1 = 32 = 6. M2 = 89 = 72. M3 = Karatsuba(11, 11). For 1111: 11 = 110 + 1, so M1' = 1, M2' = 1, M3' = 4. Karatsuba(11,11) = 100 + 20 + 1 = 121. Final: 600 + (121 - 72 - 6)*10 + 72 = 600 + 430 + 72 = 1102.
Q: An algorithm halves a when a > b and doubles a when b > a (and halts when a = b, a = 1, or b = 1). Can you find a potential function to prove termination?
A: No. The inputs can cycle (e.g. a = 4, b = 8 becomes a = 8, b = 4, then back to a = 4, b = 8). A monotonically changing function cannot exist when the state repeats, so no potential function works and the algorithm does not terminate on these inputs.
Recurrence relations and the Master Theorem reappear throughout EECS 376 whenever you analyse a recursive algorithm, including graph algorithms (Kruskal, Floyd-Warshall) and later NP-completeness reductions. The divide-and-conquer vs. greedy vs. DP distinction is foundational: on the midterm you identify paradigms, but later in the course you will need to design algorithms within a specific paradigm and prove optimality. Potential functions connect to the computability side of the course as well, since proving an algorithm terminates is closely related to showing a Turing machine halts.
EECS 376, Foundations of Computer Science, UMich, midterm review, GCD, greatest common divisor, Euclidean algorithm, Karatsuba multiplication, fast multiplication, Master Theorem, recurrence relation, divide and conquer, greedy algorithm, dynamic programming, DP table, bottom-up DP, potential function, termination proof, Slowsort, MajorityElement, majority element algorithm, algorithm paradigm, recursion, asymptotic analysis, Big-O, Omega, Theta, algorithm correctness, proof by contradiction