|
|
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 me is by coming to my office hours or sending me email. I will try to respond to questions as soon as possible - hopefully within one working day.
| Name | Position | Phone | Office hours | |
| Alexa Sharp | Instructor | asharp@cs.cornell.edu | 5-9834 | 10-12 most days, sometimes 11-1,4-5 Upson 5157 |
Monday to Friday, 8:30-9:45, Hollister 368. Starts July 8. That's a Friday.
I'll have regular office hours during the day and (possibly) 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 an office hour in time. I'm going to try not to be conned in to last-minute office hours.
I've booked the room Upson 205 from 6:30pm - 9:30pm every weeknight during the course (so, July 8 - August 19) 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 a planned evening session, that's where I'll be. If there's nothing planned, I probably won't be there. Not my style to hang out in empty classrooms. Anymore.
I want to encourage the students to give me feedback on my teaching techniques, the material covered, or anything else. To facilitate this, I 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 I'm giving you ideas.
We will also have more standard instructor evaluations every few weeks, so that I can get more standard feedback. I just want to make sure I'm doing things ok, and if not, make some changes.
The official textbook for the course is Algorithm Design by Jon Kleinberg and Eva Tardos, which you can get at the Campus Store. It'll set you back about $90, but it's a $90 well-spent. Can you use the course notes from previous semesters? Well, if it's a recent semester (Summer 2004 or Spring 2005) you can probably get away with it... as far as I can tell *most* of the content is the same, although the section numbers sometimes differ. However, and I know I'm biased and all that, it's a textbook that you may want to keep around, y'know, to show the grandkids. So a hardcover ditty may be what you want if you can spare the extra cash.
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 13 | Matchings & Graphs | ||
| Assignment 2 | July 15 | Greedy & MST | ||
| Assignment 3 | July 19 | Divide & Conquer | ||
| Assignment 4 | July 22 | Dynamic Programming | ||
| Assignment 5 | July 29 | Network Flows I | ||
| Assignment 6 | August 3 | Network Flows II | ||
| Assignment 7 | August 8 | NP Completeness | ||
| Assignment 8 | August 16 | Special Cases of NP Problems & Approximation Algorithms | ||
| Assignment 9 | August 18 | Probabilistic & Online Algorithms | ||
| Exams | Date | Time | Place | |
| Prelim I | July 25 | in class | Hollister 368 | 15% |
| Prelim II | August 9 | in class | Hollister 368 | 15% |
| Final Exam | August 19 | 9:30-12 | Hollister 368 | 25% |
The above table is, naturally, subject to change. And yes, I 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 I will 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 me as soon as possible. I'll 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 me during the first week of class so that we have time to make suitable arrangements.