Basic Algorithms
Spring 2016 —
CSCIUA.0310003
Lectures: Mon/Wed 2:003:15pm, room 101 WWH
Recitation: Mon 12:301:45pm, room 109 WWH
Midterm exam: Wed, March 23
Mailing List

It is important that you subscribe to the class mailing list,
in order to receive announcements.

You may already be subscribed, but if not, follow
these instructions.
Instructor: Victor Shoup

Office: 418 WWH

email: shoup@cs.nyu.edu

Office hours: Tuesdays, 11am12noon, and by appointment
Recitation Leader:
Abhinav Tamaskar <avt237@nyu.edu>
Grading:
There will be a problem set roughly once every two weeks.
There will be a midterm exam and a final exam.
Final grades will be weighted as follows:

problem sets: 40%

midterm exam: 25%

final exam: 35%
Text:

Introduction to Algorithms (Third Edition),
by Cormen, Leiserson, Rivest, and Stein.
Topics:
 Recurrence equations and divide & conquer
 Sorting and Searching
 Probabilistic algorithms
 Hashing
 Balanced trees
 Graph algorithms (DFS, path problems, MST; using reductions
for algorithm design)
 Dynamic programming
 NPcompleteness
Slides and notes:

merge sort

Code: sorting.c

divide and conquer

polynomials and the FFT

division

23 trees

priority queues

dynamic programming

greedy algorithms

amortized analysis

graphs

graphs (SCCs)

graphs (shortest paths)

Demo: BellmanFord

Demo: Acyclic

Demo: Dijkstra

graphs (all pairs shortest paths)

graphs (MST)

Demo: Prim

Notes: Probability Primer

probability

selection

Quick Sort

Hashing (1)

Hashing (2)

Hashing (3)

Hashing (4): cuckoo hashing

NP completeness (1)

NP completeness (2)

NP completeness (3)

NP completeness (4)
Problem Sets:
 Problem Set 1 (due Feb. 8)
 Problem Set 2 (due Feb. 17)
 Problem Set 3 (due Feb. 29)
 Problem Set 4 (due Mar. 9)
 Problem Set 5 (due Mar. 30)
 Problem Set 6 (due April 6)
 Problem Set 7 (due April 20)
 Problem Set 8 (due May 2)
 Problem Set 9 (due May 9)