This course covers foundational results in theoretical computer science, with a focus on how we model computation and how we use these models to explore key questions about what can and cannot be solved (efficiently) with computing devices. Many of the concepts in this course will come up often in the life of a computer scientist (e.g., NP-completeness, decidability, grammars, etc).
During the final lectures of the course, we will tackle some cutting edge topics from the field (time permitting), to provide guidance to those who might be interested in pursuing research in this topic in graduate school.
This course is open to PhD and Masters students. Because our department doesn't regularly offer a theory course at the undergraduate level, I'm also happy to allow advanced undergraduates to enroll with my permission.
The textbook for this course is Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, 2012. Most of the topics covered in this course will be drawn from this text.
Grades in the course will be based on five problem sets and two exams.
In determining your final grade, I will add up the total number of points you earned and assign your grade based on this sum. (The mapping from point totals to letter grades is something I develop as the semester progresses and I get a better sense of the relative difficulty of the problems I assigned. If you are unsure how you are doing in the class, please ask me.)
The point values of the exams and problem sets are calibrated so they they contribute approximately the following percentage toward your final point total:
Problem sets | 50% |
Midterm | 25% |
Final | 25% |
A few tips for doing well in this course without excessive amounts of stress:
I hold regular office hours in my office at 334 Saint Mary's Hall from 12:30 to 2:00 on Thursdays.
Problem sets will be posted for download on the schedule below on the day they are assigned. Detailed sample solutions and notes will be handed back to students along with the graded problem sets. I try to grade and return problem sets within one week.
The following rules describe my expectations and grading policies for problem sets:
There will be two exams in the course: a midterm and a final. The midterm covers automata and computability theory and the final covers complexity theory (i.e., it is not cumulative).
I take academic integrity seriously. To repeat the problem set instructions from above: You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources or talk to other students.
You may not bring any outside material into exams.
You may not reference any problem sets, exams, or solutions from prior teachings of this course.
When in doubt, ask me what is allowed.
Below is the current schedule for the course (some changes may occur during the semester). Problem sets will be posted for download on the schedule as they become available. The readings column lists the chapters from the Sipser textbook that cover the corresponding lecture's material.
Class Number | Date | Description | Readings |
Part 1: Automata Theory | |||
1 | 1/12 | Intro; finite automata
| 1.1 |
2 | 1/17 | Non-determinism; regular languages; | 1.2, 1.3 |
3 | 1/19 | Pumping lemma for regular languages; context-free grammars; Chomsky normal form | 1.4, 2.1 |
4 | 1/24 | Pushdown automata; pumping lemma for context-free languages | 2.2, 2.3 |
5 | 1/26 | Context-free languages | 3.1 |
Part 2: Computability Theory | |||
6 | 1/31 | Turing machines
| 4.1 |
7 | 2/2 | Some decidable and recognizable languages. Proof of undecidable and unrecognizable languages. | 4.1, 4.2 |
8 | 2/7 | Reducibility | 5.1, 5.3, 6.3 |
9 | 2/9 | Turing machines (cont) | 5.1, 5.2 |
10 | 2/14 | Reductions | 6.1 |
11 | 2/16 | Reductions (cont), LBAs, Recursion theorem | |
12 | 2/21 | Lecture overflow; midterm review
| |
13 | 2/23 | Midterm | 7.1 |
Part 3: Complexity Theory | |||
14 | 2/28 | Time complexity; the classes P and NP
| 7.2, 7.3 |
15 | 3/2 | NP-completeness; the Cook-Levin theorem | 7.4 |
3/7 | No Class: Spring Break | ||
3/9 | No Class: Spring Break | ||
Snowday distruption... | |||
16 | 3/21 | Cook-Levin theorem; more NP-complete problems | 7.4, 7.5 |
17 | 3/23 | Space Complexity; SPACE and NSPACE complexity classes | 8.0 |
18 | 3/28 | Savitch's Theorem; PSPACE and
PSPACE-Completeness
| 8.1, 8.2, 8.3 |
19 | 3/30 | Games and Generalized Geography; | 8.3 |
20 | 4/4 | L and NL, NL-Completeness, and NL = coNL | 8.4, 8.5, 8.6 |
21 | 4/6 | Hierarchy Theorems | 9.0, 9.1 |
22 | 4/11 | Relativization
| 9.0, 9.2 |
4/13 | No Class: Easter Break | ||
23 | 4/18 | Approximation Algorithms | 10.1 |
24 | 4/20 | Probabilistic Computation, BPP; advance topic (time permitting) | 10.2 |
25 | 4/25 | Lecture overflow; final exam review
| |
4/27 | No Class
| ||
5/5 to 5/13 | Final exam period (the date, time, and location of exam will be posted by the registrar during the semester.) |