COSC 545 - Theory of Computation (Spring 2012)
Georgetown University
Prof. Calvin Newport
Monday and Wednesday, 3:30 pm - 4:45 pm
Intercultural Center, Room 120
Course Overview
Description
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.
Textbook
The required textbook for this course is Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, 2006. Most of the topics covered in this course, and many of the problem set problems, will be drawn from this text.
Grading
Grades in the course will be based on six biweekly problem sets, two exams, and participation. The participation grade will be based on your attendance and involvement in class as well as the quality of your work when it is your turn to help grade problem sets. If you want full participation points, come to class, pay attention, ask good questions, and be thoughtful with your grading.
In determining your final grade, here is the relative weight for these factors:
| Problem sets | 40% |
| Midterm | 25% |
| Final | 25% |
| Participation | 10% |
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 an easy 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. Feel free to come to office hours to talk shop on these issues.
Course Logistics
Office Hours
Office hours for this course will be held from 2:00 to 3:00 pm on Tuesdays, in my office. If we get backed up, office hours can continue as late as needed.
Contact
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 e-mail only when the above two options are not applicable.
Problem Sets
The following rules will help keep the problem set submission and grading process running smoothly:
- 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.
- You may work in groups on your problem set. Every student, however, must write up his own solutions in his own words. If you essentially copy the answers of one of your collaborators you will not get credit. Furthermore, every student must list the names of every collaborator on the first page of their submission.
- Do not staple your problem set pages together. Put your name and problem number at the top of every page. (This will simplify grading, as different problems will be given to different graders.)
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).
At least one question from the problem sets will be included on each exam. This question will be too difficult to figure out from scratch during the exam, so students should aim to understand their answers to every problem set problem they submit.
Material Covered by Midterm
The midterm covers lectures 1 to 10 and problem sets 1 and 2. From the lectures, you are expected to know all important definitions, to understand the proofs for any result that explicitly compares the strength of different language classes/computational models, and be comfortable with all important techniques (e.g., the pumping lemmas, mapping reducibility, etc.). You are not, however, expected to know all the examples covered in lecture. For the problem sets, you should understand and be able to provide an answer for every assigned problem.
Academic Integrity
I take academic integrity seriously. Your work on your problem sets should be the work solely of you and your collaborators. No other sources are allowed. That is, do not look up answers online, in other textbooks, etc. You must write-up your problem set work in your own words and list every collaborator.
Needless to say, during exams no outside resources may be consulted.
Problem Set Grading
Every student in the class will take turns grading problem sets. When it is your turn, we will meet, along with the other grader(s) for the problem set, at 1:00 pm on the Tuesday after the problem set is due, to review the problems and construct a grading rubric. You will then have a set period of time to grade your assigned problems according to the rubric and submit the grades.
My goal is for every student to only grade one problem set and have at least one other student helping with the problem set. The exact schedule will depend on enrollment.
We will discuss the details of this process as we get closer to the first problem set being due.
Qualifying Exam
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:
- 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 regular language pumping lemma.
- 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.
Schedule
Below is the tentative schedule for the course. Pending topics will be added and existing topics modified as the course progresses. Problem sets will be posted 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/11 | Intro; finite automata | 1.1 |
| 2 | 1/18 | Non-determinism; regular languages;
| 1.2, 1.3 |
| 3 | 1/23 | Pumping lemma for regular languages; context-free grammars; Chomsky normal form | 1.4, 2.1 |
| 4 | 1/25 | Pushdown automata; pumping lemma for context-free languages | 2.2, 2.3 |
| Part 2: Computability Theory | |||
| 5 | 1/30 | Turing machines | 3.1 |
| 6 | 2/1 | Decidable languages; file look-up machine;
| 4.1 |
| 7 | 2/6 | Undecidable and Unrecognizable languages | 4.2 |
| 8 | 2/8 | Reducibility | 5.1, 5.3, 6.3 |
| 9 | 2/13 | Linear-bounded automata; PCP | 5.1, 5.2 |
| 10 | 2/15 | Advanced topics in computability theory: recursion theorem; midterm review; pset 2 due (Graders: Brad and Chris) | 6.1 |
| 11 | 2/22 | Midterm
| |
| 12 | 2/27 | 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 | |||
| 13 | 2/29 | Time complexity; TIME and NTIME complexity classes | 7.1 |
| 14 | 3/12 | The classes P and NP | 7.2, 7.3 |
| 15 | 3/14 | NP-completeness; the Cook-Levin theorem;
| 7.4 |
| 16 | 3/19 | More NP-complete problems | 7.4, 7.5 |
| 17 | 3/21 | Space Complexity; SPACE and NSPACE complexity classes | 8.0 |
| 18 | 3/26 | Savitch's Theorem; PSPACE and PSPACE-Completeness | 8.1, 8.2, 8.3 |
| 19 | 3/28 | Games and Generalized Geography;
|
8.3 |
| 20 | 4/2 | L and NL, NL-Completeness, and NL = coNL | 8.4, 8.5, 8.6 |
| 21 | 4/4 | Hierarchy Theorems | 9.0, 9.1 |
| 22 | 4/11 | Intractable Problems;
| 9.0, 9.2 |
| 23 | 4/16 | No Class. | |
| 24 | 4/18 | Approximation Algorithms | 10.1 |
| 25 | 4/23 | Probabilistic Computation, BPP | 10.2 |
| 26 | 4/25 | Open (Lecture Overflow and/or Advanced Topic) pset 6 due (Graders: Me) | |
| 27 | 4/30 | Review for final examination | |
| 5/10 | Final Exam; 4:00 - 6:00pm; ICC 213 |