Začali jste s úvodem do předmětu a pravidly zápočtu. Podívali jste se na Dijkstrův algoritmus a haldy, na konci jste se ještě kouknuli na vyvážení binárního vyhledávacího stromu v lineárním čase.

Prvně jste zadali úkol tree_successor s deadlinem 22. 10. 2023 ve 23:59 (opravující: Petr Chmel). Podívali jste se na asymptotickou notaci, iterovaného následníka, nafukovací pole a další úlohy na amortizaci. Celkem jste stihli prvních pět úloh.

Zadali jste si úkol splay_operation s deadlinem 29. 10. 2023 ve 23:59 (opravující: Petr Chmel). Pak jste se věnovali splay stromům, tedy jste si připomněli dvojrotace, jak se chová splay při hledání v rostoucím pořadí, proč splayujeme a neprovádíme jenom naivní rotace. Dále se dostalo na použití splaye při insertu a deletu, na intervalové dotazy a použití splay stromu (možná jste mezi řečí zmínili i working set bound). Nakonec jste se zmínili o staticky optimálním stromu, jeho konstrukci v kubickém čase, a statickou a dynamickou optimalitu splay stromů.

Zadali jste si úkol splay_experiment s deadlinem 12. 11. 2023 ve 23:59 (opravující: Petr Chmel). POZOR: původní termín byl omylem nastavený jinak, o týden jsme ho poté zkrátili. 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).

Potom jste řešili úlohy, na tabuli jsem ukázal řešení prvních pěti úloh (úlohy 4 a 5 spíše zběžně jen s popisem).

Zadali jsme úkol ab_tree s deadlinem 12. 11. 2023 ve 23:59 (opravující: Pavel Veselý), rychle jsem okomentoval řešení úlohy splay_operation a dále jsme zkoumali (a,b)-stromy. Všichni jste vyřešili první tři úlohy, čtvrtou a pátou jsem plánoval říct si příště, ale bohužel jsme to nestihli, takže se prosím podívejte na řešení výše.

Zadali jsme úkol ab_experiment s deadlinem 19. 11. 2023 ve 23:59 (opravující: Pavel Veselý), a upozornil jsem na to, že deadline úkolu splay_experiment jsme o týden posunuli. Dále jsme se zabývali cache-oblivious a cache-aware algoritmy - první dvě úlohy zvládly všechny skupiny, třetí jsem ukázal (bez pár detailů) na tabuli, a čtvrtou jsem naznačil řešení tak, že by pak nemělo být těžké ji domyslet -- ale všechna řešení jsou stejně k dispozici výše.

Zadali jsme úkol matrix_transpose s deadlinem 26. 11. 2023 ve 23:59 (opravující: Petr Chmel), prošli jsme rychle úlohu ab_tree, a pak jsme zkoumali cache oblivious maticové algoritmy.

Zadali jsme úkol matrix_experiment s deadlinem 3. 12. 2023 ve 23:59 (opravující: Petr Chmel), řekli jsme si pořádně splay_experiment, lehce jsme se dotkli ab_experiment, a pak jsme začali s opakováním pravděpodobnosti a hashováním.

Zadali jsme úkol cuckoo_hash s deadlinem 10. 12. 2023 ve 23:59 (opravující: Pavel Veselý), řekl jsem pár drobností k úloze matrix_transpose, potom jsme se ponořili do tabulkového a kukaččího hashování, s čímž jsme strávili zbytek hodiny, a všichni zvládli úlohy 1-3.

Zadali jsme úkol find_duplicates s deadlinem 17. 12. 2023 ve 23:59 (opravující: Petr Chmel), okomentoval jsem řešení úlohy matrix_experiment, zmínil jsem existenci Bloomových filtrů, a pak jsme si naposledy hráli s hashováním. Úlohy 1 a 2 stihli všichni, trojku jsem pak rychle řekl na tabuli.

Zadali jsme úkol hash_experiment s deadlinem 7. 1. 2024 ve 23:59 (opravující: Pavel Veselý), řekli jsme si něco k úloze cuckoo_hash, a pak jsme dále trávili čas s geometrickými datovými strukturami, zvládnuli jsme úlohy 1-3.

Zadali jsme úkoly range-tree a kgrams s deadlinem 31. 1. 2024 ve 23:59 (opravující: Pavel Veselý), lehce jsem okomentoval úlohu find_duplicates, a pak jsme se zabývali sufixovými a LCP poli.

Podívali jsme se na paralelní datové struktury, a po zbytek cvičení jsme si pak zmiňovali jiné než standardní druhy algoritmů.