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

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.

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 sets | 40% |

Midterm | 30% |

Final | 30% |

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.

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:

- 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 percent of the points deducted.
Problem sets not handed until the day
*after*the deadline will have an additional 10 percent deducted (slide late problem sets under my door if I am not in my office). Beyond this point, problem sets will not be accepted (barring special circumstances).

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 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
Number | Date | Description |
Readings |

Part 1: Automata and Languages | |||

1 | 1/9 | Intro; finite automata | 1.1 |

2 | 1/14 | Non-determinism; regular operation closure properties
**pset 1 available**(covers lectures 1 - 6; due on 2/4)
| 1.2 |

3 | 1/16 | Equivalence of regular languages and regular expressions; regular language pumping lemma | 1.3, 1.4 |

4 | 1/21 | Context free languages; universality of Chomsky Normal Form | 2.1 |

5 | 1/23 | Pushdown automata and their equivalence with context free languages | 2.2 |

6 | 1/28 | Context free language pumping lemma; Part 1 lecture overflow | 2.3 |

Part 2: Computability Theory | |||

7 | 1/30 | Turing machines | 4.1 |

8 | 2/4 | Some decidable and recognizable
languages. Proof of undecidable and unrecognizable
languages.
**pset 2 available**(covers lectures 7 - 11; due 2/20)
| 4.1, 4.2 |

9 | 2/6 | Reducibility | 5.1, 5.3, 6.3 |

10 | 2/11 | Reducibility (cont); LBAs | 5.1, 5.2, 5.3, 6.3 |

11 | 2/13 | Recursion Theorem | 6.1 |

2/18 | No Class: President's Day (Monday Schedule)
| ||

12 | 2/20 | Lecture overflow; midterm review | |

13 | 2/25 | Midterm
| |

Part 3: Complexity Theory | |||

14 | 2/27 | Time complexity; TIME and NTIME classes
**pset 3 available**(covers lectures 14 -17; due 3/24) -
| 7.1 |

15 | 3/3 | The classes P and NP | 7.2, 7.3 |

16 | 3/5 | NP-completeness | 7.4 |

3/10 | No Class: Spring Break | ||

3/12 | No Class: Spring Break | ||

17 | 3/17 | Cook-Levin Theorem | 7.4 |

18 | 3/19 | Space Complexity; SPACE and
NSPACE complexity classes**pset 4 available**(covers lectures 18 - 22; due 4/7)
| 8.0 |

19 | 3/24 | Savitch's Theorem | 8.1, 8.2, 8.3 |

20 | 3/26 | PSPACE and PSPACE-Completeness | 8.1, 8.2, 8.3 |

21 | 3/31 | Games and Generalized Geography | 8.3 |

22 | 4/2 | L and NL | 8.4, 8.5, 8.6 |

23 | 4/7 | NL-Completeness, and NL =
coNL
**pset 5 available**(covers lectures 23 - 25; due 4/21)
| 8.4, 8.5, 8.6 |

4/9 | No Class: Easter Break | ||

24 | 4/14 | Hierarchy Theorems | 9.0, 9.1 |

25 | 4/16 | Relativization | 9.0, 9.2 |

26 | 4/21 | BPP | 10.1, 10.2 |

27 | 4/23 | Overflow/Advanced Topics | 10.1, 10.2 |

28 | 4/28 | Final Exam Review |