CS273

CS273: Intro to Theory of Computation

Fall 2007 Prof. Fleck and Parthasarathy

Lecture Schedule

This is a preliminary outline of lecture topics and corresponding readings from the textbook. Right now, the topic details still reflect what was taught last term. As the term progresses, we will update it for what we actually covered and add links to the handouts and slides from lecture.

The board captures are of varying legibility and are offered primarily to remind you of which topics were discussed, so you can find and read the corresponding sections in the textbook. They are not intended to be a substitute for the textbook and handouts.

Lecture Number	Date	Material covered	Board captures	Readings/Handouts/Hyperlinks	Comments
1	8/24	Administrivia, overview, motivation	Lecture 1	Chapter 0
2	8/28	Discrete math review strings intro to state machines	Lecture 2	Chapter 0, Section 1.1 Extra notes: Discrete Mathematics, by Chen Read Chap. 1, 2 and 3 (20 pgs).
3	8/30	Languages and strings DFAs, FSTs	lecture 3	Section 1.1
4	9/4	designing DFAs JFLAP demo formal definition of acceptance closure under union, intersection, complement	Lecture 4	Section 1.1 JFLAP	Monday is Labor Day Wednesday is add date
5	9/6	NFA's	Lecture 5	Section 1.2
6	9/11	closure under three regular operations equivalence of NFA's and DFA's (no epsilon transitions)	Lecture 6	Section 1.2
7	9/13	Quiz 1 Removing epsilon transitions, regular expressions	Lecture 7	Sections 1.2, 1.3	Ramadan begins
8	9/18	Regular expressions Regexs equivalent to NFAs/DFAs	Lecture 8	Section 1.3 handout
9	9/20	Proving languages non-regular using the pumping lemma	Lecture 9	Section 1.4 pumping lemma help	Saturday is Yom Kippur
10	9/25	first midterm during lecture
	9/27	Proving non-regularity via closure properties, closure under homomorphism, DFA minimization	Lecture 10	Suffix languages and Minimization concrete example of suffix lgs closure properties
11	10/2	Context-free grammars, parse trees, ambiguity	Lecture 11	Section 2.1 The Groke grammar example Green Eggs and Ham
12	10/4	Chomsky-normal form pushdown automata	Lecture 12	Section 2.2 Sheila Greibach (picture) Noam Chomsky 1965 computer
13	10/9	More examples of PDA's converting CFG's to PDA's	Lecture 13	Section 2.2
14	10/11	Quiz 2 Converting PDAs to CFG's	Lecture 14	Section 2.2	Friday is drop date Ramadan ends Saturday
15	10/16	The pumping lemma for CFLs, closure properties	Lecture 15	Section 2.3 closure properties
16	10/18	Turing machines	Lecture 16	Section 3.1 Alan Turing Alonzo Church
17	10/23	More TM examples Multi-tape TMs	Lecture 17	Section 3.2
18	10/25	Encoding problems, decidability	Lecture 18	Section 3.3, Section 4.1
	10/30	Second midterm 7-9pm 1404 Siebel lecture = review			Wednesday is Halloween
19	11/1	TM as interpreter, simulating a real computer, more decidable problems	Lecture 19	Section 4.1
20	11/6	The Halting Problem and Undecidability	Lecture 20	Section 4.2	Election Day
21	11/8	Reductions for undecidability	Lecture 21	Section 5.1 reduction help	Friday is Diwali
22	11/13	Undecidable problems on linear bounded automata and CFLs	Lecture 22	Section 5.1
23	11/15	Quiz 3 More examples of reductions, Rice's theorem	Lecture 23	Section 5.1
	11/20	Fighting through crowded airports			Thanksgiving break
	11/22	Eating too much turkey			Thanksgiving break
24	11/27	Non-deterministic TM's	Lecture 24	Section 3.2
25	11/29	Post's Correspondence problem Undecidability of CFG ambiguity tiling problems	Lecture 25	Section 5.2 periodic tilings aperiodic tilings aperiodic wang tiles Penrose tilings undecidability of tilings
26	12/4	Algorithms for automata CYK parsing algorithm	Lecture 26	DFA minimization algorithm	Hanukkah starts Wednesday
27	12/6	Recap Course evals	Lecture 27	Review Handout
	12/11	exam week: no class
	12/13	Final Exam, 7-10pm, 1320 DCL