**Instructor:** Dawn Nye**Office Hours:** MWF 4:00 PM – 5:00 PM (or by request/whenever my door is open)**Mentor:** Moiz Yousufi**Mentor Sessions:** TBD**Meeting Times:** MWF 1:00 PM – 1:50 PM (Science 3820)**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.

## Schedule

Date | Topic* | Reading† | Assignments |
---|---|---|---|

8/26 | Introductions | ||

8/29 | Proofs | Chapter 0 | |

8/31 | Proofs | ||

9/2 | Formal Languages Deterministic Finite Automata | Section 1.1 | HW1 |

9/5 | Nondeterminism | Section 1.2 | |

9/7 | DFA and NFA Equivalence | ||

9/9 | Closure Properties | HW2 HW1 Due | |

9/12 | Regular Expressions | Section 1.3 | |

9/14 | Decidable Properties | ||

9/16 | Irregular Languages | Section 1.4 | HW3 HW2 Due HW1 Resubmission Due |

9/19 | Myhill-Nerode Theorem | Problems 1.51 and 1.52 | |

9/21 | Kolmogorov Complexity | A New Approach to Formal Language Theory by Kolmogorov Complexity (via ProQuest Central) [Suggested] Section 6.4 [for the ambitious] | |

9/23 | Context-Free and Context Sensitive Languages | Chapter 2 [Suggested] | Exam 1 |

9/26 | Turing Machines | Section 3.1 | HW3 Due |

9/28 | Variants, Other Models, and the Church-Turing Thesis | Sections 3.2 and 3.3 | |

9/30 | Decidability | Section 4.1 | HW4 HW2 Resubmission Due |

10/3 | Diagonalization | Section 4.2 | Exam 1 Due |

10/5 | Undecidability | Sections 5.1 | |

10/7 | Rice’s Theorem | Problem 5.28 | HW5 HW4 Due |

10/10 | Reducibility & Reductions | Section 5.3 | |

10/12 | HW3 Resubmission Due | ||

10/14 | HW5 Due | ||

Fall Break | |||

10/24 | Asymptotics | Section 7.1 | HW 6 |

10/26 | P | Section 7.2 | |

10/28 | NP | Section 7.3 | |

10/31 | Graph Notes NP-Complete | Section 7.4 | HW7 HW6 Due |

11/2 | NP vs co-NP | ||

11/4 | Section 7.5 | ||

11/7 | Exam 2HW7 Due HW4 Resubmission Due | ||

11/9 | Space Complexity | Section Introduction | |

10/10 | HW5 Resubmission Due | ||

11/11 | Savitch’s Theorem | Section 8.1 | |

11/14 | PSPACE | HW8Exam 2 Due | |

11/16 | L and NL | ||

11/18 | NL Continued | ||

11/21 | Space-Time Hierarchy | Section 9.1 [Suggested Skim] | HW9 HW8 Due |

11/23 | Circuit Complexity | Section 9.3 | |

Approximately Thanksgiving | |||

11/28 | The Time-Circuit Link | HW10 HW9 Due HW6 Resubmission Due | |

11/30 | The Cook-Levine Theorem Revisited | ||

12/2 | AC and NC | ||

12/5 | P/Poly | Exam 3HW10 Due | |

12/7 | Probabilistic Algorithms | ||

12/9 | Approximation Algorithms | HW7 Resubmission Due HW8 Resubmission Due HW9 Resubmission Due | |

12/14 | Exam 3 DueHW10 Resubmission Due |

* Subject material on any given day may drift forward or back 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
- Kolmogorov approach
- Myhill-Nerode Theorem

- 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