### Final Exam

The final exam is December 13th from 12:00-2:00pm

### Quiz Dates

September 20

October 4

October 18

November 1

November 15

November 29

### Homework Dates

Homework 1 handed out September 11 and due September 18

Homework 2 handed out September 18 and due September 25

Homework 3 handed out September 25 and due October 2

Homework 4 handed out October 2 and due October 9

Homework 5 handed out October 9 and due October 16

Homework 6 handed out October 16 and due October 23

Homework 7 handed out October 23 and due October 30

Homework 8 handed out October 30 and due November 6

Homework 9 handed out November 6 and due November 13

Homework 10 handed out November 13 and due November 20

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

Math review, Chapter 0

Proof techniques, Chapter 0

Diagonalization, Chapter 4

GĂ¶del's incompleteness theorem

Turing Machines, Chapter 3

Church/Turing Thesis, Chapter 3

Alternate Types of Turing Machines, Chapter 3

Algorithms, Chapter 3

Decidability, Chapter 4

The Halting Problem, Chapter 4

Reductions, Chapter 5

Turing reductions, Chapter 6

Oracles, Chapter 6

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

Time Restraints, Chapter 7

Polynomial time, Chapter 7

NP, Chapter 7

NP completeness, Chapter 7

Polynomial Hierarchy, Chapter 10

Polynomial Space, Chapter 8