Fundamental Algorithms
CSCI-GA 1170
Monday 7:00-9:00
Room WWH 101
Professor Ernest Davis
Reaching Me
- phone: (212) 998-3123
- office: 329 Warren Weaver Hall
- Office hours: Tuesday 10-12, Thursday 3-4.
- Email:
Recitation
The recitation will meet Wednesday, 6:00-7:00, WWH 109. Attendance at the
recitation is strongly recommended. In any case, be sure that you
register for the recitation (section 004) as well as the class
(section 003). The recitation instructor is Rameez Loladia.
Rameez holds office hours Wednesday, 5-6 in WWH 303.
Prerequisites: None.
Required Textbook:
Either of the following:
An Introduction to Algorithms: Their Methods and Madness by Alan
Siegel, available at the copy shop at 11 Waverley Place.
or
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein,
3rd edn. (Previous editions are also fine, if you can get them used
cheap.) Available at the NYU Bookstore.
Topics
- Algorithmic analysis:
Correctness. Worst-case running time asymptotic
analysis. Big Oh notation. CLRS, chaps. 1-3. Siegel, chap. 1,
chaps 2 through section 2.3.
- Divide-and-conquer Recurrence equations.
CLRS chap. 4. Siegel, section 2.4 pp. 52-66.
- Sorting algorithms:
N^{2} sorts, Heapsort, Mergesort, Quicksort,
Radix sort. Lower bound. CLRS chaps. 6-8. Siegel, chap. 7.
- Sets: Lists. Hash tables. Binary trees. 2-3-trees/B-trees.
CLRS
chap. 10, 11, 12, 18. Siegel Chapter 6 through 6.4.7.
- Directed graphs: Implementation. Depth-first search. DAGS.
Shortest paths. CLRS chaps. 22,24,25. Siegel, chaps. 7, 8 through
8.4. 8.3.6 is optional.
- Undirected graphs: Minimum spanning tree. Union-find algorithm.
CLRS chaps. 21, 23. Siegel, sections 8.6 and 9.4
- Algorithmic techniques: Dynamic programming.
Greedy algorithms. CLRS, Chaps. 15, 16. Siegel, sections 11.3, 11.4.
- State space search/Implicit graphs: . Iterative deepening.
Class notes.
Requirements
Weekly problem sets (40%)
Midterm (1/2 class period) (15%)
Final exam (45%).
Problem sets should be submitted in hard copy or by email to the grader
by the start of
class on the day they are due. For email submissions, PDF is preferred,
but plain-text or Word are OK.
The graders for the course are
Rameez Loladia < rgl251@nyu.edu > and
Changle Wang < cl.wang@nyu.edu >
They will be grading alternate weeks: Rameez will grade the odd-numbered
problem sets (Problem set 1, due next week; problem set 3 ...) and
Changle will grade the even-numbered ones.
Grades will be posted on the course Blackboard site.
Class email list
Link to
the class email web page and follow the instructions there for
subscribing.
Assignments
Problem Set 1 Due Jan. 30. Note: Problem 5, which
was on the handout given out in class (though not in the current online
version) has been postponed to problem set 2.
Problem Set 2 Due Feb. 6
Problem Set 3 Due Feb. 13
Problem Set 4 Due Feb. 27
Problem Set 5 Due Mar. 5
Problem Set 6 Due Mar. 26
Problem Set 7 Due Apr. 2
Problem Set 8 Due Apr. 9
Problem Set 9 Due Apr. 16
Problem Set 10 Due Apr. 23
Problem Set 11 Due Apr. 30
Supplementary Notes
Examples of Recursive Algorithms and their Analysis
Notes on sorting:
HeapSort
MergeSort
QuickSort
Linear Time Sorts
Using Hashing for Large Sets of Large Objects
B-Trees
Notes on Scheduling
Exams
Midterm March 5, 8:00--9:00
Sample Midterm Questions
Final exam
The final exam will be Monday May 14.
Notes on the Final Exam
Sample Final Exam
Solutions to Sample Final Exam
Additional practice problems can be found in the department's
collection of Core Exams
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 the first incident of cheating will result in the
student getting a grade of F for the course.
The second incident, by GSAS rules, will result
in expulsion from the University.