Lect | Date | Topic | Reference |
1 | 08/25/15 | Introduction, history of algorithms, models of computation | [DPV:0] |
2 | 08/27/15 | Asymptotic Analysis, worst-case analysis, randomized algorithms | [DPV:0,KT:2] |
3 | 09/01/15 | Divide and conquer: sorting, closest pair, recurrence relations | [Ed:2, Er:1] |
4 | 09/03/15 | Divide and conquer: median selection, more on recurrences | [Ed:3,Er:1] |
5 | 09/08/15 | Graph representation, graph search | [DPV:3,Er:18] |
6 | 09/10/15 | Directed graphs, strongly connected components, topological sort | [DPV:3,Ed:13] |
7 | 09/15/15 | Shortest paths in graphs | [DPV:4,Ed:14] |
8 | 09/17/15 | Minimum spanning tree | [DPV:5] |
9 | 09/22/15 | Maintaining disjoint sets | [Er:17,Ed:16] |
10 | 09/24/15 | Amortized analysis | [Er:15,16] |
11 | 09/29/15 | Greedy techniques | [Ed:5,Er:7] |
12 | 10/01/15 | Dynamic programming | [DPV:6] |
13 | 10/06/15 | Dynamic programming | [DPV:6] |
10/08/15 | Midterm 1 (Lectures 1-13) | ||
14 | 10/15/15 | Shortest paths revisited | [DPV:6;KT6.8] |
15 | 10/20/15 | Convex hull | See Sakai Resources |
16 | 10/22/15 | Linear Programming | [MG:1,2;DPV:7] |
17 | 10/27/15 | LP: Simplex Algorithm | [MG:4,5] |
18 | 10/29/15 | LP: Duality | [MG:6,DPV:7] |
19 | 11/03/15 | Polynomial multiplication & FFT | [DPV:2.6,KT:5] |
20 | 11/05/15 | N-body problem | Sakai |
21 | 11/10/15 | Hashing | [Er:12] |
22 | 11/12/15 | Hashing, Bloom filters | [Er:12], Sakai |
23 | 11/17/15 | NP Completeness, Polynomial-Time Reduction | [DPV:8,Ed:23] |
24 | 11/19/15 | NP-Complete Problems | [DPV:8,Ed:24,Er:30] |
25 | 11/24/15 | NP-Complete Problems | [DPV:8,Er:30] |
12/01/15 | Midterm 2 (Lectures 14-25) | ||
26 | 12/03/15 | Approximation algorithms: Vertex cover, TSP, set cover | [DPV:9,Ed:25,Er:31] |
12/08/15 | Final Exam (All lectures) 07:00-10:00pm |