School of Computer Science

University of Waterloo

CS 365 Models of Computation

Winter 2010

General Information

Instructor John Watrous Email: my last name at cs.uwaterloo.ca Office: DC 2108 Office hours: TW 10:00–11:00

Teaching Assistant Ansis Rosmanis Email: ansis.rosmanis at gmail.com Office: DC 2115 Office hours: W 1:00–2:00

Lectures: 1:00–2:20 TTh in DWE 1515.

Text and Lecture Schedule

The text book for the course is:

M. Sipser. Introduction to the Theory of Computation (Second Edition). Thomson Course Technology, 2006.

Lecture Schedule (including associated readings).

Announcements

• The final exam for CS 365 will take place Tuesday April 20 from 12:30 – 3:00 PM in PAC 6.
• A few practice problems for the final have been posted below.
• I will have "all day" office hours on Monday, April 19, from 10am to 4pm. Feel free to drop by if you have last-minute questions.

Problem Sets

• Assignment 1 (pdf)  (Solutions (pdf))
• Assignment 2 (pdf)  (Solutions (pdf))
• Assignment 3 (pdf)  (Solutions (pdf))
• Assignment 4 (pdf)  (Solutions (pdf))
• Assignment 5 (pdf)  (Solutions (pdf))

Additional Materials

• Information on Course Policies.
• Some links to auxiliary materials.
• A few practice problems on undecidability and reductions [pdf]
• Midterm 1 solutions [pdf]
• Midterm 2 solutions [pdf]
• Practice problems for the final [pdf]