Date: Tue, 05 Nov 1996 20:52:29 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Fri, 25 Oct 1996 14:39:29 GMT Content-length: 3556
The previous tentative schedule is still available.
lecture | topic |
---|---|
21 Oct | proving languages non-Context-free |
23 Oct | more non-Context-freeness, decision problems for CFLs |
25 Oct | Post Machines, Recursive and Recursively Enumerable languages |
28 Oct | Church's thesis, the Chomsky hierarchy, review |
30 Oct | mid-term examination (room 168 Noland, your choice of 12:20-2:20 or 1:10-3:10) |
1 Nov | Turing Machines |
4 Nov | more TMs |
6 Nov | equivalence of PMs and TMs |
8 Nov | more Recursive and Recursively Enumerable languages |
11 Nov | Universal Grammars and Context Sensitive Grammars |
13 Nov | equivalence of deterministic and nondeterministic TMs |
15 Nov | proving languages non-Recusively-Enumerable |
18 Nov | more non-RE languages |
20 Nov | decision problems for TMs |
22 Nov | more TM decision problems, Rice's theorem |
25 Nov | restricted TMs |
27 Nov | more Chomsky hierarchy |
2 Dec | Alternation in automata |
4 Dec | more Alternation |
6 Dec | P and NP |
9 Dec | more P and NP, NP-completeness |
11 Dec | Lambda Calculus |
13 Dec | review |
16 Dec | final examination, 2:45pm, room TBA |
< cs520 home page> < UW-Madison Computer Sciences home page> < UW-Madison home page>