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

Students are examined in a fixed sequence.

The first student draws a question at 8:30.

Note that you cannot calculate a precise 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 (the external examiner is not being paid for sitting and waiting for students).

After the preparation time, the actual exam takes place.
This part also lasts approximately 25-30 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 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. 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 10-15 minutes for your own presentation.

In general, the questions are broad enough that 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. In most cases, a complete treatment of the analysis and proofs is the harder part of the question, but will therefore also enable you to demonstrate the best understanding of the material.

You may give your presentation in Danish or English. In our experience, if your native language is Danish, you do best by choosing that.

- List accessing with emphasis on TIMESTAMP
- Randomized algorithms for list accessing
- Upper bounds for marking algorithms and lower bounds for paging in general
- The paging algorithm RAND
- The paging algorithm MARK
- The relative worst order ratio for paging: definitions and look-ahead
- The relative worst order ratio for paging: RLRU
- K-server algorithms on the line
- Memoryless paging algorithms with emphasis on mixed algorithms
- Using Yao's principle to prove a lower bound on randomized paging
- The algorithm GREEDY for the identical and the restricted machine model for load balancing

Last modified: Thu Jan 6 11:44:42 CET 2011 Kim Skak Larsen (kslarsen@imada.sdu.dk)