CSCI 256 - Spring 2025

Algorithm Design and Analysis

Home | Lectures | Problem Sets | 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!**

Part 1:

Date Lecture Sec 1 Slides Sec 2 Slides Reading
Feb 5 Introduction and Proofs of Correctness slides slides
Feb 10 Proofs & Asymptotics slides slides KT 1.1-1.2 or E 4.5
Feb 13 Stable Matchings & Intro to Graphs slides slides KT 3.1-3.2 or
E 5.1-5.3, 5.5-5.7
Feb 17 BFS, DFS slides slides KT 3.3-3.6 or
E 5.4, 6.1-6.2
Feb 20 DFS and Topological Sort slides slides KT 3.3-3.6 or
E 6.1-6.3, 6.5-6.6
Feb 24 Greedy Algorithms slides slides KT 4-4.2, 4.5-4.6 or
E 4.2, 7-7.2, 7.4-7.5
Feb 27 Dijkstra's Algorithm slides slides KT 4.4 or E 8.6
Mar 3 Minimum Spanning Trees slides slides KT 4.5-4.6 or
E 7-7.2, 7.4-7.5
March 6 Kruskal's MST Algorithm, Recap slides slides
Mar 10 Midterm 1

Part 2:

Date Lecture Sec 1 Slides Sec 2 Slides Reading
March 13 Divide and Conquer KT 5.1-5.3, 5.5 or
E 1.4-1.7, 1.9
March 17 Matrix Multiplication, Selection KT 6-6.2 or
E 1.8, 3.1
March 20 Dynamic Program: Memoized Recursion KT 6-6.2 or
E 3.1, 3.4
April 7 Dynamic Programming Examples KT 6.4, 6.6 or
E 3.7-3.8
April 10 More Dynamic Programming Examples KT 6.8 or E 8.7
Apr 14 Network Flows KT 7-7.3 or
E 10-10.4
April 17 Ford-Fulkerson Algorithm KT 7-7.3 or
E 10-10.4
April 21 Network Flows and Reductions KT 7-7.3, 7.5-7.6 or
E 10-10.4,11.1-11.4
April 24 Network Flows and Reductions Cont.
April 28 Midterm 2

Part 3:

Date Lecture Sec 1 Slides Sec 2 Slides Reading
May 1 No Class! KT 8.1-8.4 or
E 12.5-12.8
May 5 P, NP, and NP Completeness KT 8.1-8.4 or
E 12.5-12.8
May 8 NP Hardness Reductions KT 8.1-8.5 or
E 12.5-12.8
May 12 Approximation Algorithms KT 11.1-11.2
May 15 Review
Copyright 2020 | Department of Computer Science :: 47 Lab Campus Drive :: Williamstown, MA 01267