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