Design & Analysis of Algorithms — COMPSCI 330 and COMPSCI 590 — Spring 2013
Lect | Date | Topic | Reference |
1 | 01/10 | Introduction, history of algorithms, models of computation | [DPV:0] |
2 | 01/15 | Asymptotic Analysis, worst-case and average-case analysis, randomized algorithms | [DPV:0][KT:2] |
3 | 01/17 | Divide and conquer: sorting, polynomial multiplication, recurrence relations | [Ed:2][Er:1][DPV:2] |
4 | 01/22 | Divide and conquer: median selection, more on recurrences (Assignment 1) | [Ed:3][Er:1][DPV:2] |
5 | 01/24 | Graph representation, graph search | [DPV:3][Ed:13][Er:17] |
6 | 01/29 | Directed graphs, strongly connected components, topological sort | [DPV:3][KT:3][Ed:13] |
7 | 01/31 | Shortest paths in graphs (Assignment 1 due) | [DPV:4][KT:6.8][Ed:14] |
8 | 02/05 | Binary search trees, red-black trees (Assignment 2) | [Ed:7] |
9 | 02/17 | Skip list | [Er:10.2],Notes |
10 | 02/12 | Amortized analysis | [Er:14,15] |
11 | 02/14 | Maintaining disjoint sets (Assignment 2 due) | [Er:16; Ed:16] |
12 | 02/19 | Greedy techniques (Assignment 3) | [Ed:5; Er:7] |
13 | 02/21 | Minimum spanning tree | [DPV:5] |
02/26 | Exam 1 (Lectures 1-12) | ||
14 | 02/28 | Dynamic programming | [DPV:6] |
15 | 03/05 | Dynamic programming (Assignment 3 due) |
[DPV:6] |
16 | 03/07 | Shortest paths revisited (Assignment 4) |
[DPV:4.6][CLRS:23,24] |
17 | 03/19 | Linear Programming | [DPV:7] |
18 | 03/21 | LP: Simplex Algorithm | [MG:4,5], [CLRS:29] |
19 | 03/26 | LP: Duality (Assignment 4 due) | [DPV:7], [MG:6] |
20 | 03/28 | Polynomial multiplication & FFT (Assignment 5) | [DPV:2.6],[KT:5.6] |
21 | 04/02 | FFT Applications | [KT:5.6] |
22 | 04/04 | Hashing | [Er:12] |
23 | 04/09 | NP Completeness, Polynomial-Time Reduction (Assignment 5 due) | [DPV:8,Ed:23] |
24 | 04/11 | NP-Complete Problems (Assignment 6) |
[DPV:8,Ed:24] |
04/16 | Exam 2 (Lectures 13-24) | ||
25 | 04/18 | NP-Completeness & Beyond | [DPV:9,Ed:25] |
26 | 04/23 | Approximation algorithms: TSP, set cover | [DPV:9,Ed:25] |
04/25 | Assignment 6 due | ||
04/29 | Final Exam (All lectures) 09:00am-noon |