Winter 2015
Time: Tuesdays and Thursdays, 10:00-11:20
Location: MC 4064
Eric Blais
Office hours: Tuesdays, 2:00-3:00 in DC 3119
Teaching assistant
Chuan Guo
Office hours: Wednesdays, 2:30-3:30 in DC 3540
Piazza page
All announcements for the class will be posted on the Piazza page. The page will also be the central place for class discussions and for any questions about the lectures and assignments.
Sign up for the page here.

Course Description

This course provides accelerated coverage of the material from CS 360, including finite automata and regular languages, context free grammars and pushdown automata, Turing machines, and undecidability. In addition, topics from complexity theory are covered, including time and space complexity, hierarchy theorems, and complete problems for various classes.


The primary textbook for the class is:

Previous editions of the textbook are also acceptable. Another useful, though not required, reference for the second half of this course is:


The assignments will be listed here as they become available. They will be made available every Thursday and are due in class the following Thursday.

Problem set 1.
Available on: Jan 8. Due on: Jan 15.
Problem set 2.
Available on: Jan 15. Due on: Jan 22.
Problem set 3.
Available on: Jan 22. Due on: Jan 29.
Problem set 4.
Available on: Jan 29. Due on: Feb 5.
Problem set 5.
Available on: Feb 5. Due on: Feb 12.
Problem set 6.
Available on: Feb 26. Due on: Mar 5.
Problem set 7.
Available on: Mar 5. Due on: Mar 12.
Problem set 8.
Available on: Mar 12. Due on: Mar 19.
Problem set 9.
Available on: Mar 19. Due on: Mar 26.
Problem set 10.
Available on: Mar 26. Due on: Apr 2.

Assignment policy

The assignments are due in class on their respective due dates. No late assignments will be accepted.


Collaboration with classmates when completing the assignments is encouraged in this class, but must follow these guidelines.

External sources

Do not search for the solutions to the assignment problems in external sources. As described above: the point of the assignments is to learn the material, and you will be penalizing yourself if you try to shortcut this process.

However, you are allowed to look at sources outside of the official course material in order to understand the material better. In many situations, reading different presentations of the same material can be very helpful in understanding it better. Occasionally, you may find the solution to an assignment problem while reading one of these external sources. When that happens, just be honest: give a proper citation for the source of the solution in your acknowledgments and write the solution on your own (using your own words and, obviously, without the found solution in front of you). You will not be penalized for a solution found in another source that is cited properly and written by yourself, but failure to cite the source properly is plagiarism.

Effective communication

In these assignments, it is not enough to find the solution to a problem: you must also be able to clearly and effectively communicate it. You should strive to find a concise, clear, and logically sound way to present all your solutions. You should also make sure that the assignment is easy to read. If your handwriting is bad, you should consider typesetting the solutions. And if you have some difficulty writing in English, you should contact the University's Writing Centre; they have many programs that may help you.

Grading scheme

The final grades for the class will be determined by the scores on the assignments, the midterm, and the final exam, according to the following percentages:


Lecture 1 (Jan. 6)
Course overview. Languages.
Lecture 2 (Jan. 8)
Introduction to finite automata. Regular languages, DFAs, and NFAs.
Lecture 3 (Jan. 13)
Regular expressions. Equivalence with regular languages.
Lecture 4 (Jan. 15)
Non-regular languages. Pumping lemma.
Lecture 5 (Jan. 20)
Context-free grammars and regular grammars. First language hierarchy.
Lecture 6 (Jan. 22)
Pushdown automata (PDA). Equivalence with CFGs.
Lecture 7 (Jan. 27)
Parse trees. Chomsky normal form.
Lecture 8 (Jan. 29)
Non-context-free languages. Pumping lemma for CFLs.
Lecture 9 (Feb. 3)
Turing machines. Decidability. Variants and initial results.
Lecture 10 (Feb. 5)
Church-Turing thesis. Nondeterministic Turing machines.
Lecture 11 (Feb. 10)
Uncountability and undecidability.
Lecture 12 (Feb. 12)
The Halting problem. Reductions. Rice's Theorem.
Lecture 13 (Feb. 24)
Lecture 14 (Feb. 26)
Time complexity. Time hierarchy theorem.
Lecture 15 (Mar. 3)
P and NP.
Lecture 16 (Mar. 5)
NP-completeness. DNFs and CNFs.
Lecture 17 (Mar. 10)
Cook-Levin Theorem.
Lecture 18 (Mar. 12)
Boolean circuits. P/poly. Shannon's lower bound.
Lecture 19 (Mar. 17)
Uniform circuit families. Bounded-depth circuits.
Lecture 20 (Mar. 19)
Space complexity. L and PSPACE.
Lecture 21 (Mar. 24)
More reductions. NP-completness, P-completeness, and NL-completeness.
Lecture 22 (Mar. 26)
PATH is NL-complete. Immerman-Szelepcseny Theorem.
Lecture 23 (Mar. 31)
Randomized and interactive proof verification. AM, MA, IP.
Lecture 24 (Apr. 2)
Sampling of topics beyond this course.

Additional Information

Academic Integrity

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. See http://uwaterloo.ca/academic-integrity for more information.


A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.


A student is expected to know what constitutes academic integrity (check https://uwaterloo.ca/academic-integrity/) to avoid committing an academic offence, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration, should seek guidance from the course instructor, TA, academic advisor, or the Undergraduate Associate Dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, see the Guidelines for the Assessment of Penalties.


A decision made or penalty imposed under Policy 70 (Student Petitions and Grievances) (other than a petition) or Policy 71 (Student Discipline) may be appealed if there are grounds. A student who believes he/she has grounds for an appeal should refer to Policy 72 (Student Appeals).

Note for Students with Disabilities

AccessAbility Services (formerly the Office for Persons with Disabilities), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities, without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.