CSC 373 Winter 09 Syllabus

---

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 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 5th Admin, Re-Introduction to Algos Handouts Course Information sheet Lecture Notes 1 Reading DPV Chapter 0 (Review)	Jan 7th Review of numbers & arithmetic; fast multiplication Handouts Lecture Notes 2 Reading DPV Sections 1-1.2 (Review), 2.1	Jan 9th Recurrence review, sorting Handouts Lecture Notes 3 Puzzle to Ponder Reading DPV Sections 2.2, 2.3
Jan 12th Sorting in linear time & Selection Handouts Continuing Lecture Notes 3 Reading DPV 2.4, Counting Sort	Jan 14th More Divide and Conquer -- Convex Hull Handouts Reading Lecture notes on the Convex Hull (only the D&C algorithm, up to QuickHull)	Jan 16th Randomized Algorithms & A puzzle Handouts KT, Parts of Section 4.1, 4.2 Reading The Prisoner Bible
Jan 17th Greegy Algorithms for Interval Scheduling Handouts Reading KT Section 4.1 (the part that is in your handout)	Jan 19th Greedy Algorithms for Scheduling With Deadlines. Handouts Assignment 1 Reading KT 4.2	Jan 21st Proofs Gone Wrong: A Lecture on Mathematical Writing Handouts Lecture Slides Reading None
Jan 26th Greegy Algorithms for Huffman Codes Handouts Proof of optimality Reading DPV Section 5.2 Proof of optimality	Jan 28th Greedy Algorithms on Graphs: Minimum Spanning Trees Handouts Reading DVP Sections 4-4.5, 5-5.1	Jan 30th Advanced Tuorial -- Compression Handouts Reading None
Feb 2nd Greedy Algorithms for Shortest Paths Handouts Reading	Feb 4th Bellman-Ford algorithm for shortest paths. Recursion Trees Memoization Handouts HW1 Due on Feb 5th! Reading DPV Section 4.6 KT Section handout	Feb 6th Dynamic Programming Handouts Reading
Feb 9nd All-pairs Shortest Paths Handouts Reading DPV 6.6	Feb 11th Longest Increasing Subsequence Edit Distance Handouts Assignment 2 Reading DPV 6.2, 6.3	Feb 13th Dynamic Programming: Sparse LIS & LCS Handouts Reading Gusfield Book Handout
Reading Break!
Feb 23rd Combining Techniques: DNA Sequence Alignment Handouts Note: HW2 Due on Feb 24th! Reading	Feb 25th HW1 Review Handouts Reading	Feb 27th HW2 Review Handouts Reading
March 2nd Midterm!!! Handouts Reading	March 4th Network Flow -- Residual graph, augmenting paths Handouts Reading	March 6th Network Flow -- Ford Fulkerson, Cuts Handouts Midterm Solutions Handout on Network Flow from KT Reading Handout on Network Flow from KT
March 9th Network Flow -- Max Flow Min Cut Theorem, Running time of FF Handouts Programming Project Reading	March 11th Network Flow -- Reductions Handouts Reading Francois Pitt's notes (only on Matching and Teaching Assigment)	March 13th Network Flow -- More Reductions Handouts Reading KT -- Image Segmentation
March 16th Linear Programming -- Introduction Handouts Reading DPV 7.1	March 18th Linear Programming -- Simplex Handouts Reading DPV 7.6	March 20th Linear Programming -- Examples Handouts Reading
March 23rd Linear Programming -- More examples Handouts Reading	March 25th NP-Hardness Handouts Programming Project Due on March 26th! HW3 Reading DPV 8-8.2	March 27th Approximation Algorithms Handouts Reading DPV 9.2
March 30th Dealing with NP-hardness: Special cases Handouts Reading	April 1st Local Search Handouts Reading DPV 9.3	April 3rd Local Search Continued Handouts Reading
April 6th Speeding up search: Branch & Bound Handouts Reading DPV 9.1	April 8th The Real World: Speeding up code Handouts HW3 is due April 9th, 5pm Reading	April 10th NO CLASS -- EASTER Handouts Reading