Cvičení z Datových struktur I
čtvrtek od 10:40 v S7, ZS 25/26
Ke své přednášce Datové struktury I povedu cvičení, na kterém se zaměříme na procvičení a hlubší porozumění probírané látky formou řešení příkladů a diskusí o domácích úkolech. Běžně budeme procvičovat látku z poslední přednášky.
Pokud máte nějaký dotaz, pište na vesely (obmotané a) iuuk.mff.cuni.cz, případně se zeptejte při/po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Po domluvě mohu poskytnout konzultace.
Všechny důležité informace, včetně podmínek zápočtu, jsou na stránce přednášky. Nejdůležitější odkazy:
- Úkoly se odevzdávají v recodexu
- Zadání úkolů a šablony zdrojových kódů jsou v repozitáři na GitLabu
- Vzorové řešení experimentálního úkolu (pro nafukovací pole)
Co jsme dělali
| 2. 10. | Opakování Óčkové notace a binárních vyhledávacích stromů (BVS). Amortizace: iterovaná operace následníka na BVS a nafukovací pole jinak. Úlohy na cvičení (prošli jsme první tři, čtvrtý příklad bude příště). |
| 9. 10. | Zaskočil Petr Chmel: dynamické pole a Splay stromy. Úlohy na cvičení: vyřešeny první čtyři a kus příkladu. (řešení) |
| 16. 10. | Vysvětlení experimentálního úkolu se Splay stromy. Příklady na splay stromy, ze kterých jsme probrali první tři. |
| 23. 10. | (a,b)-stromy. Příklady, ze kterých jsme probrali hlavně druhý, třetí a pátý (join). |
| 30. 10. | Cvičení odpadá. Bude zadán experimentální úkol na (a,b)-stromy. |
| 6. 11. | I/O složitost. Příklady, ze kterých jsme probrali první tři. |
| 13. 11. | Opakování pravděpodobnosti a hešovací funkce univerzální a k-nezávislé. Příklady, ze kterých jsme probrali první čtyři a šestý. |
| 20. 11. | Hešovací funkce univerzální a k-nezávislé, tabelace a řešení kolizí s kukačkou. Příklady, ze kterých jsme probrali první čtyři. |
| 27. 11. | Hešování a mazání: Lineární přidávání a počítací Bloomův filtr. Rabinův-Karpův algoritmus pro vyhledávání v řetězci. Příklady, ze kterých jsme probrali první čtyři. |
| 4. 12. | Sufixové stromy a sufixová(+LCP) pole: převody stromu na pole a zpět. Opakování vyhledávání jehly a nejdelšího opakujícího se podslova. Počítání k-gramů (k-merů, tedy podřetězců délky k) a hledání nejdelšího společného podslova dvou řetězců. |
| 11. 12. | Burrowsova-Wheelerova transformace (BWT) a její použití vyhledávání v řetězci: vypočet BWT ze sufixového pole, LF mapping, použití na inverzi BWT, výpočet sufixového pole z BWT, implementace LF mappingu (stručně). Na závěr stručně rychlejší vyhledávání jehly v sufixovém poli pomocí LCP pole. |
| 18. 12. | Geometrické datové struktury postavené nad množinou bodů. Konkrétně quadtree (hloubka, počet vrcholů, chování ve více dimenzích a zlepšení kompresí cest; rozebrali jsme též heuristiku na hledání nejbližšího souseda, čili Nearest Neighbor query) a range trees, u kterých jsme zrychlili counting query (počítání bodů v obdélníku) o logaritmus pomocí techniky fractional cascading, kterou lze použít pro vyhledávání ve více setříděných polí najednou. |
| 8. 1. | Paralelní datové struktury: zámky, atomické operace (CAS, LL/SC), bezzámkové datové struktury. Konkrétně jsme navrhli hešovací tabulku se zamykáním buněk, která umožňuje přehešování. Dále jsme probrali bezzámkovou implementaci fronty pomocí CAS (bez řešení problému ABA). |