263-4312-00L  Advanced Data Structures

SemesterFrühjahrssemester 2018
DozierendeP. Uznanski
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch



Lehrveranstaltungen

NummerTitelUmfangDozierende
263-4312-00 VAdvanced Data Structures2 Std.
Mo10:15-12:00CHN E 42 »
P. Uznanski
263-4312-00 UAdvanced Data Structures2 Std.
Di15:15-17:00LFW E 13 »
P. Uznanski

Katalogdaten

KurzbeschreibungData 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.
LernzielLearning 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.
InhaltThis 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
Voraussetzungen / BesonderesThis 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.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte5 KP
PrüfendeP. Uznanski
FormSessionsprüfung
PrüfungsspracheEnglisch
RepetitionDie Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodusschriftlich 180 Minuten
Zusatzinformation zum PrüfungsmodusDuring 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.
Hilfsmittel schriftlichOpen book examination - any written aid allowed.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.

Lernmaterialien

 
HauptlinkInformation
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

StudiengangBereichTyp
CAS in InformatikFokusfächer und WahlfächerWInformation
Informatik MasterWahlfächer der Vertiefung in Theoretical Computer ScienceWInformation
Informatik MasterWahlfächer der Vertiefung General StudiesWInformation