Syllabus

Com S 531
Course Description and Syllabus

Course Description

This course covers topics in theory of computation. We will study abstract models of computational machines. We study the power of these machines and determine which problems are computable. We then study the time and space complexity of these problems - the amount of time and space required to solve these problems on these machines. An undergraduate level background in theory of computation will be expected, including a basic understanding of regular and context-free languages, finite automata, pushdown automata and Turing Machines.
 

Syllabus

The following is a brief outline of the topics to be covered in the course.

1. Basic Concepts Properties of sets, relations and functions. Proof techniques. Languages, Grammars and Machines.
2. Regular Languages and Finite Automata Regular Expressions. Deterministic and Nondeterministic Finite Automata. Regular sets and closure properties. Pumping Lemma. Myhill-Nerode Theorem.
3. Context-Free Languages Context-Free Grammars and Push-down Automata. Pumping Lemma for ContextFree Languages. Deterministic Push-Down Automata. Deterministic Context-free, Linear and Ambiguous Languages. Parsing. Chomsky and Greibach Normal Forms.
4. Computable Functions and Turing Machines Deterministic and Nondeterministic Turing Machines. Computable total and partial functions. Turing Machine enumeration and Universal Turing Machines.
5. Undecidability Halting Problem. Turing and Many-one Reducibility. Recursively Enumerable, Recursive and Undecidable Problems.
6. Computational Complexity Algorithm Analysis on a Turing Machine. Polynomial time and space complexity. NP-Completeness and reductions.
7. Distributed Computation Synchronous vs. Asynchronous Processors. Synchronous vs. Asynchronous Communication. Failures. Impossibility Results.

Back to CS531 homepage
Last Modified :