Lectures: Mon/Wed 3:30-4:45am, room 102 WWH
Mailing List
Instructor: Victor Shoup
Problem sessions: Thursday 3-4pm, Room 513 WWH (on weeks when homework is due)
Teaching Assistant: Kristiyan Haralambiev
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:
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
Lectures
Sep | 5 | Hashing, universal hashing | CLRS 11 |
10 | universal, pairwise indep. hashing | ||
12 | perfect hashing, uniform hash assumption, bloom filters | ||
17 | tries, 2-3 trees, ternary search trees | ||
19 | splitting and joining 2-3 trees, heaps, mergeable priority queues | ||
24 | sorting and selection | CLRS 6,7,9 | |
26 | more on sorting, divide and conquer | CLRS 4, 8 | |
Oct | 1 | dynamic programming | CLRS 15 |
3 | greedy algorithms | CLRS 16 | |
10 | amortized analysis | CLRS 17 | |
15 | binomial and fibonacci heaps | CLRS 19, 20 | |
17 | fibonacci heaps, union find | CLRS 20, 21 | |
22 | union find | CLRS 21 | |
24 | graphs: BFS, DFS, Top sort | CLRS 22 | |
29 | strongly connected components | CLRS 22 | |
31 | MSTs | CLRS 23 | |
Nov | 5 | shortest paths (1) | CLRS 24 |
7 | shortest paths (2) | CLRS 25 | |
12 | max flow | CLRS 26 | |
14 | max flow / NP | CLRS 34/Sipser 7 | |
19 | NP | CLRS 34/Sipser 7 | |
21 | NP | CLRS 34/Sipser 7 | |
26 | regular languages | Sipser 1 | |
28 | context free languages | Sipser 2 | |
Dec | 3 | context free languages | Sipser 2 |
5 | Decidability | Sipser 3, 4 | |
10 | Decidability | Sipser 5, 6 | |
12 | Review |