Fundamental Algorithms

CSCI-GA 1170
Wednesday 6:00-8:20
Room WWH 101
Professor Ernest Davis

Reaching Me

phone: (212) 998-3123
office: 329 Warren Weaver Hall
Office hours: Tuesday 10-12 or by appointment.
Email:

Recitation

The recitation will meet Tuesday, 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 (section 001).

Prerequisites: None.

Required Textbook: Either of the following: An Introduction to Algorithms: Their Methods and Madness, by Alan Siegel. The book is available at the NYU Copy Center (LaGuardia Place between Bleecker and 3rd, next to Citibank) for about $55.00. It comes in two volumes; be sure to get both. It will be available starting the morning of Wednesday, May 28.

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd edn. Available at the book store. (Previous editions are also fine, if you can get them used cheap.)

Topics

Algorithmic analysis: Correctness. Worst-case running time asymptotic analysis. Big Oh notation. CLRS, chaps. 1-3. Siegel, chap. 1, chap. 2 through 2.7, chap 3 through section 3.3.1
Divide-and-conquer Recurrence equations. CLRS chap. 4. Siegel section 3.3.2 through p. 133, 3.3.3, and 3.3.4 through p. 145.
Sorting algorithms: N² sorts, Heapsort, Mergesort, Quicksort, Radix sort. Lower bound. CLRS chaps. 6-8. Siegel, chap. 5 through 5.4, section 5.6 through 5.6.3.
Sets: Lists. Hash tables. Binary trees. B-trees. CLRS chap. 10, 11, 12, 18. Siegel, chap. 6 through 6.4.5.
Directed graphs: Implementation. Depth-first search. DAGS. Shortest paths. CLRS chaps. 22,24,25. Siegel, chap 7, chap 8 through section 8.3.
Undirected graphs: Minimum spanning tree. Union-find algorithm. CLRS chaps. 21, 23. Siegel, sections 8.5, 9.4
Algorithmic techniques: Dynamic programming. Greedy algorithms. CLRS, Chaps. 15, 16. Siegel, section 11.3, 11.4.
State space search/Implicit graphs: . Iterative deepening. Class notes.

Requirements

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 6 days late, at the start of recitation the following Tuesday, with a penalty of 1 point out of 10.

Class email list

You should be automatically subscribed to the class email web page.

Assignments

Problem Set 1 Due June 4.
Problem Set 2 Due June 11.
Problem Set 3 Due June 18.
Problem Set 4 Due June 25.
Problem Set 5 Due July 2.
Problem Set 6 Due July 9.
Problem Set 7 Due July 16.
Problem Set 8 Due July 23.
Problem Set 9 Due July 30.

Notes

HeapSort MergeSort QuickSort Linear Time Sorts
Binary Search Trees 2-3 Trees B-Trees
Using Hashing for Large Sets of Large Objects
Notes on Scheduling

Final exam

The final exam will be Wednesday August 13.

Notes on the Final Exam
Sample Final Exam
Additional practice problems can be found in the department's collection of Core Exams
Solutions to Sample Final Exam

Cheating

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.