Schedule
Click on the links to view the lecture notes. For homeworks or other handouts, contact the instructors.
(colors indicate weeks)
Day 
Date 
Topic & Lecture Notes 
Other Handouts 
Homework 
Tu 
9/2 
Sorting 
syllabus, survey 
HW1, HW1 source 
Th 
9/4 
Sorting (cont.), Greedy Algorithms 


Tu 
9/9 
Greedy Algorithms (cont.),
UnionFind
Study Card Day 
Section 1
Master thm
Master thm + solutions 
HW2 
Th 
9/11 
UnionFind (cont.),
Divide & Conquer 

HW1 due (Fri) 
Tu 
9/16 
Dynamic Programming 
Section 2

HW3, HW3 source 
Th 
9/18 
Models of Computation: RAMs 

HW2 due (Fri) 
Tu 
9/23 
RAMs (cont.), Turing Machines 
Palindrome TM,
Section 3


Th 
9/25 
Turing Machines (cont.) 
Turing's paper 
HW3 due (Fri) 
Tu 
9/30 
The ChurchTuring Thesis,
Complexity Classes

Section 4: Quiz review


Th 
10/2 
Quiz I (up to Dynamic Programming) 
Midterm survey 
HW4, HW4 source 
Mo 
10/6 
Add/Drop Day 


Tu 
10/7 
Shortest Paths 
Section 5


Th 
10/9 
Shortest Paths (cont.)
Linear Programming 

HW4 due (Fri)
HW5, HW5 source 
Tu 
10/14 
Linear Programming (cont.)
Network Flows 
Section 6


Th 
10/16 
Network Flows (cont.) 

HW5 due (Fri)
HW6, HW6 source 
Tu 
10/21 
Finite Automata 
Section 7


Th 
10/23 
Nondeterministic Finite Automata 

HW6 due (Fri)
HW7, HW7 source 
Tu 
10/28 
Nondeterministic PolyTime, P vs. NP 
Section 8


Th 
10/30 
NPcompleteness 

HW7 due (Fri)
HW8, HW8 source 
Tu 
11/4 
CookLevin Thm, More on NP 
Section 9


Th 
11/6 
Undecidability 

HW8 due (Fri) 
Tu 
11/11 
More Undecidability, and Godel's Incompleteness Theorem 
Section 10: Quiz review Hilbert's paper 

Th 
11/13 
Quiz II (up to NPcompleteness) 

HW9, HW9 source 
Tu 
11/18 
Randomness: Hashing 
Section 11


Th 
11/20 
Randomized Algorithms & Complexity 

HW9 due (Fri) 
Tu 
11/25 
Approximation Algorithms 
Section 12

HW10, HW10 source 
Th 
11/27 
No class  Thanksgiving 
Additional problems


Tu 
12/2 
Approximation Algs (cont.), Conclusions 
Section 13


Th 
12/4 
Reading Period Starts 

HW10 due (Fri) 
Th 
12/11 
Exam Period Starts 
Final Review Notes 

We 
12/17 
Final Exam (2pm) 

