Selected Topics in Data Structures
Syllabus:
- Amortized analysis
- Priority queues
- Binary search trees
- Hashing
- RMQ and LCA
- Sufix trees and arrays
- Succinct data structures
- BWT, FM-index
- DS for external memory
- Streaming DS
- Persistent and functional DS
Schedule: Wednesdays in M-I and Thursdays in M-II at 8:10 am.
Contact: jakub.kovac47[at-sign]gmail[dot]com
Materials:
- Bývalá stránka predmetu VPDŠ
- Erik Demaine – Advanced Data Structures
- Kozen – The Design and Analysis of Algorithms
- Cormen, Leiserson, Rivest, Stein – Introduction to Algorithms
Lecture notes and slides:
- Beta verzia skrípt (22.9.2026)
- Union find a transpozícia matice: poznámky, slidy, skriptá
- Binomiálna halda: poznámky, slidy, skriptá
- Fibonacciho halda: poznámky, slidy, skriptá
- Radixová halda: Radix heap (EN), skriptá
- Scapegoat stromy: poznámky, slidy, skriptá
- Splay stromy: poznámky, slidy, skriptá
- Geometria (Kd-stromy a rozsahové stromy)
- Perzistentné štruktúry
- Hešovanie (slides)
- Bloomove a podielové filtre (slides)
- Optimalizácia
- LCA a RMQ: poznámky, skriptá
- Sufixové stromy: poznámky, slidy, Suffix trees (EN), skriptá
- Sufixové polia: poznámky, slidy, Suffix arrays (EN), skriptá
- BWT a FM-index: poznámky, slidy, example, BWT and FM-index (EN), skriptá
- Úsporné DŠ: poznámky, rank&select, wavelet stromy, RRR, skriptá
- Externé DŠ: poznámky, sekvenčná halda, fraktálové stromy a LSM, skriptá
Announcements
Homework
All deadlines are until 8:00 in the morning, i.e. before the lecture. Submission by email.
Lectures
Intro
Amortised analysis, vectors
Scapegoat trees & Splay trees
- Scapegoat trees - poznámky, video prednášky
- (a,b)-trees - poznámky, video prednášky
- Průvodce labyrintem algoritmů – kapitola 9
- Splay stromy (poznámky)
- Sleator, Tarjan – Self-Adjusting Binary Search Trees
- Jeff Erickson – Scapegoat and Splay Trees
- Kozen – kap. 12 Splay Trees
- Chalermsook et al. – Self-Adjusting Binary Search Trees: What Makes Them Tick?
Geometry
Persistent data structures
Hešovanie
- Hešovanie – teória (poznámky), prax (slides)
- Demaine – Lecture 10 (video)
- Kulukundis – Googlovské heš-tabuľky (video)
- Kulukundis – Googlovské heš-tabuľky 2 (video)
- Bronson, Shi – Facebookovské heš-tabuľky
- Hash flooding
- Pagh, Rodler – Cuckoo Hashing
- Mitzenmacher – kap. 13.3 Universal hashing
- Chung et al. – Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream
Bloomove a podielové filtre
Optimalizácia
- Godbolt – What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid
- Ormrod – The strange details of std::string at Facebook
- Alexandrescu – Optimization Tips - Mo' Hustle Mo' Problems
- Alexandrescu – Fastware
- Khuong, Morin – Array layouts for comparison-based searching
- Sanders, Winkel – Super Scalar Sample Sort
LCA a RMQ
Suffix trees and arrays
- Sufixové stromy (poznámky)
- slides 1, slides 2
- Gusfield – kap. 5 Introduction to Suffix Trees
- Gusfield – kap. 7 First Applications of Suffix Trees
- Kärkkäinen, Sanders – Simple Linear Work Suffix Array Construction
- Manzini, Ferragina – Engineering a Lightweight Suffix Array Construction Algorithm
- Puglisi, Smyth, Turpin – A Taxonomy of Suffix Array Constrution Algorithms
BWT a FM-index
- BWT a FM-index (poznámky)
- Ferragina, Manzini – Opportunistic Data Structures with Applications
- Ferragina et al. – Compressed Text Indexes: From Theory to Practice!
- Navarro, Mäkinen – Compressed Full-Text Indexes
- Grabowski et al. – FM-index for dummies
- Ferrada et al. – Hybrid Indexing Revisited
- Manzini – An Analysis of the Burrows-Wheeler Transform