CSE 431: Introduction to the Theory of Computation (Spring 2014)

[course overview | lectures | assignments | related material]

course overview

Instructor: James R. Lee, CSE 640
Time: Tuesdays and Thursdays in THO 211, 10:30-11:50am.
Office hours:  Tues 2:30-4pm, CSE 640

Teaching assistant: Yi-Shu Wei
Office hours: Mon 1:30-2:30pm, CSE 218

Course evaluation: Scribe one lecture, homeworks, and a final exam.

About this course:
This course is about computation, proofs, logic, and the nature of truth. We will study what problems can (and cannot) be solved by a computer, as well as how much of a given resource is needed to solve them (time, memory, randomness). In doing so, we'll touch upon some of the most important mathematical (and sometimes philosophical) discoveries of the 20 and 21st centuries, as well as confront (time and again) the limits of our present understanding.

schedule of classes

"Siper" and "Papadimitriou" refer to the the corresponding books. Reading marked "[Supp]" is supplementary (extra reading for your pleasure and edification); it is not strictly necessary for the course.

Lecture Date Topic Reading Scribe
Lecture 1 Tues, Apr 1 Cantor, set theory, and diagonalization Logicomix, Ch. 1-2 notes
Lecture 2 Thurs, Apr 3 Turing machines Logicomix, Ch. 3; Sipser, 3.1-3.2 notes
Lecture 3 Tues, Apr 8 Algorithms on Turing machines Sipser, 3.2-3.3 notes
Lecture 4 Thurs, Apr 11 The Church-Turing Thesis, decidability of simpler models Sipser, Ch. 4 notes
Lecture 5 Tues, Apr 15 The Halting Problem, undecidable languages Sipser, Ch. 4 notes,
Lecture 6 Thurs, Apr 17 Reductions, the Recursion Theorem Sipser, Ch. 5, 6.1 n1, n2
Lecture 7 Tues, Apr 22 Logic, proofs, and incompleteness Sipser, Ch. 5, 6.2; [Supp] Papadimitriou, Ch. 5; [Supp] Logicomix, Ch. 4-6 notes
Lecture 8 Thurs, Apr 24 The first incompleteness theorem Sipser 6.2; [Supp] Papadimitriou, Ch. 6; [Supp] Logicomix, Ch. 4-6 notes
Lecture 9 Tues, Apr 29 Time complexity Sipser 7.1 notes
Lecture 10 Thurs, May 1 P and NP Sipser 7.2-7.3 notes
Lecture 11 Tues, May 6 NP-completeness Sipser 7.3-7.4 notes
Lecture 12 Thurs, May 8 The Cook-Levin Theorem Sipser 7.4-7.5 notes
Lecture 13 Tues, May 13 NP-completeness reductions I Sipser 7.5 notes
Lecture 14 Thurs, May 15 NP-completeness reductions II Sipser 7.5 notes
Lecture 15 Tues, May 20 Space complexity and Savitch's Theorem Sipser 8.1-8.2 n1, n2
Lecture 16 Thurs, May 22 P vs. PSPACE vs. EXPTIME, and Hierarchy Theorems Sipser 8.2, 9.1 notes
Lecture 17 Thurs, May 27 Space and Time Hierarchy Theorems Sipser 9.1 notes
Lecture 18 Thurs, May 29 Logspace Sipser 8.4 notes
Lecture 19 Thurs, Jun 3 Connectivity with random bits
Lecture 20 Thurs, Jun 5 SL=L

related material

Primary book: Introduction to the Theory of Computation by Michael Sipser.

Secondary material [no need to purchase]: Logicomix and Computational Complexity by Christos Papadimitriou.

For writing scribe notes: If you are using LaTeX, please use this template. If you are using Microsoft Word, see these notes on Microsoft Equation Editor. Briefly, there is a very rich syntax for quickly typing mathematical text.

assignments

These can be turned in electronically (scan or typeset--no fuzzy smartphone photos) by sending them to cse431-staff@cs by class time on the due date.