Final Exam is TBD

Quiz Dates

Homework Dates

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