There is project in a few parts. This project is obligatory and is evaluated as a whole, resulting in either pass or fail. A pass is required to be qualified for the oral exam. More information on the project can be found on the project page.

The rest of this page is about the oral exam.

Time and place

The exam takes place on Friday, January 6, 2017 in U11.

The first student draws a question and starts preparation at 9:00.


  1. Simone Inger Knudsen
  2. Manuel Dal Mas
  3. Peter Severin Rasmussen
  4. Svend Elberg Knudsen
  5. Jon Kingo Christensen
  6. Henrik Schulz

Even though the expected total examination time per student (excluding preparation time) is 30 minutes (see below), it is not possible to calculate the exact examination time from the placement on the list, since students earlier on the list may not show up. Thus, students are expected to show up plenty early. In principle, all students who are taking the exam on a particular date are supposed to show up when the examination starts, i.e., at the time the first student is scheduled. This is partly because of the way external examiners are paid, which is by the number of students who show up for examination. For this particular exam, we do not expect many (probably not any) no-shows, so showing up an hour before the estimated time of the exam is safe (you never have to show up before the scheduled starting time of the first student, of course), i.e., if T is your calculated preparation starting time, show up no later than max(T - 1 hour, 9:00).


This an oral exam. When it is your turn for examination, you will draw what is here referred to as a question. This is simply a topic from the course. 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 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 25-30 minutes that we aim for.

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 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 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 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 very poor presentation of the harder material. For most questions, it is natural to first sketch the data structure and then present essential elements of the analysis. To obtain the best result, you should spend most of your time on the analysis.

When two data structures are mentioned in the question, you can still select your material freely. As an example, it is fine to talk only about universal hashing or only about perfect hashing (I would recommend the latter), and this will not in itself limit your grade. We might of course still ask you questions about material that you have decided to skip. Note that for the question "disjoint sets", you should be particularly brief when discussing the structure, since this is really material from an introductory algorithms and data structures course. So, here you should to an even larger extent focus on the amortized analysis.


The curriculum in the course consists of all the material on the literature page at the end of the course plus all the weekly notes. Additionally, you can rely on that you will only be examined in the parts of the material that have been discussed at lectures and exercises. As examples of this, I will not ask questions about full persistency, and I will not ask questions about the variance in the search time for skip lists.


  1. leftists heaps and skew heaps
  2. skip lists
  3. scapegoat trees
  4. universal and perfect hashing
  5. disjoint sets with backtracking
  6. making data structures partially persistent
  7. cuckoo hashing
  8. van Emde Boas trees
  9. X- and Y-fast tries
  10. splay trees
  11. the level ancestor problem
  12. Fibonacci heaps

Last modified: Sat Jan 21 09:45:11 CET 2017
Kim Skak Larsen (kslarsen@imada.sdu.dk)