COSC 545 - Theory of Computation (Spring 2020)

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 3:30 to 4:45 pm

Reiss 559

NEW: Information on Shift to Online Instruction

Lectures

The current plan for online instruction is to hold our lectures during their normally scheduled times using Zoom video conferencing software. I will use the shared whiteboard feature in conjunction with a writing tablet to simulate the blackboard. For now, I'll record the classes as well, though if I notice a sharp decline in attendance I might stop the practice.

We will use the same recurring meeting for all lectures. The link was sent to you via email. Let me know if you need it.

Problem Sets

The only change to the problem set process is that comlpeted problem sets will now be submitted electronically. We will likely use Canvas for this purpose. Instructions on the submission process will be posted before the next problem set is due.

Office Hours

I will be holding my offices hours at my normal times using Zoom [video conference link]. I am also available via email for any questions or concerns you have about this course, or the shift to online instruction more generally.

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).

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. Well-prepared undergraduates can take the course with professor's permission (space permitting).

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. I will provide a guide for each problem set and exam that shows how your point score roughly maps to letter grades.

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 sets40%
Midterm30%
Final30%

Course Logistics

Office Hours

I hold regular office hours in my office at 356 Saint Mary's Hall from 2:00 to 3:00 on Tuesday and Thursdays. I'm also available to answer quick questions before and after class, and via email (cn248@georgetown.edu).

Teaching Assistant

The teaching assistant for this course is Alex Weaver. He is available to answer questions about problem set problems via email (baw4ux@gmail.com) or by appointment.

Problem Sets

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:

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 (changes will occur during the semester as some things take long and other shorter than expected). 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 and Languages
11/9Intro; finite automata 1.1
21/14Non-determinism; regular operation closure properties
  • pset 1 available (covers lectures 1 - 6; due on 2/4) [Download]
1.2
31/16Equivalence of regular languages and regular expressions1.3, 1.4
41/21Equivalence of regular languages and regular expressions (cont)1.3, 1.4
51/23Regular language pumping lemma; context free languages; pushdown automata 1.4, 2.2
61/28Equivalence of pushdown automta and context-free lanuages 2.2, 2.3
Part 2: Computability Theory
71/30Context-free pumping lemma; Turing machines 2.3, 4.1
82/4Some decidable and recognizable languages. Proof of undecidable and unrecognizable languages.
  • pset 2 available [Download] (covers lectures 7 - 11; due 2/20)
4.1, 4.2
92/6Reducibility5.1, 5.3, 6.3
102/11 Reducibility (cont); LBAs5.1, 5.2, 5.3, 6.3
112/13Recursion Theorem 6.1
 2/18No Class: President's Day (Monday Schedule)  
122/20Lecture overflow; midterm review  
132/25Midterm  
Part 3: Complexity Theory
142/27Time complexity; TIME and NTIME classes
  • pset 3 available (covers lectures 14 -18; due 3/31) [Download]
7.1
153/3Time complexity (continued) 7.1
163/5The class P 7.2, 7.3
 3/10No Class: Spring Break 
 3/12No Class: Spring Break 
173/17NP-completeness [Zoom conference link] 7.4
183/19Cook-Levin Theorem7.4
193/24NP-complete problems7.4
203/26Space Complexity; SPACE and NSPACE complexity classes 8.0
213/31Savitch's Theorem
  • pset 4 available [Download] (covers lectures 20 - 22; due 4/14)
8.1, 8.2, 8.3
224/2PSPACE and PSPACE-Completeness8.1, 8.2, 8.3
234/7L and NL 8.4, 8.5, 8.6
 4/9No Class: Easter Break 
244/14NL-Completeness, and NL = coNL
  • pset 5 available (covers lectures 23 - 26; due 4/28)
8.4, 8.5, 8.6
254/16Hierarchy Theorems 9.0, 9.1
264/21Relativization 9.0, 9.2
274/23BPP 10.1, 10.2
284/28Overflow/Advanced Topics 10.1, 10.2