Lectures: Mon/Wed 3:30-4:45am, room 102 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.

Instructor: Victor Shoup

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

Problem sessions: Thursday 3-4pm, Room 513 WWH (on weeks when homework is due)

Teaching Assistant: Kristiyan Haralambiev

• Office hours: Wed 5-6pm

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%

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

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