University of Helsinki Department of Computer Science

Department of Computer Science

Department information


582603 Advanced Data Structures (4 cr, 2 cu)



The course is an elective Master level course suitable for Algorithms sub-programme.


Course Design of Algorithms or equivalent knowledge is required. In general, some maturity in algorithmic and mathematical thinking is expected.


Juha Kärkkäinen
Veli Mäkinen


Lectures: 14.03.-25.04. WED 16-18 C220

Study group session: 19.03.-23.04. MON 10-12 B119
Exercises: 21.03.-25.04. WED 12-14 C221

Description and study goals

The course covers selected topics on advanced data structures, e.g. perfect hashing, van Emde Boas trees, lowest common ancestor queries, and data structures on memory hierarchies. The topics are chosen to introduce the key techniques in the design and analysis of state-of-the-art data structures. The aim is to obtain a deep understanding of a few representative structures, so that the obtained knowledge is useful in the further studies on the topic.

Study method

The course will be realized as study group work. Lectures introduce the background and fundamentals, i.e. they give the "big picture". Study group sessions go into details: The weeks topic is separated into several subtopics, each group of students focuses on different subtopic, and at study group sessions the information is shared by teaching each others. Exercises and small project work evaluate the knowledge obtained.

Getting the grade

Active participation to the study group sessions is compulsory, as well as project work. The course exam will be held on Monday 30th April from 9.00 to 12.00, giving 40 points at the maximum. Exercises and project work give at the maximum 4+4=8 extra points (exercises 25% done -> 1p, 45% done -> 2p, 65% done -> 3p, 85% done->4p). The grading is based on the total points achieved. The extra points are valid in the later exams only in the case of active participation to the compulsory sessions.

Lecture material

All lecture material will be collected to course Wikipedia (ask lecturers for password).

Project work

Doing one project work during the course is compulsory.

The topics are shared continuously during the course, on lectures and on study group sessions. Project work will typically consist of reading an article, writing summary to the course Wikipedia, and giving a short presentation of the work.


Wk Date TypeTopicsNotes
11WED 14.3LectureAdministration, Lowest Common Ancestor (LCA) structuresIntro to LCA
12MON 19.3Study group sessionLCA structuresRead LCA revisited article
12WED 21.3ExercisesExercises on LCAExercise sheet
12WED 21.3LecturePerfect Hashing - part IDictionary problem, Hash table, FKS scheme
13MON 26.3Study group session FKS schemeFollow instructions for FKS scheme study group
13WED 28.3ExercisesExercises on Perfect HashingExercise sheet
13WED 28.3LecturePerfect Hashing - part IIHash table, Two-choice hashing
14MON 2.4Study group sessionPerfect Hashing - part IIFollow instructions for Two-choice hashing study group
14WED 4.4ExercisesExercisesExercise sheet
14WED 28.3Lecturevan Emde Boas treevEB tree
14-15THU 5.4 - WED 11.4-Eastern holiday
16MON 16.4Study group sessionvan Emde Boas treeFollow instructions for vEB tree study group
16WED 18.4ExercisesExercises on vEB treeExercise sheet
16WED 18.4LectureData structures on memory hierarchiesAn introduction to cache-oblivious data structures, Basic cache-oblivious data structures, Funnelsort
17MON 23.4Study group sessionData structures on memory hierarchiesCache-oblivious study group
17WED 25.4ExerciseExercisesExercise sheet
17WED 25.4Lecture+presentationsProject work presentations
18Mon 30.4EXAM 9:00-12:00 A111

Veli Mäkinen
Last updated 30.11.2006