Instructor: Victor Shoup

• Phone: (212) 998-3511
• Office: 511 WWH
• email: shoup@cs.nyu.edu
• Office hours: Mon 5-6pm
• Problem review session: Fri 4-5pm (513 WWH)

Teaching Assistant: Abhijit Juria (office hours: 5-6pm Wed, 417 WWH)

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: 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:

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

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:

• 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.

Problem Sets

• Problem Set 1
• Problem Set 2
• Problem Set 3
• Problem Set 4
• Problem Set 5
• Problem Set 6
• Problem Set 7
• Supplemental Study Problems

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