(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 (*)

(*) Feb 22 office hours moved to Feb 29, 5:30 - 6: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: TBD (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