DM865 - Heuristics and Approximation Algorithms

Exam Guidelines

The oral exam takes place on June 6, in U59 from 9:30.

When it is your turn for examination, you will draw one of the topics listed below:

  1. Set Cover

  2. Traveling Salesman Problem

  3. Knapsack and Bin packing

  4. Scheduling: Approximation results

  5. Scheduling: Heuristics

  6. MaxSat

The examination lasts approximately 25 minutes. Your goal is to convince the examiners and external examiner (“censor” in Danish) that you have a thorough understanding of the topic.

You should start by presenting material related to the topic you drew. Aim for a reasonably high pace and focus on the most interesting material related to the question. You may bring a short list of keywords for the 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 examiners 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. Finally, we will ask questions from your handed in projects on heuristics. Resuming:

Note that the topics 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.