Lect | Date | Topic | Reference |
1 |
01/12 |
Introduction, history of algorithms, models of computation |
[DPV:0] |
2 |
01/17 |
Asymptotic Analysis, worst-case and average-case analysis, randomized algorithms |
[DPV:0][KT:2] |
3 |
01/19 |
Divide and conquer: sorting, polynomial multiplication, recurrence relations |
[DPV:2][KT:5][Ed:2] |
4 |
01/24 |
Divide and conquer: median selection, more on recurrences (Assignment 1) |
[DPV:2][KT:5][Ed:3] |
5 |
01/26 |
Graph representation, graph search |
[DPV:3][KT:3][Ed:13] |
6 |
01/31 |
Directed graphs, strongly connected components, topological sort |
[DPV:3][KT:3][Ed:13] |
7 |
02/02 |
Shortest paths in graphs (Assignment 1 due) |
[DPV:4][KT:6.8][Ed:14] |
8 |
02/07 |
Binary search trees, red-black trees (Assignment 2) |
[Ed:7] |
9 |
02/09 |
I/O-efficiency and B-trees |
slides |
notes |
10 |
02/14 |
Skip list |
Notes |
11 |
02/16 |
Amortized analysis (Assignment 2 due) |
[Er:14,15] |
12 |
02/21 |
Maintaining disjoint sets (Assignment 3) |
[Er:16; Ed:16] |
13 |
02/23 |
Greedy techniques |
[Ed:5; Er:7] |
|
02/28 |
Exam 1 (Lectures 1-12) |
|
14 |
03/01 |
Dynamic programming (Assignment 3 due) |
[DPV:6] |
15 |
03/13 |
Dynamic programming |
[DPV:6] |
16 |
03/15 |
Minimum spanning tree |
[DPV:5] |
17 |
03/20 |
Shortest paths revisited (Assignment 4) |
[DPV:4.6][CLRS:23,24] |
18 |
03/22 |
Linear Programming |
[DPV:7] |
19 |
03/27 |
Simple Algorithm and Linear Programming |
[DPV:7.5,7.6], [CLRS:29] |
20 |
03/29 |
Polynomial multiplication & FFT (Assignment 4 due) |
[DPV:2.6],[KT:5.6] |
21 |
04/03 |
Cryptography & RSA (Assignment 5) |
[CLRS:31.7] |
22 |
04/05 |
Hashing |
[Er:12] |
23 |
04/10 |
NP Completeness: Definition of NP, 3SAT |
[DPV:8,Ed:23] |
24 |
04/12 |
Reduction between NP-Complete Problems (Assignment 5 due) |
[DPV:8,Ed:24] |
|
04/17 |
Exam 2 (Lectures 13-24) (Assignment 6) |
|
25 |
04/19 |
Examples of NP-Complete Problems |
[DPV:9,Ed:25] |
26 |
04/24 |
Approximation algorithms: TSP, set cover |
[DPV:9,Ed:25] |
|
04/26 |
Assignment 6 due |
|
|
04/30 |
Final Exam (All lectures) 7:00-10:00pm |
|