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 in M-II and Wednesdays in M-III 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:
- Union find a transpozícia matice (slides)
- Scapegoat stromy (slides)
- (a,b)-stromy (slides)
- Splay stromy (slides)
- Haldy (slides, slides 2)
- 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?
- Have a look at this: solution of HW1; it's slow... what is wrong with it?
- NO LECTURE ON 4. DEC !!
Homework
- Homework #1 – due 22.10.
- Bonus homework #1 – due 29.10.
- Homework #2 – due 6.11.
- Homework #3 – due 19.11.
- Homework #4 – due
11.12.; EDIT: extended to 17.12. Instead of the old ksp address, the input files are now here:- Covid genome (30KB)
- The whole Shakespeare work (4.8MB)
- Human chromosome 21 (46MB; it's the shortest one)
- Homework #5 – due 31.12.; instead of the old links in the pdf, SH.txt is the Shakespeare corpus above; for BWT, you can use your own solution to HW4, or use this code
- Bonus homework #2 – due 31.12. - EDIT: this is the correct link
All deadlines are until 8:00 in the morning, i.e. before the lecture. Submission by email.
Points
| radix | deque | hash | bwt | wavelet | bonus 1 | bonus 2 | total | |
|---|---|---|---|---|---|---|---|---|
| Max points | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 15(+4) |
| Ailin Xie | 0.5 | 0.5 | – | – | – | – | – | 1 |
| Belák Tomáš | 2 | 3 | 2 | 3 | 2.5 | 0.5 | – | 13 |
| Caban Jakub | – | 1 | – | – | – | – | – | 1 |
| Cingel Valter | 3 | 3 | 3 | 3 | 3 | – | – | 15 |
| Gáborik Lukáš | 2.5 | 3 | 3 | 3 | 2.5 | 0.5 | – | 14.5 |
| Haščík Alex | 3 | 2 | – | – | – | – | – | 5 |
| Heldák Lukáš | 2.5 | 2 | 3 | 3 | – | 0.5 | – | 11 |
| Hlaváč Vincent | 3 | 3 | 3 | 3 | 3 | – | – | 15 |
| Horňáček Lukáš | 3 | 3 | 2.5 | 2 | 2 | 1 | – | 13.5 |
| Chutňáková Gabriela | 2.5 | 1.5 | 3 | 2.5 | 3 | – | 0.5 | 13 |
| Jaremčuková Paulína | – | 1 | – | – | – | – | – | 1 |
| Kajan Marek | 1.5 | 3 | 2.5 | – | 0.5 | – | ||
| Kamas Ján | 2 | 2 | 3 | 3 | 2.5 | – | – | 12.5 |
| Kica Anton | 2.5 | 1 | 2.5 | – | 2 | 1 | – | 9 |
| Koleková Terézia | 2 | 2 | 2.5 | 3 | 1.5 | 0.5 | 0 | 11.5 |
| Koseček Filip | 3 | 3 | 3 | 3 | 3 | 0.5 | – | 15.5 |
| Košovský Martin | 3 | 2 | 2 | 3 | 1 | 1.5 | – | 12.5 |
| Kreutzová Olívia | 0.5 | 1.5 | 2 | 3 | – | 1 | – | 8 |
| Krošlák Martin | 3 | 2 | – | 3 | – | 1 | – | 9 |
| Lopaška Adam | 3 | 3 | 3 | 2.5 | 2 | 0.5 | – | 14 |
| Man František | 3 | 1.5 | 0.5 | 3 | 1.5 | – | – | 9.5 |
| Michalovič Marek | 3 | 3 | 3 | 3 | 3 | 1 | 2 | 18 |
| Mok Matej | 3 | 3 | 3 | 3 | 2 | 1.5 | 1 | 16.5 |
| Novota Matej | 3 | 3 | – | – | – | – | – | 6 |
| Pásztorová Emma | 3 | – | 3 | 2 | 1 | – | ||
| Petráni Radoslav | 3 | 2.5 | 2.5 | 3 | 1.5 | 0.5 | 13 | |
| Pitoňák Dávid | 2 | 2 | 2.5 | 3 | 3 | 0.5 | – | 13 |
| Skubeňová Zuzana | 2.5 | 2.5 | 1 | 3 | 1 | – | – | 10 |
| Štauder Matej | 1 | 3 | 1 | – | 1 | |||
| Tarhovický Jakub | 3 | 2.5 | – | 3 | – | – | – | 8.5 |
| Vita Dennis | 3 | 3 | 3 | 3 | 3 | 0.5 | – | 15.5 |
| Zelinka Andrej |
Grading: 15 points for HW + 15 points from final exam. To pass, you need at least 7.5points from homeworks.
| Points | Grade |
|---|---|
| 30 — 26 points | A |
| 25.5 — 22 points | B |
| 21.5 — 17 points | C |
| 16.5 — 13 points | D |
| 12.5 — 9 points | E |
| < 9 points | 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