CSCI 256 Spring 2024

CSCI 256 - Spring 2024

Algorithm 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!**

Part 1:

Date	Lecture	Sec 1 Slides	Sec 2 Slides	Reading

Jan 31	Introduction and Proofs of Correctness	slides board1	slides board2

Feb 5	Asymptotics & Stable Matchings	slides 1 2 3 5	slides 1 2 5	KT 1.1-1.2 or E 4.5

Feb 8	Stable Matching contd., BFS	slides 1 2 2.5 3 4	slides 1 2 2.5 3 4	KT 3.1-3.2 or E 5.1-5.3, 5.5-5.7

Feb 12	BFS cont., DFS	slides 1 2 3	slides 1 2 3	KT 3.3-3.6 or E 5.4, 6.1-6.2

Feb 15	DFS and Topological Sort	slides 1 2 2.5	slides 1 2	KT 3.3-3.6 or E 6.1-6.3, 6.5-6.6

Feb 19	Greedy Algorithms	slides 1 1.5 2 45 6 8	slides 1 1.5 2 3 45 6 8	KT 4-4.2, 4.5-4.6 or E 4.2, 7-7.2, 7.4-7.5

Feb 22	Minimum Spanning Trees	slides: 1 2 board: 1	slides: 1 2 board: 1 2	KT 4.5-4.6 or E 7-7.2, 7.4-7.5

Feb 26	Kruskal's MST Algorithm, Recap	slides board: 1	slides board: 1

Feb 29	Midterm 1

Part 2:

Date	Lecture	Sec 1 Slides	Sec 2 Slides	Reading

Mar 4	Dijkstra's Algorithm	slides: 1 2 board: 1 2 3	slides: 1 2 board: 1 2 3	KT 4.4 or E 8.6

March 7	Divide and Conquer	slides 1 2 2.5 3 4	slides 1 2 2.5 3 4	KT 5.1-5.3, 5.5 or E 1.4-1.7, 1.9

March 11	Divide and Conquer, Selection	slides board: 1 2 3 4	slides board: 1 2 3 4	KT 6-6.2 or E 1.8, 3.1

March 14	Dynamic Program: Memoized Recursion	slides: 1 2 board: 1	slides: 1 2 board: 1	KT 6-6.2 or E 3.1, 3.4

April 1	Dynamic Programming Examples	slides: 1 2 board: 1	slides: 1 2 board: 1	KT 6.4, 6.6 or E 3.7-3.8

April 4	More Dynamic Programming Examples	slides: 1 2 board: 1	slides: 1 2 board: 1	KT 6.8 or E 8.7

Apr 8	Network Flows	slides Knapsack DP Lec recording	slides Knapsack DP Lec recording	KT 7-7.3 or E 10-10.4

April 11	Ford-Fulkerson Algorithm, Recap	slides board	slides board	KT 7-7.3 or E 10-10.4

April 15	Midterm 2

Part 3:

Date	Lecture	Sec 1 Slides	Sec 2 Slides	Reading

April 18	Network Flows and Reductions	slides	slides	KT 7-7.3, 7.5-7.6 or E 10-10.4,11.1-11.4

April 22	Network Flow Reductions Continued	slides board: 1 2 3	slides board: 1 2 3	KT 8.1, 8.3 or E 12.1-12.3

April 25	P, NP, and NP Completeness	slides board	slides board	KT 8.1-8.4 or E 12.5-12.8

April 29	NP Hardness Reductions 1	slides	slides	KT 8.1-8.4 or E 12.5-12.8

May 2	NP Hardness Reductions 2	slides board: 1 2	slides board: 1 2	KT 8.1-8.5 or E 12.5-12.8

May 6	Approximation Algorithms	slides board	slides board	KT 11.1-11.2

May 9	Review