Datové struktury I

Datové struktury I - cvičení

Tato stránka je věnována cvičení z datových struktur I (NTIN066) k přednášce Pavla Veselého.
Cvičení se konají každý čtvrtek od 14:00 v S7 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ů za domácí úkoly, přičemž celkem bude možné získat alespoň 115 bodů.

Domácí úkoly

Přesnější pravidla naleznete zde.

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

Datum	Obsah
2. 10. 2025	Úvod, opakování z bakalářského studia a amortizace. Úlohy na cvičení. Řešení úloh ze cvik. Začali jsme s úvodem do předmětu a pravidly zápočtu a dále jsme si zadali úkol `tree_successor` s deadlinem 16. 10. 2025 ve 14:00. Potom jsme řešili pár opakovacích úloh a pár úloh na amortizaci, vesměs jste zvládli úlohy 1-3, na tabuli jsem poté naznačil řešení úloh 3 (alternativní) a 4.
9. 10. 2025	Líně vyvažované stromy a úvod do splay stromů. Úlohy na cvičení. Řešení úloh ze cvik. Začali jsme se zadáním úkolu `splay_operation` s deadlinem 27. 10. 2025 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 včetně operací Find, Insert, Delete. Zvládli jsme úlohy 1-4, úlohu 5 si necháme na příště.
16. 10. 2025	Plán: Pokračování splay stromů.