We will cover three main topic areas:
- Extending algorithm design from one dimension to higher dimension.
- Approximation algorithm in higher dimension.
- 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.
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.
- Read the material taught in class, and make sure you understand all the definitions,
algorithms, theorems and proofs.
- Read the homework. Carefully.
- 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
- 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
- Only after you gave the problem a serious amount of thinking, try to collaborate,
find outside sources or come to the TAs for guidance.
- 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