CSCI-UA.0310-001/002 Basic Algorithms (Regular and Honors), Fall 2011

Lecturer: Esther Ezra , my first name at cs.nyu.edu, (212) 998-4859, room 416, WWH. Office hour: Monday 3:15--4:15
Meeting Time/Place: MW 2:00--3:15, room 201 WWH.
Recitation Time/Place: T 9:30-10:45, room 202, WWH.
Recitation Instructor: Kalyan Pabbisetty. Email: kp1043 at nyu.edu
Grader: Sakshi Chauhan. Email: sc3456 at nyu.edu
Midterm: Mon October 17, in class. Final: Mon December 19, 2:00--3:50PM, WWH 101.
Mailing list: To subscribe to the class list, whether regular section or honors section, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/csci_ua_0310_002_fa11
Notice, the above mailing list will be used both for regular (002) and honors (001) sections. So do not sign-up for the "001" list.
To post a message to all the list members, send email to csci_ua_0310_002_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-UA.0310-002/index.html

Lecture Notes:

Homework Assignments:

Midterm Samples:

You may also look at the homework assignments at http://cs.nyu.edu/~yap/wiki/class/uploads/FunAlgo/
and the problems sets at http://cs.nyu.edu/courses/fall11/CSCI-GA.1170-003/index.html
These sets of problems are somewhat harder than the ones in our course, but they are good for practicing.

Brief Course Description:

This is an introductory course in algorithms. We will cover standard topics such as sorting, recurrences, computational models, various data structures, graph algorithms, dynamic programming, and - if time permits - NP-completeness and basic approximation algorithms. The emphasis will be given on arguing the correctness of algorithms and performing the analysis of their running time. We will also discuss invariants and emphasize their importance.

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 or the SECOND 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.

Honor Project:

Students at the honor section will have to do an honor project studying and summarizing some advanced algorithmic topic not covered in class. The project is due to the end of the semester. The approximated time to begin the project is right after midterm, where, on one hand students have sufficient background to absorb it, and on the other hand, have enough time to complete it.
Note: Project is purely theoretical and does not involve programming. This is a theoretical course!

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 Wednesdays, and will be due the following Wednesdays. No late homework will be accepted.

A few hints on the homework assignments: