Chapter 4A: Computational Theory & Advanced Algorithms

Computational theory explains what can be computed efficiently, how random choices trade certainty for speed, how formal languages become executable machines, and how algorithms reason about geometric objects.

• Computational Complexity Theory: P vs NP, NP-Completeness, NP-Hardness, and Polynomial-Time Reductions
• Randomized & Approximation Algorithms: Reservoir Sampling, Fisher-Yates, MinHash, and Approximation Bounds
• Finite Automata & Formal Languages: NFA/DFA Constructions, Thompson’s Construction, and Regex Engine Compilation
• Computational Geometry Algorithms: Convex Hull (Graham Scan, Jarvis March), Closest-Pair of Points, Line Segment Intersection
• Chapter 4A References