Instructor: Victor Shoup
Teaching Assistant: Abhijit Juria (office hours: 5-6pm Wed, 417 WWH)
Mailing List
Lectures: Mon/Wed 3:30-4:45am, room 101 WWH
Grading: There will be a problem set roughly once every two weeks. There will be a final exam, which also serves as the departmental PhD qualifier in this area. Grades will be determined as follows:
The final exam is Monday, December 18, 1:30-4:30pm, WWH 101
Course description: This course is intended to cover the topics needed for the departmental comprehensive exam in Algorithms, which also includes elements of the theory of computation. The goal of the course, in addition to covering the topics listed below, is to improve your algorithmic problem solving skills.
Topics:
Texts:
Online resources:
Problem Sets
Tentative syllabus
Sep | 6 | Hashing, universal hashing | CLRS 11 |
11 | universal, pairwise indep. hashing perfect hashing | ||
13 | perfect hashing, uniform hash assumption, bloom filters | ||
18 | tries, 2-3 trees, ternary search trees | ||
20 | splitting and joining 2-3 trees, heaps, mergeable priority queues | ||
25 | sorting and selection | CLRS 6,7,9 | |
27 | more on sorting, divide and conquer | CLRS 4, 8 | |
Oct | 2 | dynamic programming | CLRS 15 |
4 | greedy algorithms | CLRS 16 | |
11 | amortized analysis | CLRS 17 | |
16 | binomial and fibonacci heaps | CLRS 19, 20 | |
18 | fibonacci heaps, union find | CLRS 20, 21 | |
23 | union find | CLRS 21 | |
25 | graphs: BFS, DFS, Top sort | CLRS 22 | |
30 | strongly connected components | CLRS 22 | |
Nov | 1 | MSTs | CLRS 23 |
6 | shortest paths (1) | CLRS 24 | |
8 | shortest paths (2) | CLRS 25 | |
13 | max flow | CLRS 26 | |
15 | max flow / NP | CLRS 34/Sipser 7 | |
20 | NP | CLRS 34/Sipser 7 | |
22 | NP | CLRS 34/Sipser 7 | |
27 | regular languages | Sipser 1 | |
29 | context free languages | Sipser 2 | |
Dec | 4 | context free languages | Sipser 2 |
6 | Decidability | Sipser 3, 4 | |
11 | Decidability | Sipser 5, 6 | |
13 | Review |