Honors Algorithms

G22.3520-001 Fall 2007

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:

The final exam is Monday, December 17, 11:00am-2:00pm, WWH 1302

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