CS 360: Introduction to Theory of Computing

Welcome to the Spring 2022 offering of CS 360. In this course, we will study the theory of computation. We will answer questions like: how should computation be defined mathematically? How do different computational models compare to each other? What are the limits of computation — are there well-defined problems that cannot be solved on a computer?

Format

(Details are subject to change.)

This will be an in-person course, with lectures twice a week:

• Mondays and Wednesdays 10:00-11:20am
• Room: MC 4060.

The lectures will not be recorded. Lecture notes will be posted here on the course website.

All students are also required to join Piazza, where we can all participate in discussions. Important announcements will be made through Piazza.

In addition, there will be 3 office hours per week, one by the professor and one by each of the two TAs. Times and locations will be posted on Piazza. There will not be office hours in the first week.

Assessments

The tentative grade breakdown is as follows:

• 5 assignments, worth a total of 25%
• Around 10 Mobius quizzes (online), posted roughly once a week and worth a total of 5%
• A midterm (format to be determined), worth 20%
• A final exam worth 50%.

Resources

The course outline is here.

The following websites will be associated with the course:

• The course webpage you are currently looking at.
• The Piazza page, found here.
  • All students need to join Piazza, as some announcements will be made exclusively on Piazza.
• The UW Learn page, found here.
  • Students need access to UW Learn to complete the Mobius quizzes.
• The Crowdmark site. (Registered students will receive an invitation.)
  • The assignments will be submitted and graded through Crowdmark.

Lecture notes will be posted below. Additional optional resources include the textbook Introduction to the Theory of Computation by Sipser, the textbook Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman, and John Watrous’s course notes.

Schedule

The following is tentative and subject to change. Assignments are currently planned to be due every other week, on Fridays before the midterm and Tuesdays after the midterm. Quizzes (which are online, can be taken any time, and are short) are currently planned to be due every week, and can be completed any time before Monday’s class.

• Week of May 2: Lecture 1 on Mon. May 2, Lecture 2 on Wed. May 4
  • Monday May 2 is the first day of classes.
• Week of May 9: Lecture 3 on Mon. May 9, Lecture 4 on Wed. May 11
  • Friday May 13 is the last day to officially enroll in the class.
• Week of May 16: Lecture 5 on Mon. May 16, Lecture 6 on Wed. May 18
  • Friday May 20 is the last day to drop the class.
  • Quiz 1 due Monday May 16 before class.
  • Assignment 1 due Friday May 20.
• Week of May 23: Lecture 7 on Wed. May 25
  • Monday May 23 is Victoria day (no class).
  • Quiz 2 due Wednesday May 25 before class.
• Week of May 30: Lecture 8 on Mon. May 30, Lecture 9 on Wed. June 1
  • Quiz 3 due Monday May 30 before class.
  • Assignment 2 due Friday June 3.
• Week of June 6: Lecture 10 on Mon. June 6, Lecture 11 on Wed. June 8
  • Quiz 4 due Monday June 6 before class.
• Week of June 13: Lecture 12 on Wed. June 15
  • Midterm is Monday June 13 during class time.
  • Quiz 5 due Monday June 13 before class.
• Week of June 20: Lec. 13 on Mon. June 20, Lec. 14 on Wed. June 22
  • Quiz 6 due Monday June 19 before class.
• Week of June 27: Lec. 15 on Mon. June 27, Lec. 16 on Wed. June 29
  • Quiz 7 due Monday June 26 before class.
  • Assignment 3 due Tuesday June 28.
• Week of July 4: Lecture 17 on Mon. July 4, Lecture 18 on Wed. July 6
  • Quiz 8 due Monday July 4 before class.
• Week of July 11: Lecture 19 on Mon. July 11, Lecture 20 on Wed. July 13
  • Quiz 9 due Monday July 11 before class.
  • Assignment 4 due Tuesday July 12.
• Week of July 18: Lecture 21 on Mon. July 18, Lecture 22 on Wed. July 20
  • Quiz 10 due Monday July 18 before class.
• Week of July 25: Lecture 23 on Mon. July 25
  • Classes end Tuesday July 26 (no class Wednesday July 27).
  • Quiz 11 due Monday July 25 before class (replaces lowest quiz).
  • Assignment 5 due Tuesday July 26.
• Final Exam to be scheduled between July 29 and August 13.