### Final Exam

The final exam is Thursday May 9th from 12-2:00pm in TBA

### Quiz Dates

January 31

February 14

February 28

March 14

April 4

April 18

### Homework Dates

Homework 1 handed out January 22 and due January 29

Homework 2 handed out January 29 and due Februdary 5

Homework 3 handed out Februdary 5 and due Februdary 12

Homework 4 handed out Februdary 12 and due Februdary 19

Homework 5 handed out Februdary 19 and due Februdary 26

Homework 6 handed out Februdary 26 and due March 5

Homework 7 handed out March 5 and due March 12

Homework 8 handed out March 26 and due April 2

Homework 9 handed out April 2 and due April 9

Homework 10 handed out April 9 and due April 16

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