**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:** Tuesday 7-9pm (Mackenzie and Jamie) and Thursday 7-9pm (Asa and Jamie), SCCE A013

*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 (30%).** There will be five longer writen homework assignments, 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.

**3. Midterm exams (15% and 20%).** There will be two in-class midterm exams, the first on Wednesday, September 26 and the second on Monday, November 5. The first midterm will be worth 15% of your grade and the second midterm will be worth 20% of your grade.

**4. Final exam (25%).** 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, and you are expected to wait to make your end-of-semester travel arrangements until after the exam is scheduled.

I will not take attendance and you will not be explicitly graded on participation, but participating in class (or not) can help (or hurt) you should you end up on the border between two grades. I strongly encourage you to attend all class meetings. You likely will find it difficult to keep up with the material if you do not come to class, and I will not use office hours time to teach you material from lectures that you decided to skip.

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