582603 Advanced Data Structures (4 cr, 2 cu)
News
- There is an extra separate exam (not shown in the official list) on Tuesday 5.6 16-20 A111. Contact lecturers if you plan to attend. After that the next scheduled separate exam is on Tuesday 14.8. 16-20 A111.
- Results.
Level
The course is an elective Master level course suitable for Algorithms sub-programme.
Prerequisites
Course Design of Algorithms or equivalent knowledge is required. In general, some maturity in algorithmic and mathematical thinking is expected.
Organizers
News
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.
Schedule
| Wk | Date | Type | Topics | Notes |
|---|---|---|---|---|
| 11 | WED 14.3 | Lecture | Administration, Lowest Common Ancestor (LCA) structures | Intro to LCA |
| 12 | MON 19.3 | Study group session | LCA structures | Read LCA revisited article |
| 12 | WED 21.3 | Exercises | Exercises on LCA | Exercise sheet |
| 12 | WED 21.3 | Lecture | Perfect Hashing - part I | Dictionary problem, Hash table, FKS scheme |
| 13 | MON 26.3 | Study group session | FKS scheme | Follow instructions for FKS scheme study group |
| 13 | WED 28.3 | Exercises | Exercises on Perfect Hashing | Exercise sheet |
| 13 | WED 28.3 | Lecture | Perfect Hashing - part II | Hash table, Two-choice hashing |
| 14 | MON 2.4 | Study group session | Perfect Hashing - part II | Follow instructions for Two-choice hashing study group |
| 14 | WED 4.4 | Exercises | Exercises | Exercise sheet |
| 14 | WED 28.3 | Lecture | van Emde Boas tree | vEB tree |
| 14-15 | THU 5.4 - WED 11.4 | - | Eastern holiday | |
| 16 | MON 16.4 | Study group session | van Emde Boas tree | Follow instructions for vEB tree study group |
| 16 | WED 18.4 | Exercises | Exercises on vEB tree | Exercise sheet |
| 16 | WED 18.4 | Lecture | Data structures on memory hierarchies | An introduction to cache-oblivious data structures, Basic cache-oblivious data structures, Funnelsort |
| 17 | MON 23.4 | Study group session | Data structures on memory hierarchies | Cache-oblivious study group |
| 17 | WED 25.4 | Exercise | Exercises | Exercise sheet |
| 17 | WED 25.4 | Lecture+presentations | Project work presentations | |
| 18 | Mon 30.4 | EXAM 9:00-12:00 A111 |
Veli Mäkinen