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.eduWednesdays 11:45 - 1:15 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).

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

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)


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