CS 360: Introduction to Theory of Computing — Winter 2020

Course Outline

This page under construction. Please check back later for updates.

Time and Place


TuTh 10:00–11:20, MC 4058



J. Watrous, Introduction to the Theory of Computing: Lecture notes for CS 360, version of June 27, 2017. (A Creative Commons License applies; see the cover page.)

The text sometimes refers to "this lecture", or "the homework", or the like. Do not take these as a guide to the present course; we will have our own timing and our own assignments.

Other versions of the above work will be similar, but not the same. Also, many other texts contain essentially the same material, albeit often with different notation and sometimes nomenclature. On assignments, exams, etc., make sure to use notation compatible with the text (or lectures, if they differ).

Electronic fora

Piazza: for questions and discussion from students, and announcements, discussion and answers from instructors and TAs.
Note that Piazza posts are completely public, and may be read by anyone anywhere.
Learn: for sensitive and/or confidential information.
Assignments and solutions. Record of marks.
Reading guides for late-March material. (See the Content tab.)


Additional material (e.g., copies of overheads, etc.) will be posted here from time to time. (Note that these are copyrighted. You have permission to access them for your own use, but not to distribute them further.)

The following materials were prepared by Jeff Shallit. Thanks, Jeff!

Study questions: midterm.


Role Name Email Contact
Instructor Jonathan Buss jfbuss DC 3353, x34428.

Hours: Tue/Thur, 2:00–3:00.
Or by appointment, or just drop by.

TA Adam Jaffe ajaffe Jan/Feb: Mondays 11:00–12:00, DC 2102.
Mar: Wednesdays 3:00–4:00, DC 2102

For questions regarding course material and/or logistics, do any/all of

To request a re-evaluation of marking, or to discuss your progress in the course, contact the instructor.

For administrative issues, including illness forms and accommodation for religious holidays, contact the instructor.

For other issues, or if nothing applies, please contact the instructor.

Course Work

Grading summary:

Academic Integrity and Students with Disabilities

This courses adheres to the UW policies on Academic Integrity and Students with Disabilities.

Course Topics

(This outline will be annotated with times and readings, as the course progresses.)

All readings are from Watrous, unless otherwise noted.
Jan 7: Course overview. Reprise of sets and countability.
Readings: Watrous, through page 9.
Jan 9: Finish countability. Alphabets, strings, and languages.
Reading: Through section 2.1 (pg. 16).
Jan 14: Deterministic finite automata (DFAs). Definition; computations by DFAs; languages of DFAs.
Reading: 2.2, pp. 16–21.
Jan 16: Reasoning about DFAs: the extended transition function. Intro to NFAs.
Reading: 2.2; 3.1.
Jan 21: Equivalence of NFAs and DFAs. Intro to regular expressions and their languages.
Reading: 3.2. Start on 4.1.
Jan 23: Regular expressions and languages; closure properties.
Kleene's Theorem—regular expressions, DFAs and NFAs are all equivalent.
Reading: Chapter 4.
Jan 28: Non-regular languages.
Reading: Chapter 5.
Jan 30: Non-regular languages, contd. Examples of regular and non-regular languages.
Reading: Chapter 5.
Feb 4: Context-free grammars and languages.
Reading: Chapter 7.
Feb 6: Proofs about context-free grammars. Ambiguity. Normal forms.
Reading: Chapters 7, 8.
Feb 11: Constructions of CFGs. Closure properties of the set of CFLs.
Reading: Chapter 9.
Feb 13: Non-context free languages (another pumping lemma).
Reading: Chapter 10.
Feb 25: Pushdown automata
Reading: Chapter 11.
Feb 27: PDAs and CFGs. Introduction to Turing machines and general computation.
Reading: §§ 11.3– 12.2.
Mar 3: No lecture --- Midterm Exam
Reading: Chapters 1–10.
Mar 5: Turing machine computations; variations on Turing machines.
Reading: Chapters 12, 13.
(Conversion to on-line).
Module: Decision problems.
Module: Undecidability of the Halting Problem.
Module: Further undecidable problems.
Module: Overview of time complexity and NP-completeness.

Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

Valid HTML 4.01!Valid CSS! Last modified: Monday, 6-Jan-2020