CS 360: Introduction to Theory of Computing — Winter 2020

Course Outline

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

Time and Place

Lectures:

TuTh 10:00–11:20, MC 4058

Resources

Textbook

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.

Other

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!

Personnel

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 M: 10:00–11:00 & W: 3:00–4:00, in DC 2102 (starts Jan 13.)

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.

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


Menu:ShowHide