This course introduces computer science theory through the study of abstract machines, grammars, languages, decidability, and NP-completeness. Students evaluate fundamental limits of these machines and grammars and classify languages according to the Chomsky hierarchy; apply various techniques to prove facts about these machines, grammars, and languages; recognize the difference between problems that are and are not solvable; and determine when a problem is NP-complete. Throughout, the course links fundamental computer science theory to modern-day practical computing devices and computational problems.
