CSCI-GA.1170-003/004 Fundamental Algorithms, Spring 2019

Lecturer: Prof. Yevgeniy Dodis, dodiscs.nyu.edu, (212) 998-3084, room 413, WWH. Office hour: Tuesday 5pm-6pm, room 413.
Meeting Time/Place: Tuesday 7:10pm-9:00pm, room 109.
Recitation Time/Place: Thursday 8:10pm-9:00pm, room 109.
Recitation Leader: Shravas Rao, raocs.nyu.edu. Office hours: Wednesday 4pm-5pm, room 412; Thursday 7pm-8pm, room 412.
Graders: Please discuss all issues related to grading with the corresponding grader (we will publish each week who graded what problem).
Do not contact the Instructor or the Recitation Leader.
    Divyansh Khanna, dk3399@nyu.edu. Office hours: Tuesday 12pm-1pm, Thursday, 12pm-1pm, room 412.
    Tejal Lotlikar, tl2482nyu.edu. Office hours: Wednesday 2pm-4pm, room 412.
    Yi Tang, yt1433nyu.edu. Office hours: Monday 3pm-4pm, Tuesday 3pm-4pm, room 412.
Midterm: Tue March 12, 7:10-9:00pm, room 109. Final: Tue May 14, 7:10-9:00pm, room 109.
NYU classes (for homework submission): https://newclasses.nyu.edu/portal/site/ef8cab71-3517-4e54-b502-08db92f2da09#
Course Homepage: https://cs.nyu.edu/courses/spring19/CSCI-GA.1170-003/index.html

Lecture Summaries (see also Selected Notes from MIT)

Additional Handouts:

Problem Sets:


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 - some special topics (e.g., online 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. Students on the "boundary" between two grades can increase their grade by doing accurate self-grading, between two grades can increase their grade by doing accurate self-grading, as explained below.

Homework:

Each problem set will consist of several problems. 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 the day of the class, and will be due the following week (unless stated otherwise). No late homework will be accepted. The solutions will be discussed 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 week.

The maximum point value for each problem (and, sometimes, parts of the problem) will be stated on the homework. Some questions in the homework will be for the extra credit, and will be explicitly marked as such (together with their maximum extra credit) on each assignment. Solving such problems can make your overall grade for the homework above 100%, or, alternatively, effectively "erase" the credit lost for not solving some of the required problems.

We suggest students to use Latex for their solutions, and will provide a Latex source file for each homework (where the students need to replace "stars" ***** by their solutions). Students are welcome to look at this short Latex tutorial for some useful pointers.

Self-Grading:

In particular, after the students handed in their homework and learned the correct solutions during the following recitation, but before getting back their graded solutions, the students can hand in their self-graded homework, using the same grading system they expect from the actual graders. Unlike regular homework, self-graded homework should only be submitted by email to shravasraofaspring2019gmail.com. Make sure you use subject line "FA19 self-graded: homework number, your name" if you follow this option. We believe self-grading their own mistakes will greatly improve the students' understanding of the material. Moreover, as explained above, students on the "boundary" between two grades might increase their grade by doing accurate self-grading.

Concluding Remarks: