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.


**The schedule may change as the semester progresses---check back regularly!**

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