COSC-311: Algorithms

Fall 2018


Home    Schedule and Assignments

Course Information

Meeting times: MWF 10-10:50am (Section 01) OR MWF 11-11:50am (Section 02)
Location: 206 Seeley Mudd
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 3-5pm. If you are unavailable during my regular office hours, I can often find time to meet by appointment at other times MWF. I am rarely available to meet on Tuesdays or Thursdays.

TA office hours: Tuesday 7-9pm (Mackenzie and Jamie) and Thursday 7-9pm (Asa and Jamie), SCCE A013


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 (10%). There will be a "mini" homework assignment every week, usually assigned on Wednesday and due the following Wednesday in class. Mini homework must be submitted in hard copy with your name and section number written at the top. 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 ocmplete. 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 (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:

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


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.