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 201, WWH.
Recitation Instructor: TBA
Midterm: TBA. Final: December 19, in class.
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-001/index.html

Lecture Notes


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

A few hints on the homework assignments: