CS 39: Theory of Computation
Spring 2019 | 10 hour (MWF 10:10-11:15, x-hr Th 12:15-13:05) | Sudikoff 115

This page will be updated frequently with current and upcoming topics.

Any content that's colored light gray is tentative and subject to change.

Homework sets will be available on this course's Canvas page (under Files). Please read the policies section of the course website for submission instructions, the lateness policy (which is absolutely strict), grading standards, and the academic honor principle.

Lectures, Quizzes, and Submissions Due

In the table below, all references are to the required textbook (Sipser). Notation like "p34" refers to a particular page number; notation like "2.1" refers to a section number; notation like "Ch 3" refers to an entire chapter.

# Date Class Topics / Other Events References
1 Mon Mar 25 Welcome, administrivia, overview; Mathematical notation Slides; 0.1, 0.2, 0.3
S Tue Mar 26 Nothing to submit
2 Wed Mar 27 Types of proof (direct, contradiction, induction) Slides; 0.4
3 Thu Mar 28 Strings and languages; Finite automata; Basic DFA examples 1.1 up to p34
4 Fri Mar 29 Further DFA examples; formalization as (Q,Σ,δ,q0,F) 1.1
5 Mon Apr 01 NFA; examples and formalization; union and concatenation 1.2
S Tue Apr 02 Homework 1 due by 22:00:00
6 Wed Apr 03 The regular operations; Regular expressions 1.3 up to p69
7 Thu Apr 04 Kleene's Theorem; Conversion of RegExp to NFA Notes; 1.3 up to p69
8 Fri Apr 05 Kleene's Theorem II: Conversion of NFA to DFA 1.3
9 Mon Apr 08 Kleene's Theorem III: of DFA to RegExp Notes; 1.3
S Tue Apr 09 Homework 2 due by 22:00:00
10 Wed Apr 10 The pumping lemma; proving non-regulartiy 1.4
11 Thu Apr 11 Proof of pumping lemma; more non-regularity proofs 1.4
12 Fri Apr 12 Non-regularity via closure properties; Pushdown automata 2.2 up to p116
Q Mon Apr 15 Quiz 1: closed notes, in class
S Tue Apr 16 Homework 3 due by 22:00:00
13 Wed Apr 17 Several examples of PDAs 2.2 up to p116
14 Thu Apr 18 Context-free grammars; a sophisticated completeness proof Notes; ; 2.1 up to p106
15 Fri Apr 19 Formal definition of PDA, CFG; Closure properties 2.1 up to p106
16 Mon Apr 22 Ambiguity; Chomsky Normal Form 2.1
S Tue Apr 23 Homework 4 due by 22:00:00
17 Wed Apr 24 Equivalence of CFGs and PDAs, I Notes; 2.2 up to p120
18 Thu Apr 25 Equivalence of CFGs and PDAs, II 2.2
19 Fri Apr 26 Pumping lemma for CFLs; applications 2.3
20 Mon Apr 29 CFL wrap-up; Turing Machines; examples; formal definition 3.1; Simulators [1], [2], [3]
S Tue Apr 30 Midterm exam due by 22:00:00
21 Wed May 01 Multi-tape TMs; Equivalence with single-tape TMs Slides; 3.2 up to p178
22 Thu May 02 Nondeterministic TMs; The RAM model; Church-Turing Thesis Slides; 3.2, 3.3
23 Fri May 03 Enumerator TMs; Connections with deciders/recognizers 3.2
24 Mon May 06 Decision problems for major language classes: ADFA, ACFG, ATM; Undecidability 4.1
S Tue May 07 Homework 5 due by 22:00:00
25 Wed May 08 More decision problems: EX, ALLX, EQX, INTX; Undecidability and unrecognizability 4.2
26 Thu May 09 Reductions, mapping reductions, and their applications 5.1 up to p220, 5.3
27 Fri May 10 Time complexity; P and NP 7.1, 7.2, 7.3
Q Mon May 13 Quiz 2: closed notes, in class
S Tue May 14 Homework 6 due by 22:00:00
28 Wed May 15 NP-completeness and polynomial time reductions (intro) Slides; 7.4 to p304, 7.5 to p318
29 Thu May 16 NP-completeness of SAT (without proof), 3-SAT, IND-SET Slides; 7.5
30 Fri May 17 NP-completeness of CLIQUE, UHAMCYCLE, TSP 7.5
31 Mon May 20 NP-completeness of 3-COL; Tractability of 2-COL and 2-SAT 7.5
S Tue May 21 Homework 7 due by 22:00:00
32 Wed May 22 Computational tableaux
33 Thu May 23 Undecidability of INTCFG; Unrecognizability of ALLCFG 5.1
34 Fri May 24 Proof of the Cook-Levin theorem 7.4
H Mon May 27 Memorial day
S Tue May 28 Homework 8 due by 22:00:00
35 Wed May 29 Wrap up

As you can see, we will be using every X-hour.

Reading Homework

There is reading homework associated with every class, which consists of reading the related sections of the textbook, plus any slides or notes linked from the table above. On rare occasions, the reading will cover a theorem or a small topic that was not discussed in detail in class. In any case, this reading homework is always due before the next class. There is nothing to submit and no grade for this homework, but I assume that you will nevertheless do the homework on time, every time.

Be warned that not doing this reading homework will make it very hard to follow along during the next class.