School of Computer Science

University of Waterloo

CS 360 Introduction to the Theory of Computing

Spring 2008

General Information

Lectures

12:30–1:20 MWF in MC 4063.

Instructor

John Watrous (IQC and School of Computer Science)
Email: my last name at cs.uwaterloo.ca.
Office: DC 2108.

Teaching Assistants

Gus Gutoski Email: gmgutoski (at) uwaterloo (dot) ca Office: DC 2116

Olga Miltchman Email: omiltchm (at) uwaterloo (dot) ca Office: DC 3543

Text and Lecture Schedule

The text book for the course is:

J. Hopcroft, R. Motwani and J. Ullman. Automata Theory, Languages, and Computation (Third Edition). Addison Wesley, 2007.

Lecture Schedule (including associated readings).

Homework Assignments

• Assignment 1 (pdf).  Solutions (pdf) prepared by Olga Miltchman.
• Assignment 2 (pdf).  Solutions (pdf) prepared by Olga Miltchman.
• Assignment 3 (pdf).  Solutions (pdf) prepared by Gus Gutoski.
• Assignment 4 (pdf).  Solutions (pdf) prepared by Gus Gutoski.

Additional Materials

• Information on Course policies
• Handout on Logic and set theory (pdf)
• Handout on Converting NFAs to DFAs (pdf)
• Handout on A non-Turing-recognizable language (pdf)
• Handout on Examples of undecidability proofs (pdf)
• Quiz 1 (pdf) and its solutions (pdf) from Spring 2007.
• Quiz 2 (pdf) and its solutions (pdf) from Spring 2007.
• Quiz 3 (pdf) and its solutions (pdf) from Spring 2007.
• Quiz 1 solutions (pdf).
• Quiz 2 solutions (pdf).
• Quiz 3 solutions (pdf).
• Final exam questions (pdf) from 2007.