CSCI 256 - Fall 2020
Algorithms Design and Analysis
Home | Lectures | Assignments | Handouts | CS@Williams
Lectures
Links to lecture slides and files will be available after class on the date shown. In the readings, KT refers to the Kleinberg-Tardos textbook, whereas E refers to Erickson. When readings from both are suggested there will generally be some overlap between the two textbooks; students are not expected to read both.
September:
Date | Lecture | Slides | Reading | |
Sep 11 | Introduction and Course Overview | Lec 1 pdf | ||
Sep 14 | Asymptotics & Stable Matchings | Lec 2 pdf | KT 1.1-1.2 & E 4.5 | |
Sep 16 | Graphs and Traversals | Lec 3 pdf Board Work |
KT 3.1-3.3 & E 5.1-5.4 | |
Sep 18 | DFS & Directed Graphs | Lec 4 pdf Board Work |
KT 3.3-3.4 & E 5.4-5.7 | |
Sep 21 | DFS Continued | Lec 5 pdf Board Work: 1 2 | KT 3.4-3.6 & E 5.6-5.7 | |
Sep 23 | Greedy: Stays Ahead & Exchange Method | Lec 6 pdf | KT 4.1-4.2 & E 4.2-4.3 | |
Sep 25 | Greedy: Min Lateness & Min Spanning Trees | Lec 7 pdf | KT 4.2, 4.5 & E 7 | |
Sep 28 | Greedy: Min Spanning Trees & Union Find | Lec 8 pdf | KT 4.6 & E 7 | |
Sep 30 | Greedy: Min Spanning Trees & Union Find | Lec 9 pdf | KT 4.2 | |
October:
Date | Lecture | Slides | Reading | |
Oct 02 | MST and Shortest Path | Lec 10 pdf | KT 4.4 | |
Oct 05 | Divide and Conquer: Sorting and Recurrences | Lec 11 pdf | KT 5.1, 5.3 & E 1.4-1.5 | |
Oct 07 | Divide and Conquer: Sorting and Recurrences | Lec 12 pdf | KT 5.2 & E 1.6-1.7 | |
Oct 14 | Divide and Conquer: Sorting and Recurrences | Lec 13 pdf | KT 5.2 & E 1.6-1.7 | |
Oct 16 | Selection and Intro to Dynamic Programming | Lec 14 pdf | KT 6.1-6.2 | |
Oct 19 | Dynamic Programming, Weighted Interval Scheduling | Lec 15 pdf | KT 6.6 & E 3.1-3.6 | |
Oct 21 | DP: LIS, Edit Distance, and Knapsack Problem | Lec 16 pdf | KT 6.4-6.5 & E 3.7-3.8 | |
Oct 23 | DP: LIS, Edit Distance, and Knapsack Problem | Lec 17 pdf | KT 6.9-6.10 & E 9.5 | |
Oct 26 | DP: Knapsack and Shortest Path Revisited | Lec 18 pdf | KT 6.9-6.10 & E 9.5 | |
Oct 28 | Midterm | |||
Oct 30 | Introduction to Network Flows | Lec 19 pdf | KT 7.1-7.2 & E 10.1-10.2 | |
November:
Date | Lecture | Slides | Reading | |
Nov 02 | Ford-Fulkerson Algorithm and Analysis | Lec 20 pdf | KT 7.2-7.3 & E 10.3 | |
Nov 04 | Network Flow Applications | Lec 21 pdf | KT 7.5, 7.6 & E 11 | |
Nov 06 | Classes: P, NP, NP-hard and NP-Complete | Lec 22 pdf | KT 8.1, 8.3 & E 12.1-12.5 | |
Nov 09 | Reductions and NP-hardness | Lec 23 pdf | KT 8.1, 8.3 & E 12.1-12.5 | |
Nov 11 | More Reductions | Lec 24 pdf | KT 8.2, 8.4 & E 12.6-12.8 | |
Nov 13 | Wrapping Up Intractability, Probability | Lec 25 pdf | Glow lecture notes 17-19 | |
Nov 16 | Randomization: Probability Review | Lec 26 pdf | Glow lecture notes 20-22 | |
Nov 18 | Randomization: Probability Review | Lec 27 pdf | Glow lecture notes 23 | |
Nov 20 | Karger's Min Cut & Randomized QuickSort | Lec 28 pdf | KT 13.2, 13.5 & E Min Cut Handout | |
Nov 23 | Randomized Max-3-SAT and Max-Cut | Lec 29 pdf | KT 13.4 | |
Nov 30 | Hashing | Lec 30 pdf | E Hashing Handout | |
December:
Date | Lecture | Slides | Reading | |
Dec 02 | Cuckoo Hashing and Skip Lists | Lec 31 pdf | E Handout 3.2 | |
Dec 04 | Approximation Algorithms: Load Balancing | Lec 32 pdf | KT 11.1 | |
Dec 07 | Approximate TSP | Lec 33 pdf | E Handout 7-8 | |
Dec 09 | Approximate Set Cover | Lec 34 pdf | KT 11.3 | |
Dec 11 | Wrap-up and Review | Lec 35 pdf | ||
Copyright 2020 | Department of Computer Science :: 47 Lab Campus Drive :: Williamstown, MA 01267 |