# G22.3520-001 Fall 2005

Instructor: Victor Shoup

• Phone: (212) 998-3511
• Office: 511 WWH
• email: shoup@cs.nyu.edu
• Office hours: Tue/Thu 5-6pm

Teaching Assistants: TBA

Mailing List

• It is important that you subscribe to the class mailing list, in order to receive announcements.
• To subscribe to the list, follow these instructions.

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:

• problem sets: 40%
• final exam: 60%

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:

• Recurrence equations and divide & conquer
• Linear time algorithms (radix sort, lexicographic sort, selection)
• Hashing
• Balanced trees and their augmentation
• Amortized analysis (splay trees, Fibonnacci heaps, Union-Find)
• Algorithms on graphs (DFS, path problems, MST; using reductions for algorithm design)
• Dynamic programming
• Randomization
• NP-completeness
• Automata theory
• Halting problem

Texts:

• Introduction to Algorithms (Second Edition), by Cormen, Leiserson, Rivest, and Stein.
• Introduction to the Theory of Computation (Second Edition), by Michael Sipser.

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