.
Midterm: Tue, Oct 9 2012, 5:006:00PM, WWH102.
Final: Tue, Dec 18 2012, 5:006:50 PM, WWH 102.
Mailing list: To subscribe to the class list follow instructions at
To post a message to all the list members, send email to
csci_ga_1170_003_fa12@cs.nyu.edu. Please, post only messages
interesting to everybody taking the class. Specific classrelated
questions and most of your other correspondence should be directed to
the instructor.
Course Homepage: http://cs.nyu.edu/courses/fall12/CSCIGA.1170003/index.html
Lecture Notes:

Recitation 4 is based on the material from recitations 2 and 3 (which I did not present
earlier in class).

Lecture Note 6 is "Lower Bounds for Sorting" included in Lecture Note 4.
Homework Assignments:
Midterm Sample:
Midterm Solution:
Final Sample:
Brief Course Description:
This course covers the design and analysis of combinatorial algorithms.
The curriculum is conceptbased and emphasizes the art of problemsolving. The course features
weekly exercises designed to strengthen conceptual understanding and problem
solving skills. Students are presumed to have adequate programming skills and
to have a solid understanding of basic data structures and their implementation
in the programming languages of their choice. Although some mathematical
sophistication would be helpful for this course, the necessary mathematics is
contained within the curriculum.
Because of the emphasis on problem solving, students are
expected to attend the Thursday recitation sessions.
Be sure that you register for the recitation (section 004) as well as the class (section 003).
Course Topics
 Algorithmic analysis:
Correctness. Worstcase running time asymptotic
analysis. Big Oh notation. CLRS, chaps. 13. Siegel, chap. 1,
chaps 2 through section 2.3.
 Divideandconquer Recurrence equations.
CLRS chap. 4. Siegel, section 2.4 pp. 5266.
 Sorting algorithms:
N^{2} sorts, Heapsort, Mergesort, Quicksort, CountingSort,
Radix sort. Lower bound. CLRS chaps. 68. Siegel, chap. 7.
 Sets: Lists. Hash tables. Binary search trees. 23trees/Btrees.
CLRS
chap. 10, 11, 12, 18. Siegel Chapter 6 through 6.4.7.
 Directed graphs: Implementation. Depthfirst search. DAGS, Topological sort.
Shortest paths. All pairs shortest paths CLRS chaps. 22,24,25. Siegel, chaps. 7, 8
through
8.4. 8.3.6 is optional.
 Undirected graphs: Minimum spanning tree. Max flow, Unionfind 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.
Textbook:
1. An Introduction to Algorithms: their methods and madness,
by A.R. Siegel, available at NYU Copy Central 547 LaGuardia Place for a complementary price
of $28.00.
2. Introduction to Algorithms by
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein,
published by MIT Press.
You can get either the THIRD EDITION
or the SECOND EDITION.
Grading:
There will be one inclass midterm and a final exam, in addition to
approximately weekly homework assignments. Tentative grade split is
30% homework, 30% midterm and 40% final exam.
Homework:
There will be approximately 12 written homework assignments.
Some of the homework exercises will be routine, but others will be
more challenging. I do not expect you to solve all of the homework
problems, but I hope that you will benefit from working on the more
difficult ones. Homework will be assigned on Tuesdays, and will be due
the following Tuesday. No late homework will be accepted.
An advice about the homework assignments:
 Start early. Most problems will not be hard,
but others will be. Such more difficult problems are not
typically solved in one sitting. Start early and let the ideas
come to you over the course of a few days.
 Be rigorous. Each problem has a (sometimes
unwritten) requirement that you prove your algorithm
correct and analyze its running time. To obtain full
credit for a problem, it is necessary to fulfill these
requirements. We expect real proofs and real analysis, not
"proof by hand waving."
 Be concise. Express your algorithms at the
proper level of detail. Give enough details to clearly present your
solution, but not so many that the main ideas are
obscured. English is often a good way to express an
algorithm; pseudocode is good for communicating complex control
structure.
 Collaboration? You are encouraged to
solve all the homework questions on your own, but are
permitted to brainstorm difficult problems in small
groups, as long as each of you writes the solutions
individually and honestly acknowledges the cooperation.
Needless to say, if you work with others but never come up with
the solution on your own, you may do OK in the homework
component of your grade, but you will suffer on exams, so be
careful.