## 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
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

### 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.

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:

• 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 analysis, 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.