Instructor: Victor Shoup
Teaching Assistants: TBA
Mailing List
Lectures: Tue/Thur 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 scheduled for Tuesday, Dec. 20, 2-5pm, 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
Syllabus
Sep | 6 | Hashing, universal hashing | CLRS 11 |
8 | epsilon universal, uniform hashing | ||
13 | cuckoo hash | ||
15 | cuckoo hash, perfect hash, bloom filters | ||
20 | sorting: merge, heap, decision trees | CLRS 6, 8.1 | |
22 | quick sort, quick select, deterministic select | CLRS 7, 9 | |
27 | divide and conquer; bucket, radix, lex sort | CLRS 4, 8 | |
29 | 2-3 trees, search tries | ||
Oct | 4 | dynamic programming | CLRS 15 |
6 | greedy algorithms | CLRS 16 | |
11 | amortized algorithms | CLRS 17 | |
13 | binomial heaps | CLRS 19 | |
18 | fibonacci heaps | CLRS 20 | |
20 | union find | CLRS 21 | |
25 | graphs: BFS, DFS, Top sort | CLRS 22 | |
27 | strongly connected components | CLRS 22 | |
Nov | 1 | MSTs | CLRS 23 |
3 | shortest paths (1) | CLRS 24 | |
8 | shortest paths (2) | CLRS 25 | |
10 | max flow | CLRS 26 | |
15 | regular languages | Sipser 1 | |
17 | regular languages | ||
22 | context free languages | Sipser 2 | |
29 | context free languages | ||
Dec | 1 | TMs, P, NP | Sipser 3, 7 |
6 | NP | Sipser 7 | |
8 | NP | ||
13 | NP |