Fundamental Algorithms

Instructor. Moshe Lewenstein, WWW418, tel: 998-3118,


The solutions to the Sample Final can be taken from here --> Solutions to "Sample Final".

For those of you had a preliminary version, the current version is a final solution (not a solution to the final but a final solution to the sample final ;). Enjoy!
By the way, to solve the NP complete problem on the sample final, it helps to read the second NP complete problem from the handout.

For those of you don't have the questions to the final. Here they are ---> Questions of "Sample Final".


Class time.
Lecture: 7:00-9:00pm, Monday, room 101.
Problem session: 7:00-8:00pm, Wednesday, room 109, Warren Weaver Hall.
First meeting: Wednesday, January 19 (special one-time lecture, 7:00-9:00pm).
No class on Monday, January 24.

Office hours. Mon. 5:45-6:45pm, Wed. 5:45-6:45pm.

Teaching Assistants

Mailing list, home page. There is a class mailing list at g22_1170_001_sp00@cs; please join this list; it is intended for discussion of course related materials and announcements if there are any (to subscribe, send mail to Majordomo@cs.NYU.EDU with a body of SUBSCRIBE g22_1170_001_sp00). The course home page can be accessed from the department home page ( by following the links to course home pages and then to this course, or directly at

Syllabus. This course will study the fundamentals of data structure and algorithm design, including methods for determining the (asymptotic) running time of algorithms. The course outline along with associated reading from the text can be found here. Topics to covered are: Order of magnitude growth (e.g. O(n), O(n log n), O(n^2)), running time, recursion, solving recurrence equations, sorting, balanced trees, hashing, graph algorithms, divide and conquer, dynamic programming.

Assignments. There will be more or less weekly homeworks comprising problems drawn from the textbook and elsewhere. Late homeworks will not be accepted (except in the event of illness or other unavoidable circumstances). If for some reason you will be unable to hand in a homework on time, please discuss it with me beforehand.

Assessment. There will be a midterm, counting 0-25% toward the final grade. The final exam will comprise 50-75% of the course grade, depending on how the midterm is counted. If the grade for the final is better than the grade for the midterm, the final grade will be used instead of the midterm grades. Homework will count for 25%.

Required text. Siegel and Cole, An Inside guide to Algorithms. Photocopied Lecture Notes.
These are available, as of 1/17/00, for purchase at Unique Copy, 252 Greeene St; hours: 8am to 9pm, Mon-Fri, 10am-8pm, Sat, Closed Sun. Copies of transparencies used in the lectures will also be available for purchase at Unique; obtaining these is recommended.
Other texts which can be used as alternate texts and are on reserve in the library:
Aho, Hopcroft and Ullman. Data Structures and Algorithms.
Cormen, Leiserson, Rivest. Introduction to Algorithms.
Brassard and Bratley. Algorithmics, Theory and Practice. (Moshe Lewenstein)
Last modified: Jan 19, 2000