Honors Algorithms

G22.3520-001 Fall 2006

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