Computer Science › Specialization
A splay tree keeps no balance information at all, yet every sequence of m operations costs O(m log n): each access rotates the touched node to the root, and the potential method proves the bound by charging expensive operations against a stored "energy" that cheap operations deposit.
Karger's algorithm finds a minimum cut by contracting random edges until two vertices remain; one run succeeds with probability at least 2/(n(n-1)), so repeating it O(n^2 log n) times makes failure negligible. Markov, Chebyshev, and Chernoff bounds are the tools that turn "usually works" into a quantified guarantee.
Exact nearest-neighbor search in high dimensions degrades to scanning everything. Locality-sensitive hashing flips the goal of an ordinary hash function: similar items should collide. Banding MinHash signatures or random-hyperplane bits amplifies a small gap in collision probability into a sharp threshold, giving sublinear approximate search.
When a problem is NP-hard, settle for a provable ratio instead of the optimum. Relax the integer program to a linear program, solve it, and round: for vertex cover, keeping every vertex with LP value at least 1/2 is a 2-approximation, and greedy set cover is within a factor ln n, which is essentially the best possible unless P = NP.
An online algorithm must decide before seeing the future, so it is compared with an offline optimum that knows everything. Ski rental shows a 2-competitive break-even rule, paging shows LRU is k-competitive and no deterministic algorithm does better, and randomization against an oblivious adversary improves paging to O(log k).
A stream too large to store must be summarized in one pass with tiny memory. The Count-Min sketch estimates any item's frequency within an additive error using a few hashed counter rows, and HyperLogLog counts distinct elements to about 2% error in a few kilobytes by tracking the longest run of leading zeros in hashed values.
Measuring memory instead of time gives a different landscape: space can be reused, so nondeterminism costs only a square (Savitch: NSPACE(s) is inside SPACE(s^2)), PSPACE equals NPSPACE, and TQBF, deciding a fully quantified Boolean formula, is PSPACE-complete, which is why perfect play in many generalized games is PSPACE-hard.
BPP is the class of problems solvable in polynomial time with error at most 1/3 on every input; repetition and a Chernoff bound shrink that error exponentially. Polynomial identity testing is in BPP via Schwartz-Zippel with no known deterministic algorithm, and the conjecture that P = BPP ties randomness to circuit lower bounds.
Let the verifier ask random questions instead of reading a static certificate, and much more becomes provable: graph non-isomorphism has a simple interactive proof, and IP equals PSPACE. Zero-knowledge proofs convince the verifier a statement is true while revealing nothing else, defined by a simulator that fakes the transcript without the secret.
Modern cryptography replaces "looks hard to break" with reductions: a scheme is secure if breaking it would let you invert a one-way function. Computational indistinguishability defines pseudorandomness, a hard-core bit turns a one-way permutation into a generator that stretches a short seed, and a PRG makes a one-time pad with a short key.
Shor's algorithm would break RSA and Diffie-Hellman on a large quantum computer, so standards are moving to lattices. Learning With Errors asks to solve a linear system mod q whose equations each carry small noise; Regev showed it is as hard as worst-case lattice problems, and it underlies ML-KEM, standardized by NIST as FIPS 203 in 2024.
Computational geometry starts from one exact primitive, the orientation test (a sign of a 2x2 determinant). With it, Andrew's monotone chain builds a convex hull in O(n log n), which a reduction from sorting shows is optimal, and a sweep line that stops only at events finds all k segment intersections in O((n + k) log n).
The Voronoi diagram splits the plane into regions closest to each site, and its dual, the Delaunay triangulation, connects sites whose circumcircles are empty. Delaunay maximizes the minimum angle among all triangulations, the incircle determinant test and edge flips build it, and both structures have linear size and O(n log n) construction.
Given three realistic problems (placing warehouses so no town is far from one, counting unique visitors across a fleet of servers, and choosing a key exchange that must stay secure for 20 years), classify each one's hardness, pick the right tool from this track (approximation, sketching, geometry, or post-quantum cryptography), and state the exact guarantee the tool gives and what it gives up.
Part of the Computer Science curriculum.
A splay tree keeps no balance information at all, yet every sequence of m operations costs O(m log n): each access rotates the touched node to the root, and the potential method proves the bound by charging expensive operations against a stored "energy" that cheap operations deposit.
Karger's algorithm finds a minimum cut by contracting random edges until two vertices remain; one run succeeds with probability at least 2/(n(n-1)), so repeating it O(n^2 log n) times makes failure negligible. Markov, Chebyshev, and Chernoff bounds are the tools that turn "usually works" into a quantified guarantee.
Exact nearest-neighbor search in high dimensions degrades to scanning everything. Locality-sensitive hashing flips the goal of an ordinary hash function: similar items should collide. Banding MinHash signatures or random-hyperplane bits amplifies a small gap in collision probability into a sharp threshold, giving sublinear approximate search.
When a problem is NP-hard, settle for a provable ratio instead of the optimum. Relax the integer program to a linear program, solve it, and round: for vertex cover, keeping every vertex with LP value at least 1/2 is a 2-approximation, and greedy set cover is within a factor ln n, which is essentially the best possible unless P = NP.
An online algorithm must decide before seeing the future, so it is compared with an offline optimum that knows everything. Ski rental shows a 2-competitive break-even rule, paging shows LRU is k-competitive and no deterministic algorithm does better, and randomization against an oblivious adversary improves paging to O(log k).
A stream too large to store must be summarized in one pass with tiny memory. The Count-Min sketch estimates any item's frequency within an additive error using a few hashed counter rows, and HyperLogLog counts distinct elements to about 2% error in a few kilobytes by tracking the longest run of leading zeros in hashed values.
Measuring memory instead of time gives a different landscape: space can be reused, so nondeterminism costs only a square (Savitch: NSPACE(s) is inside SPACE(s^2)), PSPACE equals NPSPACE, and TQBF, deciding a fully quantified Boolean formula, is PSPACE-complete, which is why perfect play in many generalized games is PSPACE-hard.
BPP is the class of problems solvable in polynomial time with error at most 1/3 on every input; repetition and a Chernoff bound shrink that error exponentially. Polynomial identity testing is in BPP via Schwartz-Zippel with no known deterministic algorithm, and the conjecture that P = BPP ties randomness to circuit lower bounds.
Let the verifier ask random questions instead of reading a static certificate, and much more becomes provable: graph non-isomorphism has a simple interactive proof, and IP equals PSPACE. Zero-knowledge proofs convince the verifier a statement is true while revealing nothing else, defined by a simulator that fakes the transcript without the secret.
Modern cryptography replaces "looks hard to break" with reductions: a scheme is secure if breaking it would let you invert a one-way function. Computational indistinguishability defines pseudorandomness, a hard-core bit turns a one-way permutation into a generator that stretches a short seed, and a PRG makes a one-time pad with a short key.
Shor's algorithm would break RSA and Diffie-Hellman on a large quantum computer, so standards are moving to lattices. Learning With Errors asks to solve a linear system mod q whose equations each carry small noise; Regev showed it is as hard as worst-case lattice problems, and it underlies ML-KEM, standardized by NIST as FIPS 203 in 2024.
Computational geometry starts from one exact primitive, the orientation test (a sign of a 2x2 determinant). With it, Andrew's monotone chain builds a convex hull in O(n log n), which a reduction from sorting shows is optimal, and a sweep line that stops only at events finds all k segment intersections in O((n + k) log n).
The Voronoi diagram splits the plane into regions closest to each site, and its dual, the Delaunay triangulation, connects sites whose circumcircles are empty. Delaunay maximizes the minimum angle among all triangulations, the incircle determinant test and edge flips build it, and both structures have linear size and O(n log n) construction.
Given three realistic problems (placing warehouses so no town is far from one, counting unique visitors across a fleet of servers, and choosing a key exchange that must stay secure for 20 years), classify each one's hardness, pick the right tool from this track (approximation, sketching, geometry, or post-quantum cryptography), and state the exact guarantee the tool gives and what it gives up.