Questions of general interest that I receive either by email or via a consultation in my office will be answered here.

Time and Location

The exam will take place on Monday, January 18, 2016. You should show up outside U29A. The first student draws a question at 8:00.

The exam sequence is now available. Note that you cannot calculate a certain examination time from your slot in the sequence, since students before you may not show up. Thus, if you want to be certain to be examined, show up early. We are not expecting many no-shows for this particular exam, so expected examinations times will probably not change much, but of course, due to accumulation of effects, the probability of your examination time moving earlier increases during the day. We take a half hour lunch break close to noon.


  1. Jon Kingo Christensen
  2. Rojin Kianian
  3. Casper Kehlet Jensen
  4. Mikkel Levisen
  5. Diana Esi Hooper
  6. Uffe Thorsen
  7. Peter Severin Rasmussen
  8. Janine Weber
  9. Martin Østergaard Villumsen
  10. Martin Pedersen
  11. Jesper Beltoft Lund
  12. Yuan Liang
  13. Maria Nathalia Vinter Kristensen
  14. David Mortan Grøne Hammer
  15. Mathias Wulff Svendsen
  16. Jes Møllegård Hansen
  17. Jonas Malte Hinchely
  18. Rune Sostack Clausen
  19. Anders Busch
  20. Kristine Vitting Klinkby Knudsen


The examination form is oral exam with preparation. When it is your turn for examination, you will draw a question. The list of questions can be found below. Then you will be placed alone in a preparation room. You will have approximately 25-30 minutes of preparation time and you are allowed to use any material that you are bringing yourself.

After the preparation time, the actual exam takes place. This part also lasts approximately 25-30 minutes. You should start by presenting material related to the question 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 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 examinator and the censor, 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 as well as discussion between examinator and censor about the grade is included in the 25-30 minutes, so do not count on more than 15 minutes for your own presentation.

Some of the questions below are very broad, so you must select the material you choose to cover. 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. For most questions, it is natural to first sketch the algorithm or data structure and then present essential elements of the analysis. In most cases, a complete treatment of the analysis is the harder part of the question, but will therefore also enable you to demonstrate the best understanding of the material.

On the other hand, some of the questions are fairly narrow. If you think you have too little material, you are welcome to continue with material from a related question.


The curriculum in the course consists of all the literature and exercises referenced on the weekly notes. You can rely on that you will only be examined in the parts of the material discussed at lectures and discussion sections.

Though it will not be a something that you will be examined in directly, you are of course expected to know topics from courses that are prerequisites for this course.

With regards to the material in the book other than exercises, we have covered the following (Section 0 refers to the first part of each chapter before Section 1):

Note that I have decided not to include the material from Chapters 13 and 15 in the curriculum.


  1. Convex Hull
  2. Line Segment Intersection
  3. Triangulation
  4. Randomized Linear Programming
  5. Kd-Trees
  6. Range Trees
  7. Point Location via Trapezoidal Maps
  8. Voronoi Diagrams
  9. Interval Trees
  10. Priority Search Trees
  11. Segment Trees
  12. Binary Space Partitions
  13. Quadtrees

Last modified: Mon Jan 11 22:15:08 CET 2016
Kim Skak Larsen (kslarsen@imada.sdu.dk)