Po úvodu do cvičení jsme zadali první úlohu tree_successor s deadlinem 17. 10. 2022 ve 23:59. Potom jsme se věnovali úlohám na cvičení, první dvě úlohy jsme probrali detailně, třetí a čtvrtou jsem spíše naznačil.

Nejprve jsme si ukázali nafukovací pole, a potom jsme se věnovali úlohám na cvičení. První dvě jsem stihnul ukázat na tabuli, pro ostatní máte řešení vedle zadání.

Nejprve jsme si ukázali splay stromy a zadali jsme úkol splay_operation s deadlinem 31. 10. 2022 ve 23:59. Pak jsme se věnovali dalším úlohám, hlavně splayování a konstrukci optimálního statického BVS. Řešení prvních tří příkladů jsou k dispozici, ostatní si necháme na příště.

Zadali jsme úkol splay_experiment s deadlinem 7. 11. 2022 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).

Potom jsme ř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 14. 11. 2022 ve 23:59, rychle jsem okomentoval řešení úlohy splay_operation a dále jsme zkoumali (a,b)-stromy.

Zadali jsme úkol ab_experiment s deadlinem 21. 11. 2022 ve 23:59, řekli jsme si hlavní body k řešení úlohy splay_experiment a dále jsme se zabývali cache-oblivious a cache-aware algoritmy - stihli jsme vlastně první tři úlohy.

Zadali jsme úkol matrix_transpose s deadlinem 28. 11. 2022 ve 23:59, projdeme úlohu ab_tree, a pak jsme zkoumali cache oblivious maticové algoritmy.

Zadali jsme úkol matrix_experiment s deadlinem 5. 12. 2022 ve 23:59, řekli jsme si, co jsem očekával v řešení úlohy ab_experiment, a pak jsme začali s hashováním a opakováním pravděpodobnosti.

Zadali jsme úkol cuckoo_hash s deadlinem 12. 12. 2022 ve 23:59, řekl jsem pár věcí k úloze matrix_transpose, a pak jsme se koukali na různé hashovací rodiny.

Zadali jsme úkol find_duplicates s deadlinem 19. 12. 2022 ve 23:59, okomentoval jsem řešení úlohy matrix_experiment, a pak jsme zkoumali tabulační i jiné hashování.

Tentokrát nebyl nový domácí úkol, řekli jsme si něco k úloze cuckoo_hash, a pak jsme dále trávili čas zkoumáním hashování.

Zadali jsme úkol kgrams, lehce jsem okomentoval úlohu find_duplicates, a pak jsme se zabývali sufixovými a LCP poli.

Ještě jsem zopakoval sufixové a LCP pole, a potom jsme se dívali na geometrické datové struktury, hlavně na k-d stromy a vícerozměrné intervalové stromy.