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 Fall 1996 Lecture Schedule

Fall 1996 Lecture Schedule

This schedule is tentative, but the date of the mid-term examination is now set in stone. The pace after the midterm may be slower than outlined here. (Some of the topics scheduled near the end of the semester have been chosen so they can be dropped without adverse affects.)

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


Fall 1996 Lecture Schedule / 21 October 1996 / Brian Cole

< cs520 home page> < UW-Madison Computer Sciences home page> < UW-Madison home page>