Extra Approved Reexam Event

For various reasons, it has been decided to hold an extraordinary reexam. The exam is oral and will take place June 6, 2023, starting at 8:30, in IMADA's Seminar Room. Details will be announced via itslearning.

Final Reexam Event

The final oral exam in the course will be January 17, 2023. Earlier I had announced that Rolf Fagerberg would teach the course in the Spring of 2023. However, that decision has been changed. Thus, there is currently no prediction as to when the course is taught again.

Next Reexam Event

The next oral exam in the course will be August 24, 2022. The project (if you have not completed it already) has deadline August 10, 2022, 23:55. The project is the same as for the regular exam. You turn in everything (part 1 and 2) at the same time via the itslearning entry for the course.

Important Notice Regarding Reexams

As all elective courses, this course is taught on an irregular schedule. Thus, you cannot rely on it running again next year. This is important wrt. possible reexam dates, should you need that. The first oral reexam will be held in August and your final attempt can be used in January next year. Specific dates will be announced later for the oral exam as well as for the project, which will have deadline some time earlier than the date for the oral exam.

There are two exam elements in this course:

• an oral exam, and
• a programming project.

You get one combined grade based on the two parts. The oral exam has highest weight.

Programming project

The programming project is in multiple parts with deadlines through the semester such that it is completed around the end of teaching.

Exam Project	Deadline
Part 1
Project description	Thursday, March 17, 2022, at 23:55
Part 2
Project description	Sunday, May 8, 2022, at 23:55

Oral exam

This exam has been allocated Wednesday and Thursday, June 8-9, 2022 in IMADA's Seminar Room.

More information will follow regarding the examination sequence. You will receive a mail later where I ask you if you have any wishes wrt. the actual examination time, and if you want to influence the decision, you need to respond fairly quickly. It's sufficient that you check mail daily, though.

Procedure

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, excluding communication devices.

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 you have about 12-13 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 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.

When two data structures are mentioned in the question, you can still select your material freely, 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, but that is no different from the rest of the curriculum. 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.

Curriculum

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, and only in the parts related to the data structures on the list of questions. 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.

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.

Questions

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

 

---