Datové struktury I - cvičení

Tato stránka je věnována cvičení z datových struktur I (NTIN066) k přednášce Jiřího Finka.
Cvičení se konají každé pondělí od 9:00 v S10 a každý pátek od 12:20 v S1 na Malé Straně.
Pokud máte nějaký dotaz nebo chcete něco konzultovat, napište mi e-mail na adresu chmel(zavinutá ryba)iuuk.mff.cuni.cz.
Účast na cvičení je dobrovolná (ale doporučená). Budeme rozebírat řešení domácích úkolů z předchozího týdne, otázky k tématům z přednášky a pokud zbyde čas, budeme řešit teoretické úlohy pro lepší porozumění.

Podmínky získání zápočtu

Pro zápočet je potřeba získat alespoň 75 bodů, přičemž celkem bude možné získat alespoň 115 bodů.

Domácí úkoly

Přesnější pravidla naleznete zde (pozor, toto jsou loňská pravidla, oproti letošku se liší počtem zadaných úloh a bodů potřebných na zápočet).

Krátká verze: po téměř každém cvičení bude zadán jeden domácí úkol, celkem garantujeme, že bude alespoň sedm programovacích (implementačních) úkolů po 10 bodech, a alespoň tři experimentální úlohy po 15 bodech. Na řešení každého úkolu budou dva týdny a všechny úkoly se odevzdávají výhradně přes ReCodEx. Zadání můžete nalézt na Gitlabu KAMu zde.

Co jsme dělali

DatumObsah
30. 9. 2024Úvod, opakování z bakalářského studia: Dijkstra a haldy, asymptotika a binární vyhledávací stromy. Úlohy na cvičení. Řešení úloh ze cvik.

Začali jsme s úvodem do předmětu a pravidly zápočtu. Potom jsme řešili opakovací úlohy, vesměs jsme zvládli úlohy 1 a 2, na tabuli jsem poté naznačil řešení úloh 3-5.

7. 10. 2024Amortizace. Úlohy na cvičení. Řešení úloh ze cvik.

Prvně jsme si zadali úkol tree_successor s deadlinem 20. 10. 2024 ve 23:59. Potom jsme se trochu pobavili o amortizaci, a řešili jsme rúzné úlohy. Celkem jsme po skupinkách stihli úlohy 1-3, a já jsem na tabuli naznačil část řešení úloh 4 a 5.

14. 10. 2024Líně vyvažované stromy a úvod do splay stromů. Úlohy na cvičení. Shrnutí splay stromů Ondry Mičky, vizualizace, řešení úloh ze cvik.

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 a nakonec jsem se krátce zmínil o nějakých vlastnostech splay stromů a dynamické optimalitě. Úlohu 5 si necháme na příště, na zbývající úlohy se případně podívejte sami.

21. 10. 2024Pokračování splay stromů. Úlohy na cvičení. Řešení úloh ze cvik.

Začali jsme se zadáním úkolu splay_experiment s deadlinem 3. 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).

Potom jste řešili úlohy, první úlohu jste lehce prošli, a zbytek času jsme strávili s druhou úlohou, kterou jsem pak také vyřešil na tabuli.

28. 10. 2024Cvičení se nekoná: Den vzniku samostatného československého státu
4. 11. 2024(a,b)-stromy. Úlohy na cvičení. Vizualizace (a,b)-stromů, řešení úloh ze cvik.

Zadali jsme si úkol ab_tree s deadlinem 17. 11. 2024 ve 23:59 a poté jsme se na (a,b)-stromy podívali. Naším cílem byly hlavně první tři úlohy s tím, že druhou a třetí jsme pak prodiskutovali na tabuli.

11. 11. 2024Cache-oblivious a cache-aware algoritmy. Úlohy na cvičení. Řešení úloh ze cvik.

Zadali jsme úkol ab_experiment s deadlinem 24. 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.

18. 11. 2024Cachování a příprava na hashování. Úlohy na cvičení. Řešení úloh ze cvik.

Zadali jsme úkol matrix_transpose s deadlinem 1. 12. 2024 ve 23:59, prošli jsme rychle úlohu ab_tree, a pak jsme vyřešili vlastně všechny úlohy, takže jsme prošli cachování, a zopakovali jsme si pravděpodobnost pro hashování na příští týden. Také jsem připomněl, že přiští týden za mě zaskočí Pavel Veselý.

25. 11. 2024Plán: Úvod do hashování, systémů a vlastností hashovacích funkcí s Pavlem Veselým.
DatumObsah
4. 10. 2024Úvod, opakování z bakalářského studia: Dijkstra a haldy, asymptotika a binární vyhledávací stromy. Úlohy na cvičení. Řešení úloh ze cvik.

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.

11. 10. 2024Amortizace. Úlohy na cvičení. Řešení úloh ze cvik.

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.

18. 10. 2024Líně vyvažované stromy a úvod do splay stromů. Úlohy na cvičení. Shrnutí splay stromů Ondry Mičky, vizualizace, řešení úloh ze cvik.

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.

25. 10. 2024Pokračování splay stromů. Úlohy na cvičení. Řešení úloh ze cvik.

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ě.

1. 11. 2024(a,b)-stromy. Úlohy na cvičení. Vizualizace (a,b)-stromů, řešení úloh ze cvik.

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.

8. 11. 2024Cache-oblivious a cache-aware algoritmy. Úlohy na cvičení. Řešení úloh ze cvik.

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.

15. 11. 2024Cachování a příprava na hashování. Úlohy na cvičení. Řešení úloh ze cvik.

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.

22. 11. 2024Plán: Úvod do hashování, systémů a vlastností hashovacích funkcí.
29. 11. 2024Cvičení odpadá.

Zajímavé odkazy

Powered by the programming Parseltongue