Fundamental Algorithms

Instructor. Richard Cole, WWW412, tel: 998-3119,

Class time.
Lecture: 5:00-7:00pm, Monday, room 109, Warren Weaver Hall.
Problem session: 5:45-6:45, Wednesday, room 109, Warren Weaver Hall.
First meeting: Monday, September 8.

Office hours. Mon. 3:45-4:45pm, Wed. 4:30-5:30pm, and by appointment.

Teaching Assistants
Xiaoge Zhang (; office hour 7-8pm 524 , Monday, 524 Warren Weaver Hall.
Tao Zhao (; office hour 4:30-5:30pm, Wednesday, 417 Warren Weaver Hall.
If you have questions regarding grading of the homeworks, please consult the teaching assistants first. Xiaoge is grading odd numbered homeworks, Tao even numbered ones.

Mailing list, home page. There is a class mailing list at g22_1170_001_fl97@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_fl97). 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. A detailed syllabus can be found here. Topics to covered are: Order of magnitude growth (e.g. O(n), O(n log n), O(n^2)), solving recurrence equations, sorting, balanced trees, 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 one or more midterms, counting 0-25% toward the final grade. The final exam will comprise 50-75% of the course grade, depending on how the midterms are counted. If the grade for the final is better than the grade for the midterms, the final grade will be used instead of the midterm grade. Homework will count for 25%.

Required text. Siegel and Cole, An Inside guide to Algorithms. Photocopied Lecture Notes.
These are available, as of 9/2/97, for purchase at Unique Copy, 252 Greeene St; hours: 8am to 9pm, Mon-Fri, 10am-8pm, Sat, Closed Sun.
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.

Course Outline

Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Homework 11
Homework 12
Homework 13 (Richard Cole)
Last modified: Nov 25, 1997