Staff

Kent Quanrudkrq (at) purdue.eduFridays 1:30 - 2:30 PM at LWSN 1211
Shubhang M. Kulkarnikulkar17 (at) purdue.eduThursdays 1:30 - 3:00 at HAAS G72
Tuan M. Lailai123 (at) purdue.eduWednesdays 2:45 - 4:15 PM at HAAS G050
Xiaowei Zhangzhan2597 (at) purdue.eduTuesday 5:00 - 6:30 PM at HAAS G050

Syllabus, policies, and other administrative things.

Similar courses elsewhere

Algorithm design, analysis, and implementation.
Jeremiah Blocki.

Algorithm design, analysis, and implementation.
Elena Grigorescu.

Introduction to algorithms.
Srini Devadas and Erik Demaine (MIT).

Algorithms and models of computation.
Jeff Erickson (UIUC).

Efficient algorithms and intractable problems.
Prasad Raghavendra and Satish Rao (Berkeley).

Advanced Algorithms.
Jelani Nelson (Harvard).

Algorithms.
Danny Sleator and Carl Kingsford (CMU).

Algorithms.
Avrim Blum and Anupam Gupta (CMU).

Fundamental algorithms.
Chandra Chekuri (UIUC).

Advanced algorithms.
David Karger and Aleksander Madry (MIT).

A course in combinatorial optimization.
Alexander Schrijver (CWI).

Advanced algorithms.
Ankur Moitra (MIT).

Advanced algorithm design.
Sanjeev Arora (Princeton).

A second course in algorithms.
Tim Roughgarden (Stanford).

Recommended texts

Algorithms, by Erickson ("Jeff's notes")

Algorithm design, by Kleinberg and Tardos ("KT")

Algorithms, by Dasgupta, Papadimitriou, and Vazirani ("DPV")

Introduction to algorithms, by Cormen, Leiserson, Rivest, and Stein ("CLRS")

Key dates

Midterm 1: Wednesday, February 12, 8:00 - 10:00 PM, MATH 175 (practice problems)

Midterm 2: Tuesday, March 10, 8:00 - 10:00 PM, MATH 175 (practice problems)

Final: Friday, May 8, originally scheduled from 8:00 AM to 10:00 AM and now remote (practice problems)

Calendar

TuesdayThursday
1/14Mergesort1/16Quicksort and heapsort

Homework 1

Section 1.4, 1.7 in Jeff's notes; Section 2.3 in DPV; Video lecture by Srini Devadas on merge sort; Section 5.1 - 5.2 in KT; Video by Jeff on merge sort (starting 30:12); Chapter 2 in Blum^2; Sections 2.3, 4.4 in CLRS; Turing award lecture by Donald Knuth on "Computer programming as an Art"

Homework 2

Video lectures by Srini Devadas on heap sort and on quick sort (starting 49:20); Chapters 6 and 7 in CLRS; Sections 2.1 - 2.2 in KT; Chapter 3 in Blum^2; Section 1.5 in Jeff's notes

1/21Amortized analysis, splay trees, tree sort1/23Searching and sorting graphs - DFS, strongly connected components, and topological sort

Homework 3

Turing award lecture by Robert Tarjan; Notes by Jeff on amortized analysis; Sections 17.1 - 17.3 in CLRS; Video by Erik Demaine on amortized analysis; Notes and video by Srini on binary search trees; Notes by Avrim Blum; Worksheet from CMU on amortized analysis; splay tree demo by Daniel Sleator; notes by Daniel Sleator; notes by Michel Goemans; notes by Jeff on splay trees; notes by Bob Tarjan; notes and video lecture by David Karger on splay trees; Video lecture by Jelani Nelson on splay trees

Homework 4

Chapters 5 and 6 of Jeff's notes; Video lecture by Erik Demaine on DFS and topological sort (and notes); Chapter 3 in DPV; Chapter 22 in CLRS; Sections 3.1 to 3.3, 3.5 to 3.6 in KT

1/28Shortest paths1/30Caching shortest paths

Homework 5

Chapter 8 in Jeff's notes; Video lecture by Erik on BFS (and notes), then by Srini first introducing the (weighted) shortest path problem and then on Dijsktra's algorithm; Chapter 4 in DPV; Sections 24.3 - 24.5 in CLRS; Turing award lecture by Edsger Dijkstra

Homework 6

Video lecture by Erik (and notes); Chapter 9 in Jeff's notes; Chapter 6 in DPV; Sections 1.1 - 1.3 in Schrijver's text; Sections 6.8 to 6.10 in KT; Chapter 24 of CLRS; Notes by Avrim Blum

2/4Caching everything2/6Caching on graphs

Homework 7

Notes by Jeff; Chapter 6 in DPV; Chapter 6 in KT; Chapter 15 in CLRS; Lecture videos by Erik Demaine (1), (2), (3)

2/11Disjoint union2/13Minimum spanning trees

Notes by Jeff; Chapter 21 in CLRS; Section 5.1.4 in DPV; Section 4.6 in KT; Tarjan (1975); Sharir and Seidel (2006)

Homework 8

Notes by Jeff; Video lecture by Erik Demaine; Section 5.1 in DPV; Section 1.4 in Schrijver's text; Section 4.5 in KT; Chapter 23 in CLRS; See Chapter 10 in Schrijver for more on matroids

2/18Packing and covering paths2/20Flows

Homework 9

Chapter 4 in Schrijver; Notes from MIT; Chapter 10 of Jeff's notes; Video lecture by Srini; Video lecture by Ankur Moitra; Sections 26.1 to 26.2 in CLRS; Sections 7.1, 7.2, 7.6 in KT; Section 7.2 in DPV; Ford and Fulkerson (1956)

Homework 10

Chapter 11 in Jeff's notes and Chapter G in Jeff's notes; Section 7.3 in DPV; Chapter 7 in KT; Chapter 26 in CLRS; Edmonds, Karp (1972); Video lectures by Tim Roughgarden on max flow, Edmonds-Karp, and applications of max flow

2/25All pairs min cuts2/27How to show that a problem is probably hard

Homework 11

Gomory, Hu (1961); Notes by Chandra Chekuri; Notes by Richard Peng; Wikipedia

Homework 12

Karp (1972); Wikipedia; Chapter 12 of Jeff's notes; Section 8.1 in DPV; Chapter 8 in KT; Chapter 34 in CLRS; Worksheet from CMU; Chapter 6 in Schrijver; Video lecture by Erik; Turing award lecture by Richard Karp; Biographical interview of Karp

3/3Cook-Levin theorem3/5Packing and covering edges

Chapter 12 of Jeff's notes; Video lecture by Erik Demaine; Section 8.4 in KT; Section 34.3 in CLRS; Turing award lecture by Stephen Cook

Notes by Michel Goemans; Notes by Chandra Chekuri; Chapter 5 in Schrijver; "A glimpse of heaven" by Jack Edmonds; 2015 OPTIMA issue celebrating the 50th anniversary of Edmonds' blossom algorithm, including an interview of Edmonds; Historical survey on combinatorial optimization by Schrijver

3/10No class3/12No class
3/24Organizing random data3/26(Sort of) randomly organizing data


Homework 13

Video lecture by Erik Demaine; Chapter 10 in Blum^2; Notes by Sanjeev Arora



Homework 14

Video lecture by Erik; Chapter 10 in Blum^2; Notes by Sanjeev Arora; Notes by Mikkel Thorup; Section 1.5 in DPV; Notes by Jeff

3/31Linear probing4/2Heavy hitters


Homework 15

Knuth (1963); Pagh, Pagh, and Ruzic (2006); Notes by Mikkel Thorup; Video by Jelani



Homework 16

Notes from Fall '19 randomized algorithms class; Notes by Moses Charikar; Video lecture by Ankur; Video lecture by Jelani; Notes by Chandra Chekuri

4/7Linear programming and approximating set cover4/9LP duality and line embeddings


Homework 17

Notes by Anupam Gupta; Slides by Chandra Chekuri; Original paper by Raghavan and Thompson; Technical report by Raghavan and Thompson



Notes by David Karger; Notes by Shayan Oveis Gharan

4/14Greedy approximations4/16Competitive analysis for caching


Homework 18

Nemhauser, Wolsey, Fisher (1978); Notes by Chandra Chekuri; Notes by Jan Vondrák



Homework 19

Sleator and Tarjan (1985); Notes by Avrim Blum; Notes by Jelani; Talk by Jeff Dean where he discusses the importance of caching among other aspects of building large systems

4/21Randomized caching4/23Buy or rent


Fiat, Karp, Luby, McGeoch, Sleater, and Young (1991); Notes by Shuchi Chawla; Video lecture by Jelani Nelson



Homework 20

Karlin, Manasse, McGeoch, Owicki (1994); Notes by Danny Sleator; Notes by Shuchi Chawla; Notes by Jelani

4/28Review4/30Review