Datové struktury 1

Vítejte na stránkách cvičení k předmětu Datové struktury I, které přednáší Michal Koucký. Jsme rozvrženi na pondělí 10:40 v místnosti S7 (plánek budovy).

Pokud máte pocit, že

• něčemu nerozumíte,
• nestíháte deadline (z jakéhokoliv důvodu),
• nemáte dost bodů na zápočet,
• nevíte něco, co byste měli vědět,
• jsem Vám neřekl něco, co bych Vám měl říct,
• bych měl něco (třeba sebe) vylepšit či změnit nebo
• Vám něco jiného brání v získání jedničky z tohohle předmětu,

Účast na cvičení je dobrovolná. Většinou budeme rozebírat, jak se měl řešit domácí úkol z předchozího týdne, jaké byly typické chyby, atd. Také si občas vyřešíme nějakou teoretickou úlohu (rozumějte důkazy), která by měla prohloubit Vaše znalosti.

Jak získat zápočet

Tyto informace už mnohem lépe než já sepsal Ondra Mička. Tl;dr každý týden budete něco programovat. Pravidla naleznete taktéž na stránkách Ondry Mičky.

Obsah cvičení

Třinácté cvičení - 2022/01/03

Pokusili jsme se pochopit první tři sekce z paperu o ledovcovém hashování.

Dvanácté cvičení - 2021/12/20

Konstrukce LCP pole. Worst-case dotaz pro kd-stromy. Zrychlení intervalového dotazu o jednu mocninu logaritmu.

Jedenácté cvičení - 2021/12/13

Optimální počet hashovacích funkcí pro bloom filter. Jak zrychlit vyhledávání vzorku v suffixovém poli. Range minimum query (RMQ).

Desáté cvičení - 2021/12/06

Hashování řetězců. Rabin-Karpův algoritmus.

Deváté cvičení - 2021/11/29

Vlastnosti systémů nezávislých či univerzálních hashovacích funkci.

Osmé cvičení - 2021/11/22

Perfektní hashování. Narozeninový paradox. Kukaččí hashování.

Sedmé cvičení - 2021/11/15

Pokusil jsem se vysvětlit, proč je LRU špatná strategie, ledaže mu dáme větší cache než optimálnímu algoritmu (tj. Sleator-Tarjanova věta).

Šesté cvičení - 2021/11/08

Pověděli jsme si, jak udělat cache-oblivious analýzu MergeSortu.

Páté cvičení - 2021/11/01

Je velmi nepovinné, neboť odpadá předcházející přednáška. Neplánuji říct nic, co byste nevěděli.

Čtvrté cvičení - 2021/10/25

Vysvětlili jsme si alternativní definici (a,b)-stromů, které si ukládají klíče ve vnitřních vrcholech a listy mají prázdné. Tuto implementaci budete potřebovat v domácích úkolech souvisejících s (a,b)-stromy. Více informací najdete ve skriptech.

Také jsme si pověděli o častých chybách v domácím úkolu splay_operation.

Třetí cvičení - 2021/10/18

Pověděli jsme si o alternativní implementaci vkládání a mazání prvků ze Splay stromu. Více informací najdete ve skriptech na straně 9 v sekci Splitting and joining.

Druhé cvičení - 2021/10/11

Vysvětlili jsme si, co je to splay strom a proč je potřeba dělat dvojté rotace.

První cvičení - 2021/10/04

Vysvětlili jsme si pravidla pro získání zápočtu. Řešili jsme následující úlohy:

• Jak k natahovacímu poli přidat operaci mazání posledního prvku tak, aby taky mělo konstantní amortizovanou složitost?
• Dokázali jsme, že binární čítačka s operací inkrementace má konstantní amortizovanou složitost.
• Jak k natahovacímu poli přidat operaci přidání prvku na začátek, aby všechny operace měly konstantní amortizovanou složitost?
• To jsme předvedli dvěma způsoby. Jednak jsme to implementovali kruhovým polem (které jsme dále implementovali na obyčejném poli) a druhak jsme rozšířili natahovací pole z přednášky tak, aby mělo volné místo i na začátku.
• Předvedli jsme si, že binární čítačka podporující operace inkrementace a dekrementace nemá konstantní amortizované složitosti.