This is a more of a "What's Happened" than a "What's Coming Up" syllabus. In particular, lectures more than a week in advance are subject to adjustment depending on the pace of the class. In the assigned reading, DPV indicates the main Dasgupta, Papadimitrou and Vazirani Algorithms text. KT stands for the optional Kleinberg and Tardos book.
Monday |
Wednesday |
Friday |
Jan 4th Admin, Re-Introduction to Algos Handouts Reading
|
Jan 6th Review of numbers & arithmetic; fast multiplication Handouts Reading
|
Jan 8th Recurrence review, sorting Handouts Reading
|
Jan 11th Sorting in linear time & Selection Handouts
Reading
|
Jan 13th More Divide and Conquer -- Convex Hull Handouts
Reading
|
Jan 15th Intro to Greedy Algorithms Handouts Reading
|
Jan 18th Greedy Algorithms for Scheduling. Handouts Reading
|
Jan 20th Greedy Algorithms for Huffman Codes Handouts Reading
|
Jan 22nd Greedy Algorithms on Graphs: Minimum Spanning Trees Handouts Reading
|
Jan 25th Greedy Algorithm for the Fab4 Puzzle & Shortest Paths Handouts Reading |
Jan 27th
Reading
|
Jan 29th All-pairs Shortest Paths Handouts Reading
|
Feb 1st |
Feb 3rd |
Feb 5th Term Test 1 |
Feb 8th Dynamic Programming: LIS and Weighted Scheduling Handouts Reading
|
Feb 10th Knapsack Handouts Reading
|
Feb 12th Dynamic Programming: Edit Distance, Combining Techniques Handouts Reading
|
Reading Break! |
||
Feb 22nd Network Flow -- Residual graph, augmenting paths Handouts
Reading
|
Feb 24th Network Flow -- Ford Fulkerson, Cuts Handouts Reading Francois Pitt's notes (only on Matching and Teaching Assigment) |
Feb 26th March 3rd Network Flow -- Reductions Handouts Reading KT -- Image Segmentation |
March 1st Network Flow -- Max Flow Min Cut Theorem, Running time of FF Handouts Reading |
March 3rd Linear Programming -- Introduction HW2 Due March 4th! Handouts Reading
|
March 5th Linear Programming -- Simplex Handouts Reading
|
March 8th Linear Programming -- Examples Handouts
|
March 10th Linear Programming -- More examples Handouts Reading |
March 12th HW2/TT2 Review |
March 15th |
March 17th NP-Hardness Handouts Reading
|
March 19th Approximation Algorithms Handouts Reading
|
March 22nd Dealing with NP-hardness: Special cases Programming Project Due on March 23rd! Handouts Reading |
March 24th Local Search Handouts Reading
|
March 26th Local Search Continued Handouts Reading |
March 29th Speeding up search: Branch & Bound Handouts Reading
|
March 31st The Real World: Speeding up code • HW3 is due April 1st Handouts Reading |
April 2nd
|