Začali jsme s úvodem do předmětu a pravidly zápočtu. Dále jsme si zadali úkol tree_successor s deadlinem 17. 10. 2024 ve 23:59. Potom jsme řešili opakovací úlohy, vesměs jsme zvládli úlohy 1-3, na tabuli jsem poté naznačil řešení úloh 4-5, řešení úlohy 6 jsem naznačil vyloženě z rychlíku.

Podívali jsme se na amortizaci, zopakovali jsme si tři způsoby amortizace, a nakonec jsme řešili úlohy. První tři jsme si řekli, úlohy 4-5 jsem odbyl jen pár slovy.

Začali jsme se zadáním úkolu splay_operation s deadlinem 27. 10. 2024 ve 23:59. Pak jsme se věnovali líně vyvažovaným stromům a splay stromům. Připomněli jsme si dvojrotace, a jak se má splay implementovat. Při řešení úloh jsme pak zjistili jak zkonstruovat staticky optimální strom v kubickém čase, jak se chová splay při hledání v rostoucím pořadí, a proč splayujeme a neprovádíme jenom naivní rotace. Úlohy 1-2 jste vyřešili sami, na tabuli jsem pak ukázal úlohy 3-4, kvadratické řešení úlohy 1 a nakonec jsem se krátce zmínil o nějakých vlastnostech splay stromů a dynamické optimalitě. Úlohu 5 si necháváme na příště, na zbývající úlohy se případně podívejte sami.

Začali jsme se zadáním úkolu splay_experiment s deadlinem 7. 11. 2024 ve 23:59. Jako zajímavé zdroje pro ilustraci toho, co přibližně čekáme, můžou sloužit ukázkové řešení "nultého" úkolu a povídání o domácích úkolech od cvičících pro minulou akreditaci. Na druhou stranu, ne všechno je nutně relevantní: protože měříme rotace, není třeba řešit konfiguraci vašeho počítače, a taky není potřeba řešit přesný odhad multiplikativních konstant. U povídání jsou asi nejzajímavější kapitolky Měření, Tvorba grafů a Popis výsledků (stránky 6-8). Také jsem zmínil pár vět, které se můžou při řešení experimentu hodit.

Potom jste řešili úlohy, prošli jsme první dvě.

Zadali jsme si úkol ab_tree s deadlinem 14. 11. 2024 ve 23:59 a poté jsme se na (a,b)-stromy podívali. Řešili jsme hlavně na první tři úlohy s tím, že druhou a třetí jsme prodiskutovali na tabuli, a čtvrtou jsem poté lehce naznačil.

Zadali jsme úkol ab_experiment s deadlinem 21. 11. 2024 ve 23:59. Dále jsme se zabývali cache-oblivious a cache-aware algoritmy - první dvě úlohy zvládly všechny skupiny, třetí a čtvrtou jsem naznačil na tabuli.

Zadali jsme úkol matrix_transpose s deadlinem 28. 11. 2024 ve 23:59, úlohu ab_tree jsem lehce okomentoval, a pak jsme vyřešili vlastně všechny úlohy kromě šestky, kterou jsem nestihnul ukázat na tabuli, takže jsme prošli cachování, a zopakovali jsme si pravděpodobnost pro hashování na příští týden.

Zadali jsme úkol matrix_experiment s deadlinem 5. 12. 2024 ve 23:59 a něco jsme si řekli k ab_experimentu. Pak jsme se zabývali hlavně nezávislostí a univerzalitou hashovacích systémů a zmínil jsem, jak funguje tabulkové hashování, stihnuli jsme první tři úlohy.

Zadali jsme úkol cuckoo_hash s deadlinem 19. 12. 2024 ve 23:59 a řekl jsem pár vět k matrix_experimentu. Pak jsme se zabývali kukačkovým hashováním a tabulkovým hashováním, stihnuli jsme první tři úlohy, a čtvrtou jsem ještě naznačil na tabuli.

Zadali jsme úkol find_duplicates s deadlinem 9. 1. 2025 ve 23:59, zmínil jsem existenci Bloomových filtrů a rolling hashe, a pak jsme si naposledy hráli s hashováním. Prošli jsme úlohy 1-4.

Zadali jsme si poslední úkol kgrams s deadlinem 31. 1. 2025 ve 23:59, a pak jsme se zabývali sufixovými a LCP poli. Stihnuli jsme vánočně vyřešit úlohy 1-3.

Podívali jsme se na geometrické a paralelní datové struktury, hlavně jsme se bavili o k-d stromech. Nakonec jsme si ještě trochu něco řekli o online a streamovacích algoritmech. Prošli jsme úlohy 1-2, 4 a 7.