Basic Algorithms, CSCI-UA.0310

Instructor. Richard Cole, 417 WWH, tel: 998-3119, cole@cs.nyu.edu; office hours: 4-5pm Monday and Wednesday, and by appointment.
Instructional Assistant. Adriana Lopez-Alt, lopez@cs.nyu.edu; office hours, Monday 11-1, Room 412 WWH; and by appointment.
Tutors.
Jingni Liu, jl3750@nyu.edu; office hours, Tuesday 10:30-12:00, 3:30-5:00; Wednesday 11-12; Thursday 12:30-1:30, 3:30-4:30, all in Room 412 WWH; and by appointment.
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 WWHAll 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.

Course Topics

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 textAn Introduction to Algorithms: their methods and madness, by A.R. Siegel; this will be available at NYU Copy Central (547 La Guardia Place) at the start of the semester.
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

Self Grading Guide

Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Homework 11
Homework 12

Sample Midterm
 
Additional Problems, Tree Algorithms
Additional Problems, Dynamic Programming

Last modified: April 22, 2014