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).
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
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
The following materials were prepared by Jeff Shallit. Thanks,
Study questions: midterm.
DC 3353, x34428.
Hours: Tue/Thur, 2:00–3:00.
Or by appointment, or just drop by.
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
If your question has general interest,
post to the course Piazza page.
See the instructor, at the above times or by arrangement.
Dropping by can work, too!
See the TA, at times above, or by prior arrangement.
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.
Due dates and times as announced.
See the assignments page for
Tuesday, March 3, during class period
Seating assignments to be posted to Odyssey; both MC 4058 and
MC 4041 will be used.
Final exam: 40%. Time and location to be announced.
Academic Integrity and Students with Disabilities
This courses adheres to the UW policies on
Academic Integrity and Students with Disabilities.
(This outline will be annotated with times and readings, as the course
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
- Reading: Chapter 4.
- Jan 28: Non-regular languages.
- Reading: Chapter 5.
- Jan 30: Non-regular languages, contd. Examples of regular and
- 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
- 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.