This course covers foundational results in theoretical computer science. Approximately the first half of the course will focus on finite automata and computability theory, with the remainder focused on complexity theory.
Students will come way from this course familiar with the classic concepts from theoretical computer science (language types, what you can and cannot solve with computers, the complexity of problems, including NPcompleteness, and so on). Students will also develop comfort formally proving things both possible and impossible.
The required textbook for this course is Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, 2012. Most of the topics covered in this course, and many of the problem set problems, will be drawn from this text.
Grades in the course will be based on biweekly problem sets, two exams, and participation. The participation grade will be based on your attendance and involvement in class. If you show up to class, pay attention, and ask questions when stuck (either in class, or after class), you will get full participation points.
In determining your final grade, I will calculate the percentage of available points you received for your problem sets, exams, and participation, and then combine these percentages with the following weights:
Problem sets  50% 
Midterm  20% 
Final  20% 
Participation  10% 
Every student will therefore end up with a single weighted point percentage. Toward the end of the course, I will decide the mapping from ranges of these values to letter grades. Feel free to check in with me earlier in the semester, however, for an estimate of where you stand.
A few tips for doing well in this course without excessive amounts of stress:
I hold regular office hours from 11:30 am to 1:00 pm on Thursdays, in my office at 342 A Saint Mary's Hall. If this time conflicts with your class schedule, let me know, and we can arrange alternate meetings as needed.
To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, I prefer that you bring them to office hours. Use email only when the above two options are not applicable.
The following rules will help keep the problem set submission and grading process running smoothly:
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 tentative schedule for the course. I will modify the schedule as needed as the course progresses. Problem sets will be posted below on this 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/10  Intro; finite automata  1.1 
2  1/15  Nondeterminism; regular languages;
 1.2, 1.3 
3  1/17  Pumping lemma for regular languages; contextfree grammars; Chomsky normal form  1.4, 2.1 
4  1/22  Pushdown automata; pumping lemma for contextfree languages  2.2, 2.3 
Part 2: Computability Theory  
5  1/24  Turing machines  3.1 
6  1/29  Decidable languages; file lookup machine;
 4.1 
7  1/31  Undecidable and Unrecognizable languages  4.2 
8  2/5  Reducibility  5.1, 5.3, 6.3 
9  2/7  Linearbounded automata; PCP  5.1, 5.2 
10  2/12  Advanced topics in computability theory: recursion
theorem;
 6.1 
11  2/14  Lecture overflow; midterm review  
12  2/19  Midterm
 
13  2/21  Advanced topics in computability theory: decidability of logical theories, Godel's incompleteness theorem, and the computational complexity of information  6.2, 6.4 
Part 3: Complexity Theory  
14  2/26  Time complexity; TIME and NTIME complexity classes  7.1 
15  2/28  The classes P and NP
 7.2, 7.3 
3/5  No Class: Spring Break  
3/7  No Class: Spring Break  
16  3/12  NPcompleteness; the CookLevin theorem;
 7.4 
17  3/14  More NPcomplete problems  7.4, 7.5 
18  3/19  Space Complexity; SPACE and NSPACE complexity classes  8.0 
19  3/21  Savitch's Theorem; PSPACE and PSPACECompleteness  8.1, 8.2, 8.3 
20  3/26  Games and Generalized Geography;

8.3 
3/28  No Class: Easter Break  
21  4/2  L and NL, NLCompleteness, and NL = coNL  8.4, 8.5, 8.6 
22  4/4  Hierarchy Theorems  9.0, 9.1 
23  4/9  Intractable Problems;
 9.0, 9.2 
24  4/11  Approximation Algorithms  10.1 
25  4/16  Probabilistic Computation, BPP  10.2 
26  4/18  Lecture overflow/advanced topic  
27  4/23  Advanced topic
 
28  4/25  Review for final examination  
Final examination (date and location pending) 
The PhD qualifying exam includes a segment on theory of computation. It is based on the material covered in COSC 545 (which is summarized in the schedule below along with the corresponding chapters of the Sipser textbook). To help your review, here is a summary of what you are expected to know from this material for the qualifying exam: