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.
Grounds the cadet in the essentials of theory of computation: formal languages, automata, and computability theory. Frames computation in the context of the Chomsky hierarchy, the polynomial and exponential time hierarchies, and the decidability hierarchy. Explores fundamental limits on computation: what problems can never be solved, what problems can be solved but are intractable, and the class NP of problems that are thought to be intractable, but for which no proof of intractability exists to date.
Grounds the cadet in the essentials of theory of computation: formal languages, automata, and computability theory. Frames computation in the context of the Chomsky hierarchy, the polynomial and exponential time hierarchies, and the decidability hierarchy. Explores fundamental limits on computation: what problems can never be solved, what problems can be solved but are intractable, and the class NP of problems that are thought to be intractable, but for which no proof of intractability exists to date.
Grounds the cadet in the essentials of theory of computation: formal languages, automata, and computability theory. Frames computation in the context of the Chomsky hierarchy, the polynomial and exponential time hierarchies, and the decidability hierarchy. Explores fundamental limits on computation: what problems can never be solved, what problems can be solved but are intractable, and the class NP of problems that are thought to be intractable, but for which no proof of intractability exists to date.
