COSC 545 - Theory of Computation (Spring 2016)
Georgetown University
Prof. Calvin Newport
Tuesday and Thursday, 2:00 to 3:15
Car Barn 202
Course Overview
Description
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).
This course is open to PhD and Masters students. I'm also happy to allow advanced undergraduates to enroll with my permission.
Textbook
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.
Grading
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% |
How to Get an A in this Course (without Burning Out)
A few tips for doing well in this course without excessive amounts of stress:
- To save time, do not read the textbook before lecture. Instead, pay careful attention during class and then go back and use the textbook to fill in only what you did not understand.
- Learn the material the same week it is presented (using your textbook, your classmates, and me to help understand what confuses you). If you do this, studying for the exams will amount to a tractable review. If you do not do this, studying will devolve into a mind-numbing slog.
- Start problem sets early. Work systematically in focused bursts. Expect to need multiple sessions to finish the assignments. My general strategy as a graduate student, for example, was to never spend more than two hours on any given day on any given problem set. (See this article for more advanced problem set strategies.)
- I am always happy to chat about the tactical side of succeeding as a graduate student (time management, study skills, etc.). Feel free to come to office hours to talk shop on these issues.
Course Logistics
Office Hours
I hold regular office hours in my office at 334 Saint Mary's Hall from 12:30 to 1:30 on Tuesday and Thursday.
Problem Sets
The following rules describe my expectations and grading policies for problem sets:
- 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, solutions from previous classes, or talk to other students when working on problem set problems.
- Problem sets should be handed in at the beginning of class on the day they are due. That is, bring a physical copy of the problem set to class to give to me before the lecture begins.
- Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (slide late problem sets under my door if I am not in my office). Beyond this point, problem sets will not be accepted.
Exams
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).
Academic Integrity
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.
Schedule
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/14 | Intro; finite automata
| 1.1 |
| 2 | 1/19 | Non-determinism; regular languages; | 1.2, 1.3 |
| 3 | 1/21 | Pumping lemma for regular languages; context-free grammars; Chomsky normal form | 1.4, 2.1 |
| 4 | 1/26 | Pushdown automata; pumping lemma for context-free languages | 2.2, 2.3 |
| 5 | 1/28 | Context-free languages | 3.1 |
| Part 2: Computability Theory | |||
| 6 | 2/2 | Context-free languages (cont.) | 4.1 |
| 7 | 2/4 | Turing machines
| 4.1 |
| 8 | 2/9 | Some decidable and recognizable languages. Proof of undecidable and unrecognizable languages. | 4.1, 4.2 |
| 9 | 2/11 | Reducibility | 5.1, 5.3, 6.3 |
| 10 | 2/16 | LBAs and PCP theorem | 5.1, 5.2 |
| 11 | 2/18 | Recursion theorem | 6.1 |
| 11 | 2/23 | Lecture overflow; midterm review
| |
| 12 | 2/25 | Midterm | |
| Part 3: Complexity Theory | |||
| 14 | 3/1 | Time complexity; TIME and NTIME complexity classes
| 7.1 |
| 15 | 3/3 | The classes P and NP | 7.2, 7.3 |
| 3/8 | No Class: Spring Break | ||
| 3/10 | No Class: Spring Break | ||
| 16 | 3/15 | NP-completeness; the Cook-Levin theorem; | 7.4 |
| 17 | 3/17 | More NP-complete problems | 7.4, 7.5 |
| 18 | 3/22 | Space Complexity; SPACE and NSPACE complexity classes | 8.0 |
| 3/24 | No Class: Easter Break | ||
| 19 | 3/29 | Savitch's Theorem; PSPACE and
PSPACE-Completeness
| 8.1, 8.2, 8.3 |
| 20 | 3/31 | Games and Generalized Geography; | 8.3 |
| 21 | 4/5 | L and NL, NL-Completeness, and NL = coNL | 8.4, 8.5, 8.6 |
| 22 | 4/7 | Hierarchy Theorems | 9.0, 9.1 |
| 23 | 4/12 | Relativization
| 9.0, 9.2 |
| 24 | 4/14 | Approximation Algorithms | 10.1 |
| 25 | 4/19 | Probabilistic Computation, BPP | 10.2 |
| 26 | 4/21 | Advanced topic | |
| 27 | 4/26 | Advanced topic
| |
| 28 | 4/28 | Final exam review | |
| 5/6 to 5/14 | Final exam period (specific date and location of our exam is pending) |
Qualifying Exam
The PhD qualifying exam includes a segment on theory of computation. It is based on the material covered in COSC 545 (see the schedule above for a list of topics and corresponding chapters in 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:
- From Part 1 of the Course: You should be comfortable proving that languages are and are not regular and/or context-free. This includes familarity with all equivalent models for these language classes and the various pumping lemmata.
- From Part 2 of the Course: You should be comfortable with the definitions of different Turing Machine models and the Turing decidable and Turing recognizable language classes. In addition to proving that languages are decidable and/or recognizable, you might also be asked to prove problems not decidable and/or not recognizable using standard reductions and mapping reductions. Your reduction tool kit should include the computation history method.
- From Part 3 of the Course: You should be comfortable with analyzing time complexity and working with the complexity classes TIME, NTIME, P, and NP. You should be comfortable proving problems are NP-complete. In addition, you should be comfortable analyzing space complexity and working with the complexity classess SPACE, NSPACE, PSPACE, L, NL, and co-NL. Finally, you should know the main space and time hierarchy theorems, but not necessarily the details of their proofs.