DM833 - Approximation Algorithms

Spring 2013
Lene Monrad Favrholdt

Exam

There will be an oral exam on Thursday 6th and Friday 7th of June.

Exam questions:

  1. Vertex Cover and Set Cover
  2. Steiner Tree and TSP
  3. Multiway Cut and k-Center
  4. Knapsack and Bin Packing
  5. Scheduling to minimize makespan
  6. Linear programming techniques

When it is your turn for examination, you will draw one of the above questions. Then you will be placed alone in a preparation room. You will have approximately 30 minutes of preparation time and you are allowed to use any material that you bring yourself. You are not allowed to leave the room or have any contact with other people until we come and pick you up. In rare cases, this could take somewhat longer than the 30 minutes that we aim for.

After the preparation time, the actual exam takes place. This part lasts approximately 25 minutes. Your goal is to convince the examiner and external examiner ("censor" in Danish) that you have a thorough understanding of the topic.

You should start by presenting material related to the question you drew. Aim for a reasonable high pace and focus on the most interesting material related to the question. You may bring a short list of keywords for the actual exam to remember what you have decided to present. Thus, you are not supposed to use note material, textbooks, transparencies, computer, etc. for this part.

We, the examiner and the external examiner, will supplement with specific questions when appropriate, and after a while, we will end the discussion of the exam question that you drew and turn to material from other parts of the curriculum. Note that all of this is included in the 25 minutes, so do not count on more than 10 minutes for your own presentation.

Note that the questions are generally quite broad. Hence, you must select the material you choose to cover. It is often a good idea to start with an overview of the most important parts of the topic and then give a detailed treatment of one result. You will of course also be evaluated based on your selection of material. If you only present the simplest material, you limit the grade you can obtain. On the other hand, a good presentation of the simple material is better than a poor presentation of the harder material