Final Exam is May 11th from 8:30-10:30am

Quiz Dates

February 1
February 15
March 1
March 15
April 5
April 19
The final exam will be on May 11th from 8:30am-10:30am in Braker 001

Homework Dates

Homework 1 handed out January 23 and due January 30
Homework 2 handed out January 30 and due February 6
Homework 3 handed out February 6 and due February 13
Homework 4 handed out February 13 and due February 20
Homework 5 handed out February 20 and due February 27
Homework 6 handed out February 27 and due March 6
Homework 7 handed out March 6 and due March 13
Homework 8 handed out March 27 and due April 3
Homework 9 handed out April 3 and due April 10
Homework 10 handed out April 10 and due April 17
Extra Credit handed out April 17 and due April 24

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