Schedule
Click on the links to view the lecture notes. For homeworks or other handouts, contact the instructors.
Note: for now, please email assignments to cs125harvard, but not at SEAS, instead at gmail.com.
(colors indicate weeks)
Day |
Date |
Topic & Lecture Notes |
Other Handouts |
Homework |
Th |
9/3 |
Sorting |
syllabus, survey |
HW1, HW1 source, HW1 solutions |
Tu |
9/8 |
Sorting (cont.), Greedy Algorithms |
|
|
Th |
9/10 |
Greedy Algorithms (cont.),
Union-Find
Study Card Day |
Section 1
Master thm
| HW2; HW1 due (Fri) |
Tu |
9/15 |
Divide & Conquer |
|
|
Th |
9/17 |
Dynamic Programming |
Section 2
|
HW3, HW3 source, buffy.txt, HW3 solutions; HW2 due (Fri) |
Tu |
9/22 |
Models of Computation: RAMs |
|
HW2 due (Fri) |
Th |
9/24 |
RAMs (cont.), Turing Machines |
Palindrome TM,
Section 3
|
HW4,HW4 source, HW3 due (Fri), HW4 solutions |
Tu |
9/29 |
Turing Machines (cont.) |
Turing's paper |
|
Th |
10/1 |
Shortest Paths
|
Section 4
|
HW5,HW5 source, HW4 due (Saturday), HW5 solutions |
Tu |
10/6 |
Linear programming |
Midterm Review Section
|
|
Th |
10/8 |
Linear programming, continued, Network flows |
|
|
Tu |
10/13 |
Midterm (up to Turing machines) |
|
|
Th |
10/15 |
Network flows, Midterm follow-up |
Section 6, Section 7 |
HW6,HW6 source, HW6 solutions |
Tu |
10/20 |
Finite Automata |
|
|
Th |
10/22 |
Nondeterministic Finite Automata |
|
HW6 due (Fri)
HW7, HW7 source, HW7 solutions |
Tu |
10/27 |
Nondeterministic Poly-Time, P vs. NP |
Section 8
|
|
Th |
10/29 |
NP-completeness |
|
HW7 due (Fri)
HW8, HW8 source, HW8 solutions |
Tu |
11/3 |
Cook-Levin Thm, More on NP |
Section 9
|
|
Th |
11/5 |
Undecidability |
|
HW8 due (Fri)
HW9, HW9 source, HW9 solutions |
Tu |
11/10 |
More Undecidability, and Godel's Incompleteness Theorem |
Section 10 Hilbert's paper |
|
Th |
11/12 |
Randomness: Hashing |
|
HW9 due (Fri)
HW10, HW10 source, HW10 solutions |
Tu |
11/17 |
Randomized Algorithms & Complexity |
Section 11 |
HW9 due (Fri) |
Th |
11/19 |
Approximations and Heuristics |
|
|
Tu |
11/24 |
Approximations and Heuristics |
|
HW11, HW11 source |
Th |
11/16 |
Thanksgiving |
|
|
Tu |
12/1 |
PCP and Approximations |
|
|
Th |
12/3 |
Randomness Extraction,Wrapup |
|
|
Tu |
12/8 |
|
Final Review Notes |
|