(email)(office hours)
Kent Quanrudkrq (at) purdue.eduTuesday and Thursday 4:15 - 5:15 PM
Himanshi Mehtamehta142 (at) purdue.eduWednesday 1:00 - 2:00 PM
Xiaowei Zhangzhan2597 (at) purdue.eduMonday 4:30 - 5:30 PM

Syllabus, policies, and other administrative things.


Similar courses elsewhere

Previous edition of this course.
Kent Quanrud, Spring 2020.

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).

Danny Sleator and Carl Kingsford (CMU).

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

Lecture notes will be provided. The following texts are also very helpful.

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: February 16 (multiple choice) and 18 (word problems)

Midterm 2: March 30 (multiple choice) and April 1 (word problems)

Final: Wednesday, May 5, from 3:30PM to 5:30PM (practice problems)


1/19Searching and sorting1/21The Secret Language of Numbers

Homework A

Handwritten notes (prepared, in class); 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"; Notes by Jeff on recurrences and on induction

Homework B

Handwritten notes (prepared, in class); Section 6.4 and 8.8 in KT; Section 3.8 in Jeff's notes

1/26Brute force over sequences1/28Searching and sorting graphs

Homework C

Handwritten notes (prepared, in class); Notes by Jeff; Sections 6.3 -- 6.5 in DPV; Chapter 6 in KT; Chapter 15 in CLRS; Lecture videos by Erik Demaine (1), (2), (3)

Homework D

Handwritten notes (prepared, in class); 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

2/2Brute force through graphs2/4Completely stuck

Homework E

Handwritten notes (prepared, in class); 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

Homework F

Handwritten notes (prepared, in class); Karp (1972); Wigderson (2009); 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; Chapter 12 of Jeff's notes; Video lecture by Erik Demaine; Turing award lecture by Stephen Cook

2/9Fast divide and conquer2/11Some lower bounds

Homework G

Handwritten notes (prepared, in class); Chapter 2 in DPV; Chapter 1 in Jeff's notes; Chapter 5 in KT

Homework H

Handwritten notes (prepared, in class); Williams (2005); Williams and Roddity (2013); Backurs and Indyk (2014); 2020 Course by Williams^2 at MIT; 2019 course by Bringmann and Künnemann at Max Planck Institute

2/16Midterm 1 (multiple choice)2/18Midterm 1 (word problems)
2/23Minimum spanning trees2/25Packing and covering paths

Homework I

Handwritten notes (prepared, in class); 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

Homework J

Handwritten notes (prepared, in class); Ford and Fulkerson (1956); 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; Section 7.3 in DPV; Chapter 7 in KT; Chapter 26 in CLRS

3/2Max flow and applications3/4Trees, flows, and cuts

Homework K

Handwritten notes (prepared, in class); Edmonds and Karp (1972); Chapter 11 in Jeff's notes; Video lectures by Tim Roughgarden on max flow, Edmonds-Karp, and applications of max flow

Homework L

Handwritten notes (prepared, in class); Nagamochi and Ibaraki (1992); Nagamochi and Ibaraki (1992)

3/9Matchings3/11Lazy data structures

Homework M

Handwritten notes (prepared, in class); Notes by Michel Goemans; Notes by Chandra Chekuri; Section 5.2 in Schrijver; Slides by Tarjan; "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

Homework N

Handwritten notes (prepared, in class); Notes by Jeff on amortized analysis; Sections 17.1 - 17.3 in CLRS; Video by Erik Demaine on amortized analysis; Tarjan (1985); Notes by Avrim Blum; Worksheet from CMU on amortized analysis; Notes and video by Srini on binary search trees

3/16Splay trees3/18Reading Day

Homework O

Handwritten notes (prepared, in class); 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; Turing award lecture by Robert Tarjan

3/23Link-cut trees3/25Dynamic Connectivity

Handwritten notes (prepared, in class); Video lecture and notes by Erik Demaine; Notes by Dan Sleator

Handwritten notes (prepared, in class); Notes and video lecture by Erik Demaine

3/30Midterm 2 (multiple choice)4/1Midterm 2 (word problems)
4/6Randomly searching and sorting4/8Heavy hitters

Homework P

Handwritten notes (prepared, in class); Notes by Avrim Blum; Notes on basic probability by Chandra Chekuri; Notes by Jeff; Chapter 13 in Kleinberg-Tardos; Karger (1993)

Homework Q

Handwritten notes (prepared, in class); Cormode and Muthukrishnan (2005); Notes from Fall '19 randomized algorithms class; Notes by Moses Charikar; Video lecture by Ankur Moitra; Video lecture by Jelani Nelson; Notes by Chandra Chekuri; Notes from Spring '20 algorithms class on universal hashing

4/13Reading Day4/15Linear probing

Homework R

Handwritten notes (prepared, in class); Knuth (1963); Pagh, Pagh, and Ruzic (2006); Notes by Mikkel Thorup; Video from Spring 2020; Video by Jelani

4/20Convex minimization4/22Greedy approximations

Homework S

Handwritten notes (prepared, in class); Sections 1.2 and 2.1 in Nesterov

Handwritten notes (prepared, in class); Nemhauser, Wolsey, Fisher (1978); Notes by Chandra Chekuri; Notes by Jan Vondrák; Video from Spring 2020; Notes from Spring 2020

4/27Randomized rounding4/29Random sums and graphs

Handwritten notes (prepared, in class); Raghavan, Thompson (1985); Video from Spring 2020 class on max-flow min-cut; Video from Spring 2020 class on set cover; Lecture notes by Chandra Chekuri; More notes by Chandra; Notes by Avrim Blum

Handwritten notes (prepared, in class); Erdős and Rényi (1960); Bollobas (1984); Karp (1990); Notes by Alistair Sinclair; Article by Joel Spencer; Chapter 7 of book by Bollobas