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:

• A Computational Introduction to Number Theory and Algebra, by Shoup. Chapter 6 contains useful background on probabilty theory. Chapters 1 and 2 reviews some basics abount numbers and congruences.
• Cuckoo Hashing, by Pagh and Rodler (Journal of Algorithms, 51(2), 2004).

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