CS273: Intro to Theory of Computation


Fall 2006   Prof. Fleck and Parthasarathy

This is a preliminary outline of lecture topics and corresponding readings from the textbook. As the term progresses, we will correct it and add links to the slides from lecture. The links under the column "Slides" may be prepared slides, handouts, and/or screen-captures from lectures.

Week Date Lecture Material covered Slides Readings/Comments Homeworks
1 8/23 1 Administrivia, overview, motivation lecture    
2 8/29 2 Types of proofs, some familiar and some new lecture
sample proof 		Chapter 0  
8/31 3 Equivalence classes, strings and languages, intro to finite automata lecture
Section 1.1  
3 9/5 4 Formalizing DFA's and FST's, closure under union lecture Section 1.1 HW 0 (warm up)
due Tuesday
9/7 5 More examples of DFAs, more proofs about DFAs lecture Section 1.1  
4 9/12 6 NFA's, closure under three regular operations lecture Section 1.2 HW 1 (DFA's)
due Tuesday
9/14 7 Equivalence of NFA's and DFA's, intro regular expressions lecture Sections 1.2 and 1.3  
5 9/19 8 Equivalence of regular expressions and NFA's, closure under homomorphism lecture Section 1.3 HW 2 (DFA's and NFA's)
due Monday
9/21 9 Proving languages non-regular (via pumping lemma, via closure properties) lecture pumping lemma help page Section 1.4  
6 9/26 10 Congruence-based characterization of regular languages lecture [handout:Illinois-Compass] HW 3 (NFA's and regular expressions)
due Monday
9/28 11 Context-free grammars, parse trees, ambiguity, CNF lecture grammar example Section 2.1  
7 10/3   first midterm in evening
lecture = review 		lecture Monday is Yom Kippur  
10/5 12 Pushdown automata lecture Section 2.2  
8 10/10 13 More examples of PDA's, PDA's are equivalent to context-free grammars lecture Section 2.2 HW 4 (pumping lemma and CFG's)
due Monday
10/12 14 Non-context-free languages, pumping lemma, closure properties, applications of CFLs lecture Section 2.3
Friday is drop date		  
9 10/17 15 Turing machines lecture Section 3.1 HW 5 (CFG's and PDA's)
due Monday
10/19 16 Variations on Turing machines: multi-tape, non-deterministic, enumerators lecture Section 3.2
Saturday is Diwali		  
10 10/24 17 Simulating real computer features on a TM lecture [handout]
Monday is Eid ul-Fitr		 HW 6 (TM's and PDA's)
due Monday
10/26 18 Encoding problems and decidability lecture Section 3.3, Section 4.1  
11 10/31 19 More decidable problems, programs that read programs lecture Section 4.1
Halloween		  
11/2   second midterm in evening
lecture = review 		     
12 11/7 20 The halting problem lecture Section 4.2  
11/9 21 Reductions and undecidable automata problems, dovetailing lecture Section 5.1  
13 11/14 22 Undecidable problems on linear bounded automata and CFLs lecture Section 5.1 HW 7 (TM's, decidability, interleaving)
due Monday
11/16 23 More examples of reductions, Rice's theorem lecture
help on reduction proofs 		Section 5.1  
break 11/21   too much fun with planes, trains, and automobiles A poem on undecidability Thanksgiving break  
11/23   eating way too much turkey   Thanksgiving break  
14 11/28 24 Post's Correspondence Problem and 2D tilings lecture
pretty aperiodic tilings 		Section 5.2 HW 8 (undecidability, reductions)
due Wednesday
11/30 25 Algorithms for automata I lecture    
15 12/5 26 More algorithms for automata II
Course evals		 lecture    
12/7 27 Recap, look ahead to other courses     HW 9 (PCP)
due Friday
16 12/12   exam week      
12/14   Final 7-10pm