Lecture Schedule

LectDateTopicReference
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

page top