CS 360: Introduction to Theory of Computing (Spring 2021)

Jun 5, 2021

Welcome to the Spring 2021 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

This will be an online course, with two written lecture notes posted each week. There will also be occasional video recordings posted to the YouTube channel for the class. All students are also required to join Piazza, where we can all participate in discussions.

In addition, there will be 3 office hours per week, one by the professor and one by each of the two TAs.

Assessments

The tentative grade breakdown is as follows:

  • 5 assignments, worth a total of 40%
  • Around 10 Mobius quizzes, posted roughly once a week and worth a total of 5%
  • A live-interview midterm (will likely be a 15-20 minute meeting with the professor), worth 15%
  • A final exam. We will likely use some proctoring software for this. It will be worth 40%.

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 youtube channel, where occasional videos will be posted.
  • 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.

Office hours

There will not be office hours the first week (the week of May 10). Afterwards, the office hours will be as follows (this is subject to change).

  • Shalev Ben-David (instructor): Thursdays 7:00pm - 8:00pm (Eastern time)
  • Daniel Gabric (TA): Fridays 12:00pm - 1:00pm (Eastern time)
  • Jack Spalding-Jamieson (TA): Tuesdays 3:00pm - 4:00pm (Eastern time)

Schedule + Notes

The following is tentative and subject to change.

Shalev Ben-David
Shalev Ben-David
Associate Professor of Computer Science