CSE 431: Introduction to the Theory of Computation

Winter, 2025

Paul Beame

Lectures MWF 10:30-11:20.
Office hours: MWF 11:20-11:50 and W 3:00-3:50
Office: CSE 668, Phone 206-543-5114.

Discussion board:
We will use the Ed discussion board. This is the right place to ask any questions about the course. We will happily answer questions from lecture or about general concepts. We also will answer clarifications about homework (e.g. correcting typos). You are encouraged to answer each other’s questions on the message board as well. If you have a question that might reveal your approach to a homework problem, you must ask the question privately. For accommodations and other private questions, you can ask privately on Ed or email the instructor directly. Only you and the course staff can see a private question on Ed.
Homework submission is via Gradescope.
Canvas
We will only use Canvas for Panopto lecture capture and for the release of homework solutions.

Textbook:
Michael Sipser, Introduction to the Theory of Computation.

Any of the first, international, second or third editions will work. Earlier editions are less than one quarter the cost of the third edition online. Although the numbering of almost everything in the first and international editions is different from the others, the content is mostly unchanged except for some corrections and new and solved problems in each subsequent edition. The third edition has an extra section 2.4 on deterministic context-free languages that we won't cover anyway. See errata links from Sipser's book page for lists of errors and corrections.

Review Reading:

  • Review Sipser text: Chapter 0
  • Review Sipser text: Chapter 1
  • If you did not take CSE 311 and have not seen finite state machines, you should skim Chapter 1 of Sipser's text to get a sense of the material covered there.

Lectures

Date Topic Materials Reading (Sipser)
Mon, Jan 6 Introduction.
Prehistory of computing		 Infinity & Computation Chapter 3 (first part 3.3)
Wed, Jan 8 Turing Machines Turing & Post Handout
Fri, Jan 10 Turing Machines definition & operation Section 3.1
Mon, Jan 13 Turing Machine diagrams;k-tapes ≡ 1-tape Section 3.1-3.2
Wed, Jan 15 Finish k-tapes ≡ 1-tape
NTMs, NTM≡ TM		 Section 3.2
Fri, Jan 17
Mon, Jan 20 HOLIDAY
Wed, Jan 22
Fri, Jan 24
Mon, Jan 27
Wed, Jan 29
Fri, Jan 31
Mon, Feb 3
Wed, Feb 5
Fri, Feb 7
Mon, Feb 10
Wed, Feb 12
Fri, Feb 14 Midterm
Mon, Feb 17 HOLIDAY
Wed, Feb 19
Fri, Feb 21
Mon, Feb 24
Wed, Feb 26
Fri, Feb 28
Mon, Mar 3
Wed, Mar 5
Fri, Mar 7
Mon, Mar 10
Wed, Mar 12
Fri, Mar 14

TA Office hours Room
Matthew Shang Mondays 3:30-4:20 Gates 153
Wednesdays 1:30-2:20 Gates 153
Michael Whitmeyer Tuesdays 2:30-3:20 Allen 220
Thursdays 9:30-10:20 Gates 153

Homework:

Before starting on homework, please review our homework policy Submission is online in Gradescope. Extra credit problem solutions need to be uploaded separately from the regular problems.

Exams:

  • Midterm exam:
    Friday, February 14 in class.
  • Final exam:
    The final exam will be in our regular classroom at the time listed in the official exam schedule which is 8:30-10:20 am, Monday March 17.

Grading Scheme:
The grading scheme below is subject to change depending on our ability to have in-person exams this term.

Homework 45-55% + Extra Credit
Midterm 15-20%
Final Exam 30-35%
Further reading
Accommodations
Please refer to university policies regarding disability accommodations or religious accommodations.
Catalog Description
Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 312.