Instructor: Dawn Nye
Office Hours: Noyce 2610 at TTh 12:00-1:50pm (or by request/whenever my door is open)
Mentor: Tanmaie Kailash (Section 01) and Austin Yu (Section 02)
Mentor Sessions: Wednesdays 7-8pm and Sundays 4-5pm at Noyce 3812
Meeting Times:
T 10:00-11:50am and Th 10:00-10:50am at Noyce 1530 (Section 01)
T 2:00-3:50pm and Th 2:00-2:50pm at Noyce 2245 (Section 02)
Textbook: Introduction to the Theory of Computation (3rd Edition) by Michael Sipser
Computer science is as much concerned with the analysis of computation as it is with implementation. In the study of algorithms, for example, we frequently analyze best, worst, and (when appropriate) average and amortized case runtimes. We might instead analyze the space requirements of an algorithm. For example, most sorting algorithms can be done in place requiring no more than linear space. Reachability (roughly speaking finding a path) can be done in as little as log space. Pursuing a formalization of these notions allows us to argue about the relative difficulty/tractability of problems or to determine if they are impossible outright.
In this course, we study the theory of computation to formally model problems and study their relationships with one another. In doing so, we can gain insight into not just a problem but all related problems. We can also identify problems which are intractable and might require probabilistic or approximation algorithms to solve with reasonable resources. Some problems, we will discover, can provably never have a solution, a fact which an imprecise understanding can often obscure.
Order of Topics and Readings
| Topic* | Associated Reading† |
|---|---|
| REVIEW | |
| Introductions | |
| Proofs | Chapter 0 |
| AUTOMATA AND LANGUAGES | |
| Formal Languages Deterministic Finite Automata | Section 1.1 |
| Nondeterminism | Section 1.2 |
| DFA and NFA Equivalence | |
| Closure Properties | |
| Regular Expressions | Section 1.3 |
| Decidable Properties | |
| Irregular Languages | Section 1.4 |
| Myhill-Nerode Theorem | Problems 1.51 and 1.52 |
| Kolmogorov Complexity | A New Approach to Formal Language Theory by Kolmogorov Complexity (via ProQuest Central) [Suggested] Section 6.4 [for the ambitious] |
| Context-Free and Context Sensitive Languages | Chapter 2 [Suggested] |
| COMPUTABILITY THEORY | |
| Turing Machines | Section 3.1 |
| Variants, Other Models, and the Church Turing Thesis | Sections 3.2 and 3.3 |
| Decidability | Section 4.1 |
| Diagonalization | Section 4.2 |
| Undecidability | Sections 5.1 |
| Rice’s Theorem | Problem 5.28 |
| Reducibility & Reductions | Section 5.3 |
| The Arithmetic Hierarchy | Section 6.3 |
| COMPLEXITY THEORY | |
| Asymptotics | Section 7.1 |
| P | Section 7.2 |
| NP | Section 7.3 |
| Graphs | |
| NP-Complete | Section 7.4 Section 7.5 |
| NP vs co-NP | |
| Space Complexity | Section Introduction |
| Savitch’s Theorem | Section 8.1 |
| PSPACE | |
| L and NL | |
| Space-Time Hierarchy | Section 9.1 [Suggested Skim] |
| SELECTED TOPICS | |
| Circuit Complexity | Section 9.3 |
| The Time-Circuit Link | |
| The Cook-Levine Theorem Revisited | |
| AC and NC | |
| P/Poly | |
| Probabilistic Algorithms | |
| Approximation Algorithms |
* Some subject material may be omitted according to actual progress during class
† Supplemental readings beyond the scope of the textbook may appear at future dates
Learning Outcomes
- Formal Automata and Languages
- Represent a problem using finite automata
- Deterministic and non-deterministic finite automata
- Regular languages
- Equivalence of NFAs and DFAs
- Prove closure and algorithmic properties of the regular languages
- Prove the irregularity of a problem
- Pumping Lemma
- Myhill-Nerode Theorem
- Kolmogorov Complexity
- Represent a problem using a context-free model of computation
- Stack machines
- CF grammars
- Prove a language is not context-free
- Represent a problem using a context-sensitive model of computation
- Linear bounded automata
- CS grammars
- Represent a problem using a Turing machine
- Prove closure and algorithmic properties of Turing machines
- Represent a problem using finite automata
- Computability Theory
- Prove the decidability of a problem
- Prove the decidability of a problem via an explicit construction
- Prove the undecidability of a problem via a reduction
- Prove the undecidability of a problem via Rice’s Theorem
- Prove that a problem is recognizable, co-recognizable, or neither
- Describe the practical ramifications of computational undecidability
- Summarize the Church-Turing Hypothesis and Gödel’s Incompleteness Theorems
- Prove the decidability of a problem
- Computational Complexity
- Prove that a problem is in a particular time complexity class
- Prove that a problem is NP-complete by way of a reduction
- Explain the practical ramifications of P vs NP
- Describe practical problem-solving strategies for dealing with intractable problems
- Approximation algorithms
- Probabilistic algorithms
- As Time Permits
- Prove that a problem is in a particular space complexity class
- Formally define each of the major complexity classes
- Describe the essential characteristics of a problem belonging to each complexity class
- Describe the practical relationships between various time/space complexity classes
- Prove that a problem is in a particular circuit complexity
- Understand and utilize oracle machines for higher levels of computation
- Understand other models of computation and be able to generate new ones
- Prove that a problem is in a particular space complexity class