Tuesdays and Thursdays, 3:00PM to 4:15 PM
Lectures and office hours are on Zoom at purdue-edu.zoom.us/j/93829189665
|Kent Quanrud||Tuesday and Thursday 4:15 - 5:15 PM|
|Himanshi Mehta||Wednesday 1:00 - 2:00 PM|
|Xiaowei Zhang||Monday 4:30 - 5:30 PM*|
* Moved to 2:30 - 3:30 PM on Monday, April 19
Syllabus, policies, and other administrative things.
Previous edition of this course.
Kent Quanrud, Spring 2020.
Algorithm design, analysis, and implementation.
Algorithm design, analysis, and implementation.
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).
Jelani Nelson (Harvard).
Danny Sleator and Carl Kingsford (CMU).
Avrim Blum and Anupam Gupta (CMU).
Chandra Chekuri (UIUC).
David Karger and Aleksander Madry (MIT).
A course in combinatorial optimization.
Alexander Schrijver (CWI).
Ankur Moitra (MIT).
Advanced algorithm design.
Sanjeev Arora (Princeton).
A second course in algorithms.
Tim Roughgarden (Stanford).
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")
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/19||Searching and sorting||1/21||The Secret Language of Numbers|
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
|1/26||Brute force over sequences||1/28||Searching and sorting graphs|
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/2||Brute force through graphs||2/4||Completely stuck|
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
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/9||Fast divide and conquer||2/11||Some lower bounds|
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/16||Midterm 1 (multiple choice)||2/18||Midterm 1 (word problems)|
|2/23||Minimum spanning trees||2/25||Packing and covering paths|
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
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/2||Max flow and applications||3/4||Trees, flows, and cuts|
|3/9||Matchings||3/11||Lazy data structures|
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
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/16||Splay trees||3/18||Reading Day|
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/23||Link-cut trees||3/25||Dynamic Connectivity|
|3/30||Midterm 2 (multiple choice)||4/1||Midterm 2 (word problems)|
|4/6||Randomly searching and sorting||4/8||Heavy hitters|
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/13||Reading Day||4/15||Linear probing|