15-456/852: Computational Geometry, Fall 2015

- Extending algorithm design from one dimension to higher dimension.
- Approximation algorithm in higher dimension.
- Topological algorithms.

Classroom Participation 5%Homework 25%Project 20%Midterm 25%Final 25%

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

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

- 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 these policies.