Room WWH 101
Professor Ernest Davis
- phone: (212) 998-3123
- office: 329 Warren Weaver Hall
- Office hours: Tuesday 10-12 or by appointment.
The recitation will meet Thursday, 6:00-7:00, WWH 101. Attendance at the
recitation is strongly recommended. In any case, be sure that you
register for the recitation (section 002) as well as the class
The recitation instructor and grader for the course is Zi Wang
. Zi Wang will hold office hours Thursday 5-6 in WWH 412.
An Introduction to Algorithms: Their Methods and Madness, by Alan
Siegel. This is available at the NYU Copy Center, La Guardia Place between
3rd and Bleecker, next to the Citibank.
- Algorithmic analysis:
Correctness. Worst-case running time asymptotic
analysis. Big Oh notation.
Siegel, chap. 1,
chap. 2 through 2.7, chap 3 through section 3.3.1. Cormen, Leierson, Rivest,
and Stein chaps 1-3
- Sorting algorithms:
N2 sorts, Heapsort, Mergesort, Quicksort,
Radix sort. Lower bound. Siegel, chap. 5 through
5.4, section 5.6 through 5.6.3. CLRS chaps 6-8.
- Sets: Lists. Hash tables. Binary trees. B-trees.
Siegel, chap. 6 through 6.4.5. CLRS chaps 10-12, 18.
- Directed graphs: Implementation. Depth-first search. DAGS.
Siegel, chap 7, chap 8
through section 8.3. CLRS 22, 24, 25.
- Undirected graphs: Minimum spanning tree. Union-find algorithm.
Siegel, sections 8.5, 9.4. CLRS chaps 21, 23
- Algorithmic techniques: Dynamic programming.
Siegel, section 11.3, 11.4. CLRS chaps. 15, 16
- Computation theory Undecidable problems. NP-complete problems.
Weekly problem sets (50%)
Final exam (50%).
Problem sets should be submitted in hard copy in class or uploaded to the NYU
Classes site in either Word, PDF, or plain text. Do not write your
solutions by hand, scan them, and upload the image.
Problem sets are due at the beginning of class each Wednesday. They will be
accepted up to 8 days late, at the start of recitation the Thursday
of the following week, with
a penalty of 1 point out of 10.
Class email list
You should be automatically subscribed to
the class email web page.
Problem Set 1 Due June 3
Problem Set 2 Due June 10
Problem Set 3 Due June 17
Problem Set 4 Due June 24
Problem Set 5 Due July 1
Problem Set 6 Due July 8
Problem Set 7 Due July 15
Problem Set 8 Due July 22
Problem Set 9 Due July 29
Linear Time Sorts
Binary Search Trees
Using Hashing for Large Sets of Large Objects
Notes on Scheduling
The final exam will be Wednesday August 12.
Notes on the Final Exam
Sample Final Exam (actually the exam from 2013)
Additional practice problems can be found in the department's
collection of Core Exams
You may discuss any of the assignments with your classmates (or anyone else)
but all work for all assignments must be
entirely your own. Any sharing or copying of assignments will be
considered cheating. By the rules of the Graduate School of Arts and Science,
I am required to report any incidents of cheating to the department.
My policy is that, in any incident of cheating, I recommend a grade of F
to the department.
By GSAS rules a second incident of cheating results
in expulsion from the University.