263-4312-00L Advanced Data Structures
| Semester | Spring Semester 2018 |
| Lecturers | P. Uznanski |
| Periodicity | yearly recurring course |
| Language of instruction | English |
Courses
| Number | Title | Hours | Lecturers | ||||
|---|---|---|---|---|---|---|---|
| 263-4312-00 V | Advanced Data Structures | 2 hrs |
| P. Uznanski | |||
| 263-4312-00 U | Advanced Data Structures | 2 hrs |
| P. Uznanski |
Catalogue data
| Abstract | Data structures play a central role in modern computer science and are essential building blocks in obtaining efficient algorithms. The course covers major results and research directions in data structures, that (mostly) have not yet made it into standard computer science curriculum. |
| Learning objective | Learning modern models of computation. Applying new algorithmic techniques to the construction of efficient data structures. Understanding techniques used in both lower- and upper- bound proofs on said data structures. |
| Content | This course will survey important developments in data structures that have not (yet) worked their way into the standard computer science curriculum. Though we will cover state of the art techniques, the presentation is relatively self-contained, and only assumes a basic undergraduate data structures course (e.g., knowledge of binary search trees). The course material includes (but is not exhausted by): - computation models and memory models - string indexing (suffix trees, suffix arrays) - search trees - static tree processing (Lowest Common Ancestor queries, Level Ancestry queries) - range queries on arrays (queries for minimal element in a given range) - integers-only data structures: how to sort integers in linear time, faster predecessor structures (van Emde Boas trees) - hashing - dynamic graphs connectivity |
| Prerequisites / Notice | This is a highly theoretical course. You should be comfortable with: - algorithms and data structures - probability Completing Algorithms, Probability, and Computing course (252-0209-00L) is a good indicator. |
Performance assessment
| Performance assessment information (valid until the course unit is held again) | |
Performance assessment as a semester course | |
| ECTS credits | 5 credits |
| Examiners | P. Uznanski |
| Type | session examination |
| Language of examination | English |
| Repetition | The performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling. |
| Mode of examination | written 180 minutes |
| Additional information on mode of examination | During the semester, bonus points can be developed through active presenting of the solutions at the exercise classes. Bonus point contribute extra to the points scored from the written exam. Obtaining highest grade purely from the exam is possible. |
| Written aids | Open book examination - any written aid allowed. |
| This information can be updated until the beginning of the semester; information on the examination timetable is binding. | |
Learning materials
| Main link | Information |
| Only public learning materials are listed. | |
Groups
| No information on groups available. |
Restrictions
| There are no additional restrictions for the registration. |
