The schedule includes required readings for each lecture under References. Sections that are expected to be read before lecture are listed under Pre-reading. Additional optional readings are also provided under Extra for those interested.
Full citations and links for the references are found on the Reading page. Lecture notes are on Sakai.
| Lect | Date | Topic | References | Pre-reading | Extra |
| 1 |
08/24 |
Introduction |
[Er Ch0] |
|
|
| | Ranking | | | |
| 2 |
08/26 |
Sorting, divide & conquer
|
[Er Ch1.4-1.6, Ed Sec2] |
[Er Ch0-1] |
[AV] |
| 3 |
08/31 |
Order statistics
|
[Er Ch1.8, MR Ch3.1-3.3] |
[MR Ch3.1-3.2] |
[MP, GK] |
| 4 |
09/02 |
Rank aggregation, fair ranking
|
Notes |
|
[DKNS, BCELP Ch2&4] |
| | Graphs: Shortest Paths | | | |
| 5 |
09/07 |
Graph representations, shortest path metric, BFS
|
[Er Ch5-6, DVP Ch4] |
[Er Ch5] |
|
| 6 |
09/09 |
Dijkstra's algorithm
|
[Er Ch8] |
|
[NBK] |
| 7 |
09/14 |
All pairs shortest paths
|
[Er Ch9] |
[Er Ch3&6] |
[ADFGW] |
| 8 |
09/16 |
Graph similarity: LCS, edit distance
|
[Er Ch3] |
[Er Ch3] |
[SM Ch3] |
| | Clustering | | | |
| 9 |
09/21 |
Hierarchical clustering
|
[Er Ch7.5, MRS Ch17] |
|
[XT] |
| 10 |
09/23 |
Centered clustering, greedy & k-means algorithm
|
[MRS Ch16] |
|
[JMF] |
| | Graphs: Flows, cuts, matchings | | | |
| 11 |
09/28 |
Maximum flows and minimum cuts, bipartite matchings
|
[Er Ch10.1-10.3] |
|
[KT Ch7] |
| 12 |
09/30 |
Flow algorithms
|
[Er Ch10.4-10.7] |
|
[KT Ch7] |
| Exam |
10/07 |
Midterm |
Lects 1-12 |
|
|
| 13 |
10/12 |
Project 1 presentations |
|
|
|
| 14 |
10/14 |
Matching algorithms |
[Er Ch11, Kl] |
|
[St] |
| 15 |
10/19 |
Online matching & adwords |
[Er Ch4.5, MSVV] |
|
|
| | Optimization | | | |
| 16 |
10/21 |
Linear and integer programming
|
[Er2 Ch H, Kl] |
|
[Go] |
| 17 |
10/26 |
Duality
|
[Er2 Ch H-I] |
|
|
| 18 |
10/28 |
LP algorithms
|
[La, WS Ch4-5, Go2, Te] |
|
|
| 19 |
11/02 |
Beyond LP
|
[Ka, Gr] |
|
|
| | Clustering, revisited | | | |
| 20 |
11/04 |
LP rounding, local search
|
[WS Ch5, Bh] |
|
[Na] |
| 21 |
11/09 |
Spectral clustering
|
[VL] |
|
[Sp] |
| | Hashing | | | |
| 22 |
11/11 |
Universal hashing
|
[Er2 5, lecture notes] |
|
|
| 23 |
11/16 |
Bloom filters, consistent hashing
|
[Er2 6, BM, MS, RV, CM] |
|
|
| 24 |
11/18 |
Locality sensitive hashing
|
[HP Ch9, AI, GIM] |
|
|
| 25 |
11/23 |
Project 2 presentations
|
[Ma Ch15] |
|
|
| Exam |
12/10 |
Final (9:00am-12:00pm) |
Lects 1-24 |
|
|