Princeton
University

COS 487/MAT 407


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).
Lectures: TueThu 1:302:50pm, Room: Friend Center 016, Signup on Piazza: Link
Professor: Gillat Kol
 316 CS Building gkol@princeton.edu
TA: Raghuvansh Saxena rrsaxena@princeton.edu
Honor Code for This Course
The grade is based on problem sets. You are encouraged to work in groups upto 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.Date 
Lecture topics 
Reading 
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.  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.21.3 of text. 
Lecture 3, Sep 21 
Topic: Finite Automata (cont'd)  Regular expressions: equivalence to DFAs.  Nonregular languages: the pumping lemma. 
Chapters 1.31.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.  Multitape Turing machine: definition, equivalence to singletape 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 ChurchTuring Thesis.  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 ChurchTurning theorem (checking whether a statement has a proof is undecidable). 
Notes on unprovable statements by Luca Trevisan. 