CS 360: Introduction to Theory of Computing (Spring 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.

  • Week of May 10: Lecture 1, Lecture 2.
  • Week of May 17: Lecture 3, Lecture 4.
  • Week of May 24: Lecture 5, Lecture 6. Quiz 1 due Tuesday.
    • Holiday on Monday.
    • Assignment 1 due Friday May 28.
  • Week of May 31: Lecture 7, Lecture 8. Quiz 2 due Monday.
  • Week of June 7: Lecture 9, Lecture 10. Quiz 3 due Monday.
    • Assignment 2 due Friday June 11.
  • Week of June 14: Lecture 11, Lecture 12. Quiz 4 due Monday.
  • Week of June 21: Lecture 13, Lecture 14. Quiz 5 due Monday.
    • Midterm interviews will be scheduled this week.
  • Week of June 28: Lecture 15. Quiz 6 due Monday.
    • Holiday Thursday and Friday.
  • Week of July 5: Lecture 16, Lecture 17. Quiz 7 due Monday.
    • Assignment 3 due Friday July 9.
  • Week of July 12: Lecture 18, Lecture 19. Quiz 8 due Monday.
  • Week of July 19: Lecture 20, Lecture 21. Quiz 9 due Monday.
    • Assignment 4 due Friday July 23.
  • Week of July 26: Lecture 22, Lecture 23. Quiz 10 due Monday.
  • Week of August 2: Lecture 24.
    • Holiday on Monday, no class Friday (end of classes).
    • Assignment 5 due Thursday August 5.
  • August 7-16: Final exam will be scheduled in this range.
Shalev Ben-David
Shalev Ben-David
Assistant Professor of Computer Science