Honors Algorithms

G22.3520-001 Fall 2005

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

  1. Problem Set 1, Due Sept. 27
  2. Problem Set 2, Due Oct. 11
  3. Problem Set 3, Due Oct. 25
  4. Problem Set 4, Due Nov. 8
  5. Problem Set 5, Due Nov. 22
  6. Problem Set 6, Due Dec. 6
  7. Problem Set 7, Not to hand in

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