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

- Recognize a standard body of computational problems and understand the algorithms that are used to solve them,
- Develop familiarity with three key algorithmic paradigms: divide-and-conquer, greedy, and dynamic programming,
- Gain experience and comfort applying the above paradigms to unfamiliar problems, and
- Advance your ability to clearly communicate complex technical ideas.

Web site

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

- To help you quickly identify topics you would benefit from studying further,
- To help me quickly identify topics that we would all benefit from spending more time on in class, and
- To ensure that you are engaging with the material regularly outside of class.

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

- To give you practice applying the ideas we have discussed in class to new problems, and
- To give you practice communicating your ideas clearly and concisely.

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

- 12pm (noon) is the cutoff for what constitutes a "day" (that is, if the homework is due in class on Friday, then if you submit it between noon on Friday and noon on Saturday it is one day late, if you submit it between noon on Saturday and noon on Sunday it is two days late, and if you submit it Sunday afternoon it is three days late).
- You may use up to 2 late days without penalty on any individual homework assignment.
- If you submit an assignment 3 days late (or one day beyond your total remaining number of late days, if you have fewer than 2 late days remaining), you can receive up to half credit on the assignment. This will count as having used 2 of your penalty-free late days.
- Work submitted more than 3 days late (or more than one day beyond your remaining number of late days) will not receive credit.
- Please submit any late work to me by email.

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