Overview: This course is the second half of a two-course sequence on data structures and algorithms (COSC-211, Data Structures, is the first half). Topics covered will include sorting and selection, divide-and-conquer algorithms, greedy algorithms, dynamic programming, network flow, and NP-completeness. Much of the course content is theoretical, focusing on understanding what it means for an algorithm to be efficient, learning how to analyze algoithms' efficiency, and exploring what to do when we cannot design efficient algorithms.
Course goals:
TA office hours: Kathleen Isenegger and Jack Klein, Sunday 5-7pm and Thursday 6:30-8:30pm, SCCE C101
Moodle forum: Always available! Please use this forum to ask questions about course material and to answer your classmates' questions. Prof. McGeoch, Kathleen, Jack and I guarantee that we'll respond to your question (or endorse another student's response) by 6pm the day after you post your question.
Algorithm Design, by Kleinberg and Tardos, Pearson/Addison-Wesley, 2006. ISBN: 0321295359.
The following textbook is another commonly used algorithms book that you may wish to consult to supplement the in-class course content. Again, it is not required. It is available from the library.
Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, MIT Press, 2009. ISBN: 9780262033848.
2. Homework. There will be five longer writen homework assignments throughout the semester, usually assigned on Friday and due two weeks later. These are larger assignments that will take time to complete. I give you two weeks for a reason, and I highly recommend that you start early! The primary purposes of homework are:
Submission: Homework must be typed; I recommend using LaTeX to typeset your work. Each problem must be turned in on a separate pice of paper, not stapled, with your name and section number on each problem (if you use more than one piece of paper for a single problem please staple those paged together). If you worked with classmates on the homework (see below for course policies regarding collaboration), you must note at the top of the submission with whom you worked. Late homework (see below) must be submitted to me by email.
Deadlines, late days, and extensions: Homework must be submitted at the start of class on the day it is due. You make take 4 late days during the semester. These can be used for any reason, without penalty, and you do not need to ask me or tell me that you are using them. Details:
3. Midterm exams. There will be two in-class midterm exams, the first on Friday, October 18 and the second on Friday, November 22. Note that the second midterm is just before the start of Thanksgiving break; please keep this in mind when making your travel plans.
4. Final exam. There will be a final exam during exam week. The exact date and time will be scheduled by the Registrar's office in mid-October. Please do not make your end-of-semester travel arrangements until after the exam is scheduled. Amherst's final exam week is December 16-20; if you are a five college student note that this may differ from the schedule at your home institution.
5. Class participation. I expect students to attend class and to engage with the material while in class. While the class format is primarily lecture-based, I ask lots of questions and I hope to hear from all of my students. My goal is for the classroom to be a place where you feel comfortable contributing to the discussion, both by responding to my questions and by speaking up if you have a question.
Mini homework must be completed individually without discussion with classmates, students who have previously taken the course, or anyone else (besides myself and the TAs, who you are always welcome and encouraged to talk to). Mini homework is designed to help me identify topics that have been confusing, and it is difficult for me to do so if the assignments are not done individually.
You may discuss how to approach homework with other students who are currently taking the class. The homework assignments are meant to be challenging, and I encourage you to share ideas and approaches with your classmates. However, your final writeup must be entirely your own. My recommendation is to work with classmates to formulate an approach to a problem, but then work independently to write up your solution.
All exams must be completed individually without help from classmates, TAs, notes, textbooks, internet, phones...you get the idea.
If you have a documented disability that requires accommodations, you will need to contact Accessibility Services (accessibility@amherst.edu or 413-542-2337). After you have arranged your accommodations with Accessibility Services, please set up a time to meet with me to discuss how we can best implement your accommodations in this class. If you use accommodations for exams, you will need to tell me this in writing (i.e., by email) at least one week in advance of each exam so that we can make appropriate arrangements.