Cvičení z datových struktur 1 — Pravidla

Znalostní prerekvizity

• Programování (v rozsahu základního kursu)
• Základní algoritmy a datové struktury (např. vyvažované binární vyhledávací stromy)
• Diskrétní matematika (kombinatorika, základy teorie čísel)
• Základy teorie pravděpodobnosti (linearita střední hodnoty, …)

Pokud v čemkoliv z tohoto máte mezery, ozvěte se prosím brzy. Doporučíme vhodné materiály k doplnění znalostí.

Úkoly

Požadavky:

• Alespoň 8 programovacích (implementačních) úkolů, 10 bodů za kus
• Alespoň 4 experimentální úkoly, 15 bodů za kus
• Na zápočet je třeba získat alespoň 90 bodů.
• Termíny: 2 týdny od zadání (na konci semestru obvykle více)

Programovací úkoly:

• Dostanete částečnou implementaci datové struktury.
• Máte za úkol implementovat chybějící části. Původní části můžete upravovat.
• Úkol je nejprve testován automaticky, testovací data jsou veřejná.
• Cvičící si prohlédne váš program a případně koriguje bodové ohodnocení.
• Automatické testy jsou pouze nutnou podmínkou. Řešení musí mít správnou složitost, udržovat potřebné invarianty atp.
• Lze řešit v C++ a v Pythonu.

Experimentální úkoly

• Cílem je změřit chování zadané datové struktury.
• Odevzdáváte zprávu s naměřenými hodnotami a diskusí (jako PDF).
• Výsledky je třeba zdůvodnit teorií z přednášek (jde-li to).

Všeobecná pravidla

• O úkolech můžete diskutovat s ostatními, ale nesdílejte s nimi své programy ani zprávy (ukázat je přednášejícímu nebo cvičícímu samozřejmě můžete).
• Nesdílejte vzorová řešení úkolů s lidmi mimo vaši skupinu.
• Termíny jsou pevné.
• Před termínem můžete své řešení odevzdávat vícekrát, platí maximum získaných bodů.
• Program musí projít všemi testy.
• Kvalita vašich programů a zpráv se promítá do hodnocení.
• V programovacích úkolech nepoužívejte netriviální kód, který jste nenapsali sami. To zahrnuje cizí implementace datových struktur a jiné než zřejmé knihovní funkce. Základní použití natahovacích polí (vkládání na konec std::vector v C++ nebo list.append() v Pythonu) je povoleno, nic složitějšího už ne. Pokud si nejste jistí, poraďte se s cvičícím.
• Předchozí pravidlo zahrnuje také kód stažený z internetu, např. ze StackOverflow. Zjistit si, jak se používá Pythoní list je pravděpodobně v neškodné. Hledat, jak se implementuje splay strom už pravděpodobně ne — raději použijte poznámky z přednášky. Nejste-li si jistí, zeptejte se cvičícího.
• Citujte všechny zdroje! Všechny převzaté výsledky (věty z literatury, výsledky experimentů z cizích článků, ...) musí být řádně formulovány a citovány. Chybějící citace jsou (nejen zde) považovány za významný prohřešek proti akademické etice.
• Pokud se rozhodnete použít jinou verzi datové struktury, než zazněla na přednášce, čeká se od vás důkaz, že také má požadované vlastnosti.