COSC-311: Algorithms

Fall 2019


Section 1 (Prof. Gardner)    Section 2 (Prof. McGeoch)    Schedule and Assignments

Course Information

Meeting times: MWF 11-11:50am
Location: Seeley Mudd 206 (note the NEW location)
Prerequisites: COSC-112 and COSC-211 (or their equivalents at another institution). Please come talk to me if you have not taken both of these courses.

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:

  1. Recognize a standard body of computational problems and understand the algorithms that are used to solve them,
  2. Develop familiarity with three key algorithmic paradigms: divide-and-conquer, greedy, and dynamic programming,
  3. Gain experience and comfort applying the above paradigms to unfamiliar problems, and
  4. Advance your ability to clearly communicate complex technical ideas.
I will post grades on Moodle, but all other course information, assignments, handouts, etc. will be on this page.

Contact Information

Instructor: Kristy Gardner
Email: kgardner@amherst.edu
Office: C215 Science Center
Phone: 413-542-5428
Web site
Office hours: Monday 2-3:30pm and Wednesday 4-5:30pm. If you are unavailable during my regular office hours, I can often find time to meet by appointment at other times MWF. I am not, in general, available to meet on Tuesdays or Thursdays.

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.


Recommended Textbook

The following textbook is a good reference that provides supplementary coverage of the material we will discuss in class. You are NOT required to purchase this book. There will not be any assignments that require you to have the book (though I will note the relevant chapters for each topic on the course schedule); it is simply a recommendation should you wish to consult a source other than your notes. The book is available on reserve in the library.

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.


Grading

1. Mini Homework. There will be a "mini" homework assignment every week, usually assigned on Friday and due the following Friday in class. Please write your name and section number on your submission. These assignments will directly check your understanding of the material we cover in class and are intended to take a short amount of time to complete. Mini homework has three primary purposes:
  1. To help you quickly identify topics you would benefit from studying further,
  2. To help me quickly identify topics that we would all benefit from spending more time on in class, and
  3. To ensure that you are engaging with the material regularly outside of class.
Each mini homework will be given a score of 0 (not turned in or largely incorrect), 1 (partially correct), or 2 (correct). I will post solutions to the mini homework after class on the day it is due, so there are no extensions on mini homework.

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:

  1. To give you practice applying the ideas we have discussed in class to new problems, and
  2. To give you practice communicating your ideas clearly and concisely.
Homework will be graded based on both correctness and clarity. All problems will be graded for correctness. Usually I will choose one problem per assignment for which I will evaluate and give feedback on your writing, but I will not tell you in advance which problem this will be.

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:

I will grant additional extensions only if I hear from your class dean that you are facing extenuating medical or personal circumstances.

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.


Intellectual Responsibility

In general, you are expected to do your own work in this class unless otherwise specified. All written solutions must be your own. Do not look at other students' written work, and do not show your work to other students. Do not discuss assignments with anyone other than myself, the course TAs, and students currently enrolled in the class. You are not permitted to look for solutions to any assignment on the internet.

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 are struggling...

Please come see me. In addition to my office hours and the TA-led evening help sessions, the Dean of Students office offers peer tutoring if we decide you would benefit from some extra time spent one-on-one with a peer tutor. Should you need support related to challenges beyond this course, I encourage you to seek help from the numerous resources available on campus, including but not limited to your class dean, your RC, the health center, and the counseling center.

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.