The exam will take place in IMADA's seminar room and U49E.

Lists are available in the secretaries' office. Here, you must sign up for a specific slot in the sequence of students to be examined. Please do so as soon as possible after the lists become available. Note that you cannot calculate an 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.

After the preparation time, the actual exam
takes place. This part also lasts approximately
30 minutes. 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, though some transparencies will be available (see below).

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 30 minutes, so do not count on more than 10-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.

- Convex Hull
- Line Segment Intersection
- Triangulation
- Randomized Linear Programming
- Kd-Trees
- Range Trees
- Point Location via Trapezoidal Maps
- Voronoi Diagrams
- Interval Trees
- Priority Search Trees
- Segment Trees
- Binary Space Partitions
- Quadtrees

- Figure 3.3, page 50.
- Figures 5.8 and 5.9, page 114.

Last modified: Thu May 31 11:09:28 CEST 2007 Kim Skak Larsen (kslarsen@imada.sdu.dk)