Princeton University Logo
Princeton University
Computer Science Dept.

COS 487/MAT 407
Theory of Computation

Gillat Kol

Fall 2017

Course Summary

What is computation? What can be computed in principle with unbounded computational resources? What can be computed efficiently? What can we gain by formally modeling computation and how do different models relate to one another? How can models highlight different resources of computations, such time, memory, communication, and randomness. We will consider these questions and others using a rigorous mathematical approach. We will discuss what we know as well as some of the central open problems in pure and applied mathematics, and specifically the P vs. NP problem.

Prerequisites: COS 340/341 or equivalent math background (basically, the ability to do mathematical proofs).

About This Course

Text:  Introduction to the Theory of Computation (3rd Edition) by Michael Sipser.

Grading: The grade will be based upon assignments, which will be handed out every roughly two weeks. A week will be given to complete each assignment. Collaborating with your classmates on assignments is encouraged, with the exception of the last assignment that should be completed alone. The last assignment will constitute for 30% of the grade and the rest of the assignments for 70%.
Assignments should be typed. LaTeX is strongly recommended, it's free and can be downloaded here. Here is a suggested LaTaX template for problem sets' solutions (.tex), this is what it looks like once compiled (.pdf).

Administrative Information

Lectures: Tue-Thu 1:30-2:50pm, Room: Friend Center 016, Signup on Piazza: Link

Professor: Gillat Kol - 316 CS Building 
TA: Raghuvansh Saxena 

TA office hours Tuesdays 4:30-6:00pm, CS Building tea room (second floor)  

Honor Code for This Course

The grade is based on problem sets. You are encouraged to work in groups up-to three people on each problem set, accept the last problem set (groups may change between problem sets). However, we ask that you dedicate enough time to think about each problem by yourself before consulting others. You must write up each problem solution by yourself without assistance and are asked to identify your collaborators on problem sets. You must complete the last problem set by yourself and are not allowed to discuss it with anyone until after the deadline.
You may consult your course notes, the text (Sipser), and any resource given in this webpage. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.

Schedule and Readings

Lecture topics
Lecture 1,
Sep 14
Introduction to Course Topics
- Computational models.
- Computability theory and connections to mathematical logic.
- Complexity theory and the P vs. NP problem.

Topic: Finite Automata
- Deterministic finite automata (DFA): definition, examples.
Chapter 1.1 of text.
Lecture 2,
Sep 19
Topic: Finite Automata (cont'd)
- Nondeterministic finite automata (NFA): definition, equivalence of DFAs and NFAs.
- Regular expressions: definition, examples.
Chapters 1.2-1.3 of text.
Lecture 3,
Sep 21
Topic: Finite Automata (cont'd)
- Regular expressions: equivalence to DFAs.
- Nonregular languages: the pumping lemma.
Chapters 1.3-1.4 of text.
Lecture 4,
Sep 26
Topic: Streaming Algorithms
- Definition.
- The distinguishably technique for space lower bounds.
- The most frequent element problem - space upper and lower bounds.
Notes on streaming algorithms by Ryan Williams and Luca Trevisan's.
Notes on finding the majority element of a stream.
Lecture 5,
Sep 28
Topic: Streaming Algorithms (cont'd)
- The number of distinct elements problem - space upper and lower bounds.
- The randomized streaming model: randomized algorithm for sampling and number of distinct elements.
Notes on streaming algorithms by Ryan Williams and Luca Trevisan.
Lecture 6,
Oct 3
Topic: Turing Machines
- Deterministic Turing machines: definition, examples.
- Multi-tape Turing machine: definition, equivalence to single-tape Turing machines.
Chapters 3.1,3.2 of text.
Lecture 7,
Oct 5
Topic: Turing Machines (cont'd)
- Nondeterministic Turing machines: definition, equivalence to deterministic Turing machines.
- The Church-Turing Thesis.

Topic: Computability Theory
- Definition of decidable and recognizable languages.
Chapters 3.2,3.3,4.1 of text.
Lecture 8,
Oct 10
Topic: Computability Theory (cont'd)
- Examples of decidable and recognizable languages.
- Diagonalization arguments and undecidable languages (Acceptability and Halting).
- Unrecognizable languages.
Chapter 4 of text.
Lecture 9,
Oct 12
Topic: Computability Theory (cont'd)
- Reductions: definition, examples.
Chapters 5.1,5.3 of text.
Lecture 10,
Oct 17
Topic: Computability Theory (cont'd)
- More reductions.
- Rice's theorem.
Chapter 5.1 of text.
Proof of Rice's theorem is the answer to Problem 5.28.
Next up:
Topic: Computability and Mathematical Logic - Connections
- Gödel's incompleteness theorems.
- The Church-Turning theorem (checking whether a statement has a proof is undecidable).
Notes on unprovable statements by Luca Trevisan.

Problem Sets

Problem Set 1. Out: September 20. Due: September 28. (pts:60; mean: 50.6; median: 55)
Problem Set 2. Out: October 4. Due: October 12. (pts:60; mean: 45; median: 50)