|
|
CS482 is an introduction to the design and analysis of algorithms. The primary goal of this course is to introduce some common techniques and issues that arise in the study of algorithms. The topics include dynamic programming, network flows, NP-completeness, intractability, and muchos more. We expect the students are familiar with the topics from CS211, CS 280, and CS 312. (CS 381/481 is also a prerequisite, but as far as CS482 is concerned, serves primarily to ensure the ability to write clear and mathematically rigorous proofs, and provides some exposure to the concept of a reduction).
We want our students to come out of the course with the confidence, tools, and techniques to tackle difficult problems. They will learn how to assess the main challenges of a problem, find one or more solutions, and determine which solution is best for the application. Finally, they will learn how to recognize and prove that certain problems are computationally intractable, and what can be done in these situations.
The best way to reach the course staff is by coming to our office hours or sending us email. We will try to respond to questions as soon as possible - hopefully within one working day. If we judge that the question might have been better directed to the other staff member, the question may be forwarded there unless an explicit request is included to the contrary.
| Name | Position | Phone | Office hours | |
| Alexa Sharp | Instructor | asharp@cs.cornell.edu | 5-9834 | M-R 11-12, TR 4-5, M 6-7 Upson 5157 |
| Vivek Vishnumurthy | TA | vivi@cs.cornell.edu | 5-7216 | F 11-12, MW 4-5, T
7:30-8:30 Upson 350 |
Monday to Friday, 8:30-9:45, Hollister 368. Starts July 9.
We have regular office hours during the day and evenings. Office hours are given in the above table. Try to get your assignments started early so that if you have any trouble you can make it to someone's office hour in time. We are going to try not to be conned in to last-minute office hours.
We have booked the room Upson 215 from 6:30pm - 9:30pm every weeknight during the course (so, July 9 - August 20) for evening office hours, study/review sessions, raves, or any other evening activities we may have. If you're in doubt as to where to find us for a planned evening session, that's where we'll be. If there's nothing planned, we probably won't be there. I mean, it's not our style to hang out in empty classrooms.
We want to encourage the students to give us feedback on our teaching techniques, the material covered, or anything else. To facilitate this, we set up a hotmail account coms482@hotmail.com with the password whatever for you to use to send either of the staff email anonymously. Please only use this for constructive comments, and not just to send us spam or insults, or to sign up for something suspicious. Great, now we're giving you ideas.
We will also have more standard instructor evaluations every few weeks, so that we can get more standard feedback. We just want to make sure we're doing things ok, and if not, make some changes.
The official textbook for the course is a draft of a book by Jon Kleinberg and Eva Tardos, which you can get at the Campus Store. If the Campus Store has run out of books, you can call them and ask for an additional copy to be printed. This usually takes one or two days.
The authors developed the book while teaching CS 482 in the past few years, so it is organized around the structure of the course. However, it is not a substitute for coming to class, as we will cover material not in the book, and the book contains some material that is not required. Note that some reading assignments will be given from the book on topics not covered in class.
There are also some useful textbooks on reserve in the Engineering library, such as
Students are responsible for all material in the assigned readings, as well as material covered in lectures. There will be nine(ish) assignments, two in-class preliminary exams, one final exam, and pop quizzes that we may or may not tell you about. The assignments will be written exercises. Exams will cover material presented in class and will require you to do some heavy thinking on your feet. The pop quizzes will test you on what you learned in the last day or so. Your final grade is determined roughly as follows:
| Assignments | Date | Subject | % of grade | |
| Assignment 1 | July 14 | Matchings & Graphs | ||
| Assignment 2 | July 16 | Greedy & MST | ||
| Assignment 3 | July 20 | Divide & Conquer | ||
| Assignment 4 | July 23 | Dynamic Programming | ||
| Assignment 5 | July 30 | Network Flows I | ||
| Assignment 6 | August 4 | Network Flows II | ||
| Assignment 7 | August 9 | NP Completeness | ||
| Assignment 8 | August 16 | Special Cases of NP Problems & Approximation Algorithms | ||
| Assignment 9 | August 19 | Probabilistic & Online Algorithms | ||
| Exams | Date | Time | Place | |
| Prelim I | July 26 | in class | Hollister 368 | 15% |
| Prelim II | August 10 | in class | Hollister 368 | 15% |
| Final Exam | August 20 | 9:30-12 | to be determined | 25% |
The above table is, naturally, subject to change. And yes, we can add. Usually. The remaining 5% are up to the instructor's discretion, and will probably be based on class participation, attendance and quizzes.
No late assignments will be accepted. Period. This is because we will often try to grade the assignments the same day they are due and return them immediately. They will be due at the beginning of lecture on the due date. This is partly to make you show up to class. And I know everyone always says this, but really, you should try to get started on your assignments (especially these ones) early.
If for some reason (such as severe life-threatening illness) you are unable to complete an assignment or take a test, please talk to one of the instructors as soon as possible. We will handle them on a case-by-case basis.
In general, it is OK to talk with other students about the assignments, but you have to be very careful about how much you collaborate. A good rule of thumb is that you may talk to each other so long as no one writes or types anything down. And when you work in a group, you must list on your assignment who you worked with. Please do not hand in work done with (or by) someone else under your own name. The penalties for cheating at Cornell are severe, and include expulsion; see the CS Department's Code of Academic Integrity. Please don't break the rules. Not only is it bad, but it's disrespectful to us as instructors. If you are unsure about anything, please ask.
If you are registered with the Office of Student Disability Services and require special accommodation (such as additional time to complete exams), please speak to Alexa during the first week of class so that we have time to make suitable arrangements.