Datové struktury 1: cvičení

Vítejte na stránkách cvičení k předmětu Datové struktury 1, které přednáší Jiří Fink. Jsme rozvrženi na úterý 14:00 v místnosti S1 (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 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. Odkazy platily v roce 2021/2022, možná se letos něco změní.

Obsah cvičení

1. 2022-10-05: Regulární haldy, nějaké amortizace.
2. 2022-10-12: Amortizovaná analýza.
3. 2022-10-19: Random příklady na vyhledávací stromy.
4. 2022-10-26: Snažili jsme se pochopit důkaz logaritmické amortizované složitosti splay stromů.
5. 2022-11-01: (a, b)-stromy. Rešení.
6. 2022-11-08: Cache-oblivious analýza známých algoritmů.
7. 2022-11-15: Cachování z pohledu teorie a online algoritmy <3.
8. 2022-11-22: Kukačkové hashování.
9. 2022-11-29: Hashování z lineární kongruence. FKS.
10. 2022-12-06: Konečně FKS, tabulkové hashování.
11. 2022-12-13: Finále hashování, izolační lemma.