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.),
Union-Find
Study Card Day |
Section 1
Master thm
Master thm + solutions |
HW2 |
| Th |
9/11 |
Union-Find (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 Church-Turing 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 Poly-Time, P vs. NP |
Section 8
|
|
| Th |
10/30 |
NP-completeness |
|
HW7 due (Fri)
HW8, HW8 source |
| Tu |
11/4 |
Cook-Levin 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 NP-completeness) |
|
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) |
|
|