Kjetil (Snow) Pettersen, kp1085@nyu.edu; office hours, Monday 1:30-3:30 (13th floor Commons, WWH), Wednesday, 2-4; Friday 11-1, the rest in Room 412 WWH; and by appointment.

**Class time**. 2:00-3:15pm, Tuesday/Thursday, room 109
WWH.

**Recitation. **12:30-1:45pm, Wednesday, room 109 WWH. You
need to attend the recitation as well as the classes.

First meeting.
Tuesday, January 28. You might find it helpful to watch the video on the
recursive algorithm for theTower of Hanoi problem before the
first class.

Class, April 24. Note unusual location:
Kimmel, room 914.

**Exam Dates:** Midterm, Thursday March 13. Alternative
final date: Friday May 16, 2:00-3:50pm, room 109 WWH.
Final, Tuesday May 20, 2:00-3:50pm, room 109 WWH**.
**All exams are closed book.

**Mailing list, home page**. There is a class mailing
list (csci_ua_0310_002_sp14@cs.nyu.edu). I send homework updates
and other useful information to this list. You should be
automatically subscribed to the list (I will send a test message
in the first week of classes); if you are not subscribed please
join the list (see http://www.cs.nyu.edu/mailman/options/csci_ua_0310_002_sp14).

**Course Goal and Syllabus**. The goal of this class is
to develop your ability to design effective algorithms. What
does this mean? Your algorithms should be correct (of course),
efficient (this is a major focus of the course), and adaptable
(i.e. if the problem changes, modifying the algorithm should not
involve a complete rewrite; just what this means and why it is
possible will become clearer as the course proceeds).

More specifically, this course concerns the design and
analysis of combinatorial algorithms, as opposed to numerical
algorithms. My approach is to focus on concepts and the art of
problem-solving. There will be weekly exercises designed to
strengthen your conceptual understanding and problem solving
skills. I am assuming you have adequate programming skills and a
solid understanding of basic data structures and their
implementation in your favorite programming language. Although
some mathematical knowledge and skill is helpful, I will cover
any mathematics we need.

**Assignments**. There will be more or less weekly
homeworks. 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. While you may
discuss homework problems with your fellow students, you must
write up your solutions in your own words. Be aware that
you are unlikely to perform well on exams unless you gain
practice at problem solving on the homeworks. Homeworks are due
at the start of class; **don't miss class to finish a
homework.** Finally, you will need to make a copy of your
homework for the reason I will explain next.

**Self-grading**. On the day the homeworks are due I will
be handing out solution sets. You are required to grade a copy
of your homework using the solution set as a guide and to hand
the graded copy in at the following class session. The
self-grading should indicate the mistakes in the original
solution and why they are mistakes. We will grade your original
solution and your self-grading. The purpose of this is to
enhance your understanding of the material.

To facilitate the management of the homework, I ask that you
do the following.

1. Write the solution to each problem on a separate sheet of
paper and leave space for your grading comments and for our
grading comments (e.g. margins on both sides, and top and
bottom, and don't use tightly spaced lines).

2. Hand in you solution in an envelope with your name on it. You
will need four envelopes in total: one for the homework, one for
the self-graded homework, and two for the following week's
homework. The intended schedule is as follows: homeworks
submitted on Tuesday, self-graded homeworks submitted on
Thursday, graded homeworks returned the following Thursday.

3. You may handwrite your homework, legibly of course, or
typeset it. The best way to typeset mathematical material is to
use Latex.

**Further Comments**. If you are unable to completely
solve a problem (or you cannot solve it at all) please write
down your thoughts on how the problem should be approached, and
where you approach breaks down. Or if you have given an answer
that you know is incorrect, please indicate what the error is.

**Honors Section. **You will be expected to do
additional homework problems. These should be written up
separately from the rest of the homework and submitted directly
to me. In addition, if you are interested, there is the
possibility of more open-ended implementation projects.

**Academic Integrity**. Please take note of
the course and departmental policy on this matter: http://www.cs.nyu.edu/web/Academic/Undergrad/academic_integrity.html

**Assessment**. The homeworks will comprise 40% of the
overall grade, the midterm 20% and the final 40%. However,
if the grade on the final is better than the midterm grade it
will replace the midterm grade. Exams will be closed book.

**Required text**. *An Introduction to Algorithms: their methods
and madness*,

If you want a published textbook, the following book has been
ordered by the NYU bookstore: *Introduction to Algorithms*
by Cormen, Leiserson, Rivest and Stein, but be aware that
the approach I will be following is the one in Prof. Siegel's
text.

Reading guide.
Detailed
lecture by lecture reading guide.

**Videos**. I will be recording videos of some of the
most critical material, as time permits. At the current time,
these are accessible only in NYU Stream (i.e. access is limited
to those with an NYU account). Video repository

Homeworks and handouts

Recitation
section notes

Class lecture notes

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

Homework 10

Homework 11

Homework 12

Homework 13

Sample Midterm

Sample Final

Additional Problems, Tree Algorithms

Additional Problems, Dynamic Programming

Last modified: April 29, 2014