Course Policies

Class Topics

We will cover three main topic areas:

  1. Extending algorithm design from one dimension to higher dimension.
  2. Approximation algorithm in higher dimension.
  3. Topological algorithms.
Please see the schedule for a tentative schedule of specific topics.


Grades will be deterimed by the following components:
Classroom Participation 5%
Homework 25%
Project 20%
Midterm 25%
Final 25%

Lateness and Absence

Make-ups for the exams and the final must be arranged at least one week in advance, barring extreme situations. Make sure to document any health problems you might have.

Academic Integrity

We will assume that you understand the issues and do not need an explanation here.


  • All homeworks are due at the beginning of class on the due date. See due dates.
  • You are encouraged to work in groups. The group should be as diverse as possible, and no larger than three people per problem.
  • On all assignments each person should hand-in their own writeup. That is, collaboration should be limited to talking about the problems, so that your writeup is written entirely by you and not copied from your partner. In addition, list all members of your group.
  • You are required to neatly handwrite or type your solutions (preferably using LaTeX). For your convenience, we have provided a LaTex Homework Template.
  • You must cite all reference, including individuals and/or webpages that you may have used to solve the problems.

Tips for Solving the Homework

Ideally, this is how you should approach the homework.
  1. Read the material taught in class, and make sure you understand all the definitions, algorithms, theorems and proofs.
  2. Read the homework. Carefully.
  3. Spend at least one hour thinking about each problem by yourselves. This is the vital part of understanding the course's material. You will get stuck, that's ok. When you do, here are some suggestions to help you get past it.
    • Come up with a dummy example, over a small number of item, and try to solve it. This is particularly helpful when you're trying to follow an algorithm, or when devising a counter example.
    • Which algorithms / techniques / heuristics taught in class are applicable to the problem at hand? When do they fail and for what reason?
    • Reduce the problem to a problem taught in class. Can the problem be represented as a graph? a network? maybe to a less general instance of the problem itself (a graph with negative weight to a graph with unique, non-negative weights)?
    • The notion of sub-problem (divide-and-conquer, dynamic programming, induction) is a recurring theme in this class. Try to identify and solve the sub-problems of the problem at hand.
  4. Only after you gave the problem a serious amount of thinking, try to collaborate, find outside sources or come to the TAs for guidance.
  5. Write down the solution, by yourselves. Re-read what you've wrote. Make sure the solution is exact, and answers specifically what you've been asked about. It should be clear, but it need not necessarily be long.

Finally, feel free to contact either instructor to clarify these policies.