4391 CS 262-7997 E-mail famous baroque composer at cs dot wisc edu Office hours MWF 11-12

1351 CS E-mail soundararaj2 at wisc dot edu Office hours TR 11:30-12:30

- Homework 1 Due 9/22
- Homework 2 Due 10/13
- Homework 3 Due 11/13
- Homework 4 Due 11/29

- Hopcroft & Ullman on Myhill-Nerode
- Hopcroft & Ullman on machines with output
- Kernighan & Pike on grep
- Rogers on the notion of an algorithm
- Godel's "software" for sequence coding
- Hopcroft & Ullman on partial functions
- Hopcroft & Ullman on Rice's theorem
- Machtey & Young on the recursion theorem
- Lewis and Papadimitriou on NP-completeness