### Final Exam is Thursday, December 14th from 12pm-2pm

### Quiz Dates

~~September 19~~
~~October 5~~
**Midterm:** October 12~~November 2~~

November 21

December 7
**The final exam will be Thursday, December 14 in Robinson 253**

### Homework Dates

~~Homework 1 handed out September 12 and due September 19~~
~~Homework 2 handed out September 19 and due September 28 (extended from Sep 26)~~
~~Homework 3 handed out September 26 and due October 10 (extended from Oct 3)~~
~~Homework 4 handed out October 17 and due October 24 (extended from Oct 10)~~
~~Homework 5 handed out October 24 and due October 31~~
~~Homework 6 handed out October 31 and due November 9~~

Homework 7 handed out November 14 and due November 30

Homework 8 handed out November 28 and due December 7

### Topic Schedule

Here is a list of topics we intend to discuss in the course and the associated chapters in the text. The topics are listed in the general order in which they will be presented in class. They do not directly map to a single lecture, some topics will be discussed in multiple lectures, and some only a fraction of the lecture.

A bit about Turing Machines, Chapter 3

Finite Automata, Chapter 1

Regular Expressions, Chapter 1

Pumping Lemma, Chapter 1

Context Free Grammars, Chapter 2

Pushdown Automata, Chapter 2

Context Free Languages, Chapter 2

Back to Turing Machines, Chapter 3

Alternate Types of Turing Machines, Chapter 3

Church/Turing Thesis, Chapter 3

Algorithms, Chapter 3

Decidability, Chapter 4

The Halting Problem, Chapter 4

Diagonalization, Chapter 4

Reductions, Chapter 5

Turing reductions, Chapter 6

Oracles, Chapter 6 (possibly)

Time Restraints, Chapter 7

Polynomial time, Chapter 7

NP, Chapter 7

NP completeness, Chapter 7

Polynomial Hierarchy, Chapter 10

Polynomial Space, Chapter 8