Tuesday & Thursday, 1:30–2:45 p.m.
Tuesday  Thursday  

1 
Models of computation

Jan. 21 
Jan. 23 
2 
Finite automata

Jan. 28 
Jan. 30 
3 
Nondeterminism

Feb. 4 
Feb. 6 
4 
Regular expressions

Feb. 11 
Feb. 13 
5 
Regular and nonregular languages

Feb. 18 
Feb. 20 
6 
Contextfree grammars

Feb. 25 
Feb. 27 
7 
CFGs and parsing

Mar. 3 
Mar. 5 
8 
Mar. 10Spring Break 
Mar. 12Spring Break 

9 
Mar. 17Spring Break 
Mar. 19Spring Break 

10 
Pushdown automata

Mar. 24Pushdown automata 
Mar. 26The power of PDAs 
11 
Contextfree and noncontextfree languages

Mar. 31The limits of contextfree languages 
Apr. 2Closure properties for CFLs 
12 
Exam 2Turing machines

Apr. 7 
Apr. 9Turing machines 
13 
Turing machines

Apr. 14Turing machines, continued 
Apr. 16Turing machines and computation 
14 
Undecidability

Apr. 21At the foot of the mountains of undecidability 
Apr. 23Undecidability 
15 
The limits of computation

Apr. 28The limits of computation 
Apr. 30The big picture 
16 
May. 5 
May. 7Study Period 

17 
May 12Study Period 
May 14Exam Period 

18 
Resources
Perspectives
Software
Presentday computers are built of transistors and wires, but they could just as well be built, according to the same principles, from valves and water pipes, or from sticks and string. The principles are the essence of what makes a computer compute. One of the most remarkable things about computers is that their essential nature transcends technology.W. Daniel Hillis, The Pattern on the Stone