CS125 FALL 2015


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.),
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