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?
Homework
- Homework #1 – due 22.10.
- Bonus homework #1 – due 29.10.
- Homework #2 – due 6.11.
- Homework #3 – due 19.11.
All deadlines are until 8:00 in the morning, i.e. before the lecture. Submission by email.
Points
| Max | 3 | 3 | 3 | 3 | 3 | 15 | |
| Ailin Xie | 0.5 | ||||||
| Belák Tomáš | 3 | ||||||
| Caban Jakub | – | 1 | |||||
| Cingel Valter | 3 | ||||||
| Gáborik Lukáš | 3 | ||||||
| Haščík Alex | |||||||
| Heldák Lukáš | |||||||
| Hlaváč Vincent | |||||||
| Horňáček Lukáš | |||||||
| Chutňáková Gabriela | 1.5 | ||||||
| Jaremčuková Paulína | |||||||
| Kajan Marek | - | ||||||
| Kamas Ján | |||||||
| Kica Anton | |||||||
| Koleková Terézia | |||||||
| Koseček Filip | |||||||
| Košovský Martin | |||||||
| Kreutzová Olívia | |||||||
| Krošlák Martin | |||||||
| Lopaška Adam | |||||||
| Man Václav | |||||||
| Michalovič Marek | |||||||
| Mok Matej | |||||||
| Novota Matej | |||||||
| Pásztorová Emma | |||||||
| Petráni Radoslav | |||||||
| Pitoňák Dávid | |||||||
| Skubeňová Zuzana | |||||||
| Štauder Matej | |||||||
| Tarhovický Jakub | |||||||
| Vita Dennis | |||||||
| Zelinka Andrej | - |
Grading: 15 points for HW + 15 points from final exam.
| 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