(Fall 2021) CS 581 - Theory of computation

Resource

Suggested texts/readings

  • [AB] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Online access via PSU Library
  • [W] Avi Wigderson. Mathematics and Computation. Princeton University Press, 2019. Online access Link

Review: introduction to ToC

  • [S3] Michael Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012. PSU library link. An excellent introductory text. Review the basics and test your preparedness.
  • [Watrous] John Watrous. Introduction to the Theory of Computing, Lecture notes. Link.
  • [B] Boaz Barak. Introduction to Theoretical Computer Science. Link. Online textbook, mostly introductory, and providing alternative perspectives sometimes.

LaTex

  • A Not so short intro to LaTex PDF, a thorough introduction to LaTeX, and guide on good style.
  • Online TeX editors, such as Overleaf, are convinent to get you started. Overleaf also maintains a nice set of tutorials. It’s most effective just to open a template tex file and tweak it!