COSC 545 - Theory of Computation (Spring 2014)

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 3:30 - 4:45

Intercultural Center, Room 211B

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.

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 NP-completeness, and so on). Students will also develop comfort formally proving things both possible and impossible.

Textbook

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.

Grading

Grades in the course will be based on five 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 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 sets50%
Midterm20%
Final20%
Participation10%

 

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:

Course Logistics

Office Hours

I hold regular office hours from 1:00 to 2:30 pm on Thursdays, in my office at 334 Saint Mary's Hall. If this time conflicts with your class schedule, let me know, and we can arrange alternate meetings as needed.

Problem Sets

The following rules describe my expectations and grading policies for problem sets:

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 NumberDateDescription Readings
Part 1: Automata Theory
11/9Intro; finite automata 1.1
21/14Non-determinism; regular languages; 1.2, 1.3
31/16Pumping lemma for regular languages; context-free grammars; Chomsky normal form1.4, 2.1
41/21Pushdown automata; pumping lemma for context-free languages2.2, 2.3
51/23Context-free languages 3.1
Part 2: Computability Theory
 1/28No Class 
 1/30No Class 
62/4Context-free languages (cont.); Turing machines and decidable languages 4.1
72/6Undecidable and unrecognizable languages 4.2
82/11Reducibility5.1, 5.3, 6.3
92/13Linear-bounded automata; PCP5.1, 5.2
102/18Recursion theorem 6.1
112/20Advanced topics in computability theory: decidability of logical theories, Godel's incompleteness theorem, and the computational complexity of information
  • pset 2 due
6.2, 6.4
112/25Lecture overflow; midterm review 
122/27Midterm  
Part 3: Complexity Theory
143/4Time complexity; TIME and NTIME complexity classes 7.1
153/6The classes P and NP 7.2, 7.3
 3/11No Class: Spring Break 
 3/13No Class: Spring Break 
163/18NP-completeness; the Cook-Levin theorem; 7.4
173/20More NP-complete problems7.4, 7.5
183/25Space Complexity; SPACE and NSPACE complexity classes 8.0
193/27Savitch's Theorem; PSPACE and PSPACE-Completeness
  • pset 3 due
  • pset 4 available [Download]
8.1, 8.2, 8.3
204/1Games and Generalized Geography; 8.3
214/3L and NL, NL-Completeness, and NL = coNL8.4, 8.5, 8.6
224/8Hierarchy Theorems 9.0, 9.1
234/10Relativization
  • pset 4 due
  • pset 5 available [Download]
9.0, 9.2
244/15Approximation Algorithms10.1
 4/17No Class: Easter Break 
254/22Probabilistic Computation, BPP 10.2
264/24Lecture overflow; final exam review (last day for graduate students to withdrawal from course)
  • pset 5 due
 
 5/2 to 5/10Final examination (specific date and location 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: