Selected Topics in Data Structures - NTIN110

• Title: Vybrané kapitoly z datových struktur
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2020
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Additional information: http://mj.ucw.cz/vyuka/vkds/
• Note: you can enroll for the course repeatedly
• Guarantor: Mgr. Martin Mareš, Ph.D.
• Teacher(s): Mgr. Martin Mareš, Ph.D.; Mgr. Lukáš Ondráček
• Class: Informatika Mgr. - Teoretická informatika
• Classification: Informatics > Theoretical Computer Science

Annotation

English

The course covers more advanced topics from the area of data structures. It is a loose continuation of the basic courses Data structures I and II.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (07.05.2019)

Czech

Obsahem této přednášky jsou pokročilé partie z teorie datových struktur a algoritmů. Přednáška volně navazuje na Datové struktury I a II a dále jejich látku rozšiřuje. Každý běh bude věnován jinému tématu.

Last update: Klimošová Tereza, Mgr., Ph.D. (05.05.2020)

Course completion requirements

English

Oral examination, possibly in distance form.

Last update: Mareš Martin, Mgr., Ph.D. (24.09.2020)

Czech

Ústní zkouška, může být vedena distančně.

Last update: Mareš Martin, Mgr., Ph.D. (24.09.2020)

Literature

English

• Mehta, D. P., Sahni, S.: Handbook of data structures, Chapman & Hall, 2005

• Papers on relevant topics from proceedings and journals SODA, JACM, J. Algorithms, ICALP, FOCS, STOC

Last update: Kynčl Jan, doc. Mgr., Ph.D. (07.05.2019)

Czech

• Mehta, D. P., Sahni, S.: Handbook of data structures, Chapman & Hall, 2005

• Články týkající se zadaných témat z konferencí a časopisů SODA, JACM, J. Algorithms, ICALP, FOCS, STOC

Last update: Kynčl Jan, doc. Mgr., Ph.D. (07.05.2019)

Requirements to the exam

English

It is necessary to understand the theory presented at the lecture and to be able to apply it.

Last update: Mareš Martin, Mgr., Ph.D. (15.10.2019)

Czech

Ke zkoušce je nutné rozumět teorii z přednášky a být schopen ji aplikovat.

Last update: Mareš Martin, Mgr., Ph.D. (15.10.2019)

Syllabus

English

• cache-oblivious sorting and dynamic data structures

• persistent data structures

• data structures for integers

• lower bounds

• succinct data structures

• data structures in sub-linear space

Last update: Mareš Martin, Mgr., Ph.D. (30.04.2020)

Czech

• cache-oblivious třídění a dynamické datové struktury

• persistentní datové struktury

• datové struktury pro práci s celými čísly

• dolní odhady

• úsporné (succinct) datové struktury

• datové struktury v sublineárním prostoru

Last update: Mareš Martin, Mgr., Ph.D. (30.04.2020)