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.