Difficulty: Intermediate | Prerequisites: basic data structures (trees, graphs), Big-O notation, proof by induction.
This topic covers the algorithmic backbone of EECS 376: how to design algorithms, analyse their running time, and classify problems by difficulty. It spans concrete data structures (BSTs, AVL trees), fundamental graph algorithms (Kruskal's, Floyd-Warshall), number-theoretic algorithms (Euclidean, Karatsuba), the three main algorithm paradigms (greedy, divide and conquer, dynamic programming), complexity classes (P, NP, NP-Complete), and a handful of practical tools (bash, git, Makefiles, unit testing). You should be comfortable with recursion, basic graph terminology and asymptotic notation before diving in.
TL;DR: Algorithm design in EECS 376 revolves around choosing the right paradigm (greedy, divide and conquer, or DP), proving correctness, and analysing runtime with recurrences and the Master Theorem. Complexity theory then asks which problems are tractable (P), verifiable (NP), or provably as hard as the hardest NP problems (NP-Complete).
Binary Search Tree (BST)
A rooted binary tree where every node's left descendants hold smaller values and right descendants hold larger values. Supports search, insert and delete in O(h) time, where h is the tree height.
In-order predecessor / in-order successor
The predecessor is the largest value in the left subtree; the successor is the smallest value in the right subtree. Used when deleting a node with two children.
AVL tree
A self-balancing BST where the balance factor of every node is -1, 0 or +1. Guarantees O(log n) height.
Balance factor
The difference between the height of a node's left subtree and the height of its right subtree. In an AVL tree this must be at most 1 in absolute value.
Rotation (tree)
A local restructuring operation (left or right rotation) that restores balance in an AVL or Red-Black tree after an insert or delete, while preserving the BST ordering property.
Minimum Spanning Tree (MST)
A subset of edges connecting all vertices of a weighted graph with the minimum possible total edge weight and no cycles.
Kruskal's algorithm
A greedy MST algorithm that sorts edges by weight and adds each edge that does not create a cycle, using a union-find structure. Runs in O(E log E).
Floyd-Warshall algorithm
An all-pairs shortest path algorithm using dynamic programming over intermediate vertices. Runs in O(V³).
Euclidean algorithm
Computes the greatest common divisor (GCD) of two integers by repeatedly replacing (x, y) with (y, x mod y) until the remainder is 0. Always terminates; the potential function Φ(x, y) = x + y strictly decreases each step.
Potential function
A non-negative function that strictly decreases with each iteration of an algorithm, proving termination (it must eventually reach its lower bound).
Master Theorem
A tool for solving recurrences of the form T(n) = aT(n/b) + f(n). Compares f(n) against n^(log_b(a)) to determine the overall complexity.
In simple terms, it gives you the runtime of a divide-and-conquer algorithm directly from its recurrence, without unrolling.
Karatsuba algorithm
A divide-and-conquer method for multiplying two n-digit numbers using only three recursive multiplications instead of four, achieving O(n^1.585) instead of O(n²).
Greedy algorithm
An algorithm that makes the locally optimal choice at each step, hoping to reach a global optimum. Works for MST (Kruskal's) and some scheduling problems; does not work for all optimisation problems.
Divide and conquer
An algorithm paradigm with three steps: divide the problem into smaller subproblems, conquer (solve) them recursively, and combine their solutions.
P (complexity class)
The set of decision problems solvable by a deterministic Turing machine in polynomial time.
NP (complexity class)
The set of decision problems whose solutions can be verified in polynomial time, given a certificate.
Think of it as: you might not know how to find the answer quickly, but if someone hands you a candidate answer, you can check it fast.
NP-Complete
A problem that is in NP and is at least as hard as every other NP problem (every NP problem reduces to it in polynomial time). Examples: 3-SAT, Vertex Cover, Hamiltonian Path.
Generator (in RSA/modular arithmetic)
An element g of a group such that its powers g, g², g³, ... produce every element of the group. Preferred for the public exponent because the wider range makes the discrete logarithm harder to compute.
When deleting a node with two children, replace it with either its in-order predecessor (max of the left subtree) or its in-order successor (min of the right subtree).
Example from the exam: a node with value 12 has left child 6 (children 3, 10) and right child 15 (right child 17). Deleting 12: the in-order predecessor is 10 (largest in left subtree), the in-order successor is 15 (smallest in right subtree). Valid replacements: 10 or 15.
A self-balancing BST where the balance factor (height of left subtree minus height of right subtree) of every node stays in {-1, 0, +1}.
When an insertion or deletion violates this property, one or two rotations restore balance.
Rotations are local operations that restructure parent-child links to reduce height while preserving the BST ordering property. They do not sort, delete or convert the tree.
Computes GCD(x, y) by repeatedly applying (x, y) → (y, x mod y) until the remainder is 0.
Termination proof: the potential function Φ(x, y) = x + y is a non-negative integer that strictly decreases at each step, so it must eventually reach its lower bound.
Worst-case inputs are consecutive Fibonacci numbers, which produce the most iterations. Among (800, 300), (100, 55), (29, 18) and (19, 11), the pair (29, 18) takes the most steps (6 iterations), because 29 and 18 are closest to consecutive Fibonacci numbers in that range.
The Master Theorem applies to recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1.
Case 1: if f(n) = O(n^d) with d < log_b(a), then T(n) = O(n^(log_b(a))).
Case 2: if d = log_b(a), then T(n) = O(n^d log n).
Case 3: if d > log_b(a), then T(n) = O(n^d).
The Master Theorem cannot be used when the recurrence has multiple recursive terms with different reduction rates, such as T(n) = 2T(n/2) + T(n-1) + O(1). The T(n-1) term prevents the recurrence from fitting the standard aT(n/b) + f(n) form.
Example: MajorityElement uses T(n) = 2T(n/2) + O(n). Here a = 2, b = 2, f(n) = O(n), so d = 1 and log_b(a) = 1. Case 2 gives T(n) = O(n log n).
Multiplies two n-digit numbers using three recursive multiplications instead of four.
Split x = a × 10^(n/2) + b and y = c × 10^(n/2) + d. Compute M₁ = a × c, M₂ = b × d, M₃ = (a + b)(c + d).
Combine: x × y = M₁ × 10^n + (M₃ - M₁ - M₂) × 10^(n/2) + M₂.
Example: 59 × 55. a = 5, b = 9, c = 5, d = 5. M₁ = 25, M₂ = 45, M₃ = 14 × 10 = 140. Result = 2500 + (140 - 25 - 45) × 10 + 45 = 2500 + 700 + 45 = 3245.
Three steps: (1) Divide the problem into smaller subproblems similar to the original. (2) Conquer by solving subproblems recursively; if small enough, solve directly (base case). (3) Combine subproblem solutions into the solution for the original problem.
Examples: merge sort, binary search, Karatsuba multiplication, the MajorityElement algorithm.
Make the locally optimal choice at each stage without backtracking, hoping to reach a global optimum.
Correctness requires a proof (typically by exchange argument or greedy-stays-ahead).
Contrast with dynamic programming (overlapping subproblems, optimal substructure, stored results) and brute force (systematically checking all solutions).
Sort all edges by weight. Process each edge in order: add it to the MST if it does not create a cycle (checked via union-find). Stop when n-1 edges are added.
Solves the minimum spanning tree problem: connecting all vertices with minimum total edge weight.
Computes shortest paths between all pairs of vertices using dynamic programming.
Three nested loops over V vertices give O(V³) time.
Recurrence: dist(i, j, k) = min(dist(i, j, k-1), dist(i, k, k-1) + dist(k, j, k-1)), where k is the set of allowed intermediate vertices.
A "hidden city" flight from i to j means finding a path from i through j to some further destination k, where the ticket to k is cheaper than a direct ticket to j.
After running Floyd-Warshall to get all-pairs shortest distances d(i, j), compute h(i, j) = d(i, j) + min over all k of d(j, k).
The min_k(d(j, k)) term can be precomputed for each j in O(V), giving overall O(V³) for the full algorithm.
P: problems solvable in polynomial time. Example: MST (via Kruskal's or Prim's).
NP: problems whose solutions are verifiable in polynomial time given a certificate. P ⊆ NP.
NP-Complete: problems in NP that are as hard as any NP problem. Known examples: 3-SAT, Vertex Cover, Hamiltonian Path. MST is not NP-Complete (it is in P).
If P = NP, then every NP problem (including NP-Complete ones) can be solved in polynomial time. This would undermine public-key cryptography (RSA relies on the assumed hardness of factoring/discrete log). It would not make the halting problem decidable (that is a computability result, not a complexity result).
In RSA and related systems, generators are preferred for the public exponent because they span a larger range of the group through exponentiation, making the discrete logarithm problem harder for an attacker. They do not ensure primality of the public key or help compute the modulus.
bash: rm ../list.txt deletes a file in the parent directory. .. refers to the parent of the current working directory.
git: git checkout -b feature creates a new branch named "feature" and switches to it immediately. It does not merge, delete or log.
Makefiles: a rule A depending on file B triggers the command for A when B has a newer timestamp than A. This is how make avoids unnecessary rebuilds.
Unit testing: tests a single individual component or method in isolation. Contrast with integration testing (modules together), system testing (whole system), and load testing (performance under stress).
Master Theorem (Case 2 example): T(n) = 2T(n/2) + O(n). a = 2, b = 2, d = 1. log₂(2) = 1 = d. Result: T(n) = O(n log n).
Floyd-Warshall runtime: O(V³), from three nested loops over all V vertices.
Karatsuba combination formula: x × y = M₁ × 10^n + (M₃ - M₁ - M₂) × 10^(n/2) + M₂, where M₁ = ac, M₂ = bd, M₃ = (a+b)(c+d).
Euclidean algorithm potential function: Φ(x, y) = x + y. Strictly decreasing and bounded below by 0, proving termination.
Hidden city cost: h(i, j) = d(i, j) + min_k d(j, k), where d is the all-pairs shortest path matrix from Floyd-Warshall.
Socially distant string recurrence: S(n) = S(n-1) + S(n-6) for n > 6, with S(n) = n + 1 for n ≤ 6.
Kruskal's runtime: O(E log E) (dominated by sorting edges).
MST algorithms (Kruskal's, Prim's) are used in network design: laying cable, designing circuit boards, connecting infrastructure at minimum cost.
Floyd-Warshall and shortest-path algorithms power routing in GPS systems, logistics networks and the "hidden city ticketing" trick that travellers use to find cheaper flights by booking a connection and disembarking early.
The Karatsuba algorithm is the basis for fast multiplication in arbitrary-precision arithmetic libraries. Every time your phone multiplies very large numbers (cryptographic keys, for instance), an algorithm in this family is running.
NP-completeness explains why scheduling, timetabling and combinatorial optimisation problems in industry are typically solved with heuristics rather than exact algorithms.
Students often think the Master Theorem works on any recurrence. It requires the specific form T(n) = aT(n/b) + f(n). A recurrence with multiple recursive terms at different reduction rates (e.g. T(n/2) and T(n-1) in the same equation) cannot use it.
Students sometimes confuse the in-order predecessor with the left child. The predecessor is the rightmost (maximum) node in the left subtree, not the left child itself.
MST is not NP-Complete. It is solvable in polynomial time. Students sometimes lump all graph problems together, but MST (Kruskal's, Prim's) is firmly in P.
Students assume P = NP would solve everything. It would not affect undecidable problems (like the halting problem). Computability and complexity are separate questions.
Rotations in AVL trees do not sort the tree. The BST property is maintained throughout; rotations only adjust the structure to restore the balance-factor constraint.
⚠️ BST deletion with two children: know both the in-order predecessor and in-order successor approaches. The exam tests which values are valid replacements for a given tree.
⚠️ Master Theorem: be able to identify a, b, d and the correct case. Also know when the theorem does not apply.
⚠️ Karatsuba: the exam asks you to walk through the three multiplications and the combination formula. Practise splitting digits and computing M₁, M₂, M₃.
⚠️ Floyd-Warshall runtime (O(V³)) and its application to hidden-city flights are both tested.
⚠️ Know which problems are in P vs NP-Complete. MST is in P; 3-SAT, Vertex Cover and Hamiltonian Path are NP-Complete.
⚠️ Practical tools (bash, git, Makefiles) appear as quick multiple-choice questions. Know rm ../file, git checkout -b, and Makefile timestamp logic.
True or false: the balance factor of an AVL node is the total number of nodes in its left subtree. (False: it is the difference in height between the left and right subtrees.)
Fill in the blank: Kruskal's algorithm solves the ______ problem. (Minimum spanning tree.)
True or false: the Master Theorem can be applied to T(n) = 2T(n/2) + T(n-1) + O(1). (False: the T(n-1) term prevents it.)
Fill in the blank: Floyd-Warshall runs in O(______). (V³.)
True or false: Hamiltonian Path is in P. (False: it is NP-Complete.)
Q: When removing value 12 from a BST where 12 has left child 6 (children 3, 10) and right child 15 (right child 17), which values could validly replace 12?
A: 10 or 15. The in-order predecessor is 10 (max of left subtree) and the in-order successor is 15 (min of right subtree).
Q: Which pair requires the most iterations of the Euclidean algorithm: (800, 300), (100, 55), (29, 18), or (19, 11)?
A: (29, 18). It takes 6 steps: (29,18) → (18,11) → (11,7) → (7,4) → (4,3) → (3,1) → (1,0). Worst cases are pairs near consecutive Fibonacci numbers.
Q: Why is the Master Theorem unusable for T(n) = 2T(n/2) + T(n-1) + O(1)?
A: The T(n-1) term prevents the recurrence from fitting the required form aT(n/b) + f(n).
Q: Analyse T(n) = 2T(n/2) + O(n) using the Master Theorem.
A: a = 2, b = 2, f(n) = O(n) so d = 1. log₂(2) = 1 = d, so this is Case 2: T(n) = O(n log n).
Q: Use Karatsuba to multiply 59 × 55. Show M₁, M₂, M₃ and the combination.
A: Split: a = 5, b = 9, c = 5, d = 5. M₁ = 5 × 5 = 25. M₂ = 9 × 5 = 45. M₃ = (5+9)(5+5) = 14 × 10 = 140. Result = 25 × 100 + (140 - 25 - 45) × 10 + 45 = 2500 + 700 + 45 = 3245.
Q: Which of these is NOT NP-Complete: 3-SAT, Vertex Cover, Minimum Spanning Tree, Hamiltonian Path?
A: Minimum Spanning Tree. It is solvable in polynomial time (e.g. Kruskal's), so it is in P.
Q: What is the purpose of a rotation in an AVL tree?
A: To reduce the height of the tree by rebalancing nodes, restoring the balance-factor constraint while maintaining the BST ordering property.
Q: Describe an algorithm based on Floyd-Warshall for the hidden city ticketing problem.
A: Run standard Floyd-Warshall to compute all-pairs shortest distances d(i, j). For the hidden city cost from i to j, compute h(i, j) = d(i, j) + min over all k of d(j, k). The idea is that j is an intermediate stop on a cheaper flight to some further destination k. Precomputing min_k(d(j, k)) for each j keeps the total complexity at O(V³).
Q: What is the result of running git checkout -b feature?
A: It creates a new branch named "feature" and switches to it.
Q: In a Makefile, when does the command for rule A execute if A depends on file B?
A: When file B has a newer timestamp than target A (meaning A is out of date with respect to its dependency).
This material connects directly to computability theory: complexity classes (P, NP) only make sense for decidable problems, and reductions in NP-completeness proofs mirror the mapping reductions used for undecidability. The Master Theorem and recurrence analysis appear whenever a divide-and-conquer algorithm is introduced. Graph algorithms (Floyd-Warshall, Kruskal's) recur in networking, operations research and database query optimisation courses. RSA and generators connect to number theory and the broader cryptography curriculum.
Related Terms / Search Tags
BST deletion, in-order predecessor, in-order successor, AVL tree, balance factor, rotation, minimum spanning tree, MST, Kruskal's algorithm, Floyd-Warshall, all-pairs shortest paths, hidden city ticketing, Euclidean algorithm, GCD, potential function, Master Theorem, recurrence relation, Karatsuba multiplication, divide and conquer, greedy algorithm, dynamic programming, P, NP, NP-Complete, 3-SAT, Vertex Cover, Hamiltonian Path, RSA, generator, public exponent, bash, git checkout, Makefile, unit test, EECS 376, foundations of computer science, University of Michigan