CS125 FALL 2014


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.),
Study Card Day
Section 1
Master thm
Master thm + solutions
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)