Design and Analysis of Algorithms

Course Goals

By the end of this course, you will have developed the following knowledge and skills:
  • Know how to design and analyze algorithms.
  • Understand several standard algorithmic design techniques, including greedy algorithms, divide and conquer, and dynamic programming.
  • Be able to design randomized and/or approximation algorithms, and determine when approximation and/or randomization are useful for a problem.
Above all, the goal of this course is to instill a deep understanding of how to think algorithmically about problems.


Grades will be tentatively weighted as follows:
45% Homework Assignments
5% Classroom and Lab participation
25% Midterm Exam
25% Final Exam

Most lab assignments will consist of in-class exercises and will not be graded. Expect roughly ten homework assignments during the semester. You'll be able to work with a partner with several but not all of them; each homework assignment will specify if working with a partner is allowed.

Homework Policy

Written homework will typically go out Friday afternoon and be due at 10AM the next Friday. We should have around 10 homework assignments. Some will be individual assignments; others you'll be able to work with a partner. Unless stated otherwise, you can submit either typed LaTeX solutions or hand-written notes.

Extra Credit Policy. In many of the homework assignments, there will be one or two extra credit problems. These problems are completely optional -- do not feel obligated in any way to complete these problems. Extra credit will not be directly applied to your overall grade; at best, they will be used to make up some credit lost by not handing in assignments on time. Please contact me if you have questions about the extra credit policy.

Late Policy. Each individual will be given 2 late days for the semester. This will encompass any reason---illness, interviews, paper deadlines, etc. You must notify me 24 hours in advance of the original lab deadline that you plan on using a late day. When handing in late group assignments, each partner must use a late day. Once you use up your late days, further late assignments will not be accepted except in very unusual extreme circumstances. Even if you do not fully complete a lab assignment you should submit what you have to receive partial credit.

Academic Accomodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services, located in Parrish 130, or e-mail lhempli1 to set up an appointment to discuss your needs and the process for requesting accommodations. Leslie Hempling is responsible for reviewing and approving disability-related accommodation requests and, as appropriate, she will issue students with documented disabilities an Accommodation Authorization Letter. Since accommodations may require early planning and are not retroactive, please contact her as soon as possible. For details about the Student Disabilities Service and the accomodations process, visit the Disability Services Webpage.

You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Leslie Hempling in the Office Of Student Disability Services.

To receive an accommodation for a course activity, you must have an Accomodation Authorization letter from Leslie Hempling and you need to meet with me to work out the details of your accommodation at least two weeks prior to any activity requiring accomodations.

Academic Integrity

Note: in the following paragraphs, "code" refers to all homework solutions, including written programs but also proofs, analysis, written reports, etc.

Academic honesty is required in all your work. Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Please contact me if you have any questions about what is permissible in this course.