Skip to content
Documentation
Part I: Fundamental Data Structures & Core Algorithms
Chapter 4A: Computational Theory & Advanced Algorithms
Chapter 4A References

Chapter 4A References

Books

  • Sanjeev Arora and Boaz Barak, The Nature of Computation. Polynomial-time reductions, NP-completeness, and complexity classes.
  • Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Randomized sampling, hashing, and probability bounds.
  • John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation. Finite automata, regular languages, and algorithmic techniques.
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications. Convex hulls, closest pairs, and geometric primitives.

Websites

SourceTopics
Princeton Algorithms: ReductionsNP-completeness and polynomial-time reductions
Princeton Algorithms: Reservoir SamplingUniform stream sampling and its space cost
RE2 SyntaxSupported regular-expression syntax and finite-automaton execution
Princeton Algorithms: Closest PairDivide-and-conquer geometry and the constant-sized neighbor check
Computational Geometry Algorithms: Convex Hull (Graham Scan, Jarvis March), Closest-Pair of Points, Line Segment Intersection