CSCI-GA.1170-003/004 Fundamental Algorithms, Fall 2011

Lecturer: Prof. Yevgeniy Dodis, dodis

cs.nyu.edu, (212) 998-3084, room 413, WWH. Office hour: Monday 5-6
Meeting Time/Place: M 7-9, room 101, WWH.
Recitation Time/Place: W 7-8, room 101, WWH.
Recitation Instructor: Arka Prava Bandyopadhyay, apb321

nyu.edu, (212) 998-3153, Rm 425, WWH. Office hour: Tuesday, 5-7
Midterm: Monday, October 31, in class. Final: Monday, December 19th, 7:10-9:00PM, Room 101, WWH.
Mailing list: To subscribe to the class list, follow instructions at

http://www.cs.nyu.edu/mailman/listinfo/csci_ga_1170_003_fa11

To post a message to all the list members, send email to csci_ga_1170_003_fa11@cs.nyu.edu. Please, post only messages interesting to everybody taking the class. Specific class-related questions and most of your other correspondence should be directed to the instructor.
Course Homepage: http://cs.nyu.edu/courses/fall11/CSCI-GA.1170-003/index.html

Lecture Summaries

Additional Handouts:

Problem Sets: (Please remember to write each new problem on a separate, new sheet of paper with your name on top.)

Brief Course Description:

This is an introductory course in algorithms. We will cover standard topics such as sorting, divide-and-conquer, various data structures, graph algorithms, dynamic programming, greedy algorithms, and - time permitting - NP-completeness and basic approximation algorithms. The emphasis will be given to arguing the correctness of algorithms and performing the analysis of their running time.

Textbook:

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 (recommended) or the SECOND EDITION. The exercises will refer to the THIRD edition.

Grading:

There will be one in-class midterm and a final exam, in addition to approximately weekly homework assignments. Tentative grade split is 40% homework, 25% midterm and 35% final exam.

Each homework grade will consist of two parts: correctness and effort. The correctness grade is a numeric grade equaling the sum of the correctness grades for each homework problem, and roughly measures the fraction of the homework correctly solved. In contrast, the effort grade is a single number from 0% to 100%, and roughly measure the effort level the student has put into solving the homework. This grade will play an important role in the "overall" homework evaluation, so students are encouraged to try as many problems as possible. (Of course, simply restating the problem or intentionally writing "nonsense" as a proposed "solution" might actually lower your effort grade, so only put genuine thoughts and attempts into your solutions.) Generally, I expect the effort grade to be "higher" than the correctness grade.

Programming Project:

Currently, I plan on not giving the final programming project. If this changes, the details of the project will appear here.

Homework:

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 Mondays, and will be due the following Monday. No late homework will be accepted. The solutions will be handed out during the recitation of the week the homework is due. We encourage the students to come to the recitation - not only for the homework solutions, - but primarily to see examples of the problems similar to those assigned for the following Monday.

A few hints on 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 analyses, 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.
Bibles? Help? More or less, you are only allowed to use the textbook and your lecture notes. In particular, the use of internet, course bibles, outsiders, and other clearly "cheating" resources is strictly prohibited. Please talk to me if you are having problems keeping up with the material.