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: Tuesdays and Wednesdays in M-I at 8:10 am.
Contact: kuko[at-sign]ksp[dot]sk
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:
- Union find a transpozícia matice (slides)
- Scapegoat stromy (slides)
- (a,b)-stromy (slides)
- Splay stromy (slides)
- Haldy (slides, slides 2)
- Radix halda / Radix heap
- Geometria (Kd-stromy a rozsahové stromy)
- Perzistentné štruktúry
- Hešovanie (slides)
- Bloomove a podielové filtre (slides)
- Optimalizácia
- LCA a RMQ
- Sufixové stromy (slides) / Suffix trees
- Sufixové polia (slides) / Suffix arrays
- BWT a FM-index (slides, example) / BWT and FM-index
- Úsporné DŠ (rank&select, wavelet stromy, RRR)
- Externé DŠ (sekvenčná halda, fraktálové stromy a LSM)
Announcements
- Have a look at this: code and measurements; what is wrong with them?
Homework
- Homework #1 – due 24.10.
- Bonus homework #1 – due 24.10.
- Homework #2 – due 7.11.
- Homework #3 – due 21.11.
- Homework #4 – due 10.12.
- Homework #5 – due 6.1.
All dates are until 8:00 in the morning, i.e. before the lecture. Submission by email.
Points
| heap | deque | hash/geom | bwt | wavelet | bonus | total | |
|---|---|---|---|---|---|---|---|
| Max | 3 | 3 | 3 | 3 | 3 | 15 | |
| Ďurdina Michal | 3 | 1 | 3 | 3 | 2 | 1 | 13 |
| Farnbauer Michal | — | 2.5 | 3 | — | — | 5.5 | |
| Hladíková Hana | 1 | 1 | 0 | 0.5 | 0.5 | 3 | |
| Husárová Tatiana | 3 | 2 | 3 | 0.5 | — | 8.5 | |
| Jurčák Matej | 3 | 2 | 3 | — | — | 8 | |
| Kajan Marek | — | 2 | — | — | — | 2 | |
| Kováčiková Jana Viktória | 1.5 | 1 | — | 3 | 0.5 | 6 | |
| Lichmanová Júlia | 3 | 2 | 2.5 | 3 | 1 | 11.5 | |
| Pásztor Dávid | 3 | 3 | — | — | — | 1 | 7 |
| Pisoňová Karolína | 3 | 2 | 1 | — | 2 | 8 | |
| Priner Ján | 3 | 3 | 2.5 | 3 | — | 11.5 | |
| Radošinská Nikola | 3 | 3 | 2.5 | 1 | — | 9.5 | |
| Ravinger Andrej | 3 | 3 | 3 | 3 | 3 | 0.5 | 15.5 |
| Řehulka Erik | 3 | 3 | 2.5 | 3 | 2 | 13.5 | |
| Revúcky Samuel | 2 | 2 | 2.5 | 3 | — | 9.5 | |
| Sásiková Kristína | 1.5 | 1.5 | 0 | 2.5 | 5.5 | ||
| Tardiou Gabrielle | |||||||
| Vavrek Samuel | — | 1.5 | 3 | — | — | 4.5 | |
| Verplanke Rick | 0.5 | 0 | |||||
| Vnenčáková Patrícia | 3 | 2 | 3 | — | — | 8 | |
| Zelinka Andrej | — |
Hodnotenie: 15 bodov za D.Ú. + 15 bodov zo skúšky.
| Počet bodov | Hodnotenie |
|---|---|
| 30 — 26 bodov | A |
| 25.5 — 22 bodov | B |
| 21.5 — 17 bodov | C |
| 16.5 — 13 bodov | D |
| 12.5 — 9 bodov | E |
| < 9 bodov | Fx |
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
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
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
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
Rank/Select, Wavelet trees
- Úsporné DŠ (poznámky)
- Demaine – Lecture 17 (video)
- Navarro – Wavelet Trees for All
- Clause, Navarro – Practical Rank/Select Queries over Arbitrary Sequences
- Mäkinen, Navarro – Implicit Compression Boosting with Applications to Self-Indexing
- Grabowski, Raniszewski – Rank and select: Another lesson learned
External data structures
Stream algorithms
- HyperLogLog vizualizácia
- Heule et al. – HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
- Xiao et al. – Better with Fewer Bits – Improving the Performance of Cardinality Estimation of Large Data Streams (kód)
- Datar et al. – Maintaining stream statistics over sliding windows