Datové struktury I – Pravidla hry

Struktura předmětu

K předmětu patří přednášky a cvičení.

Ke splnění předmětu je potřeba složit zkoušku (ústní zkouška s písemnou přípravou, pokrývá teorii z přednášky) a získat zápočet z cvičení.

Předpokládáme následující znalosti

• 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:

• Zadáme alespoň 8 programovacích úkolů po 10 bodech
• a alespoň 4 experimentální úkoly po 15 bodech.
• Na zápočet je potřeba získat minimálně 90 bodů.
• Termín: 2 týdny od zadání (více ke konci semestru)

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 testován automaticky, testovací data jsou veřejná.
• Cvičící si prohlédne váš program a případně koriguje bodové ohodnocení.
• Lze řešit v C++ a (obvykle) také v Pythonu.

Experimentální úkoly

• Cílem je změřit chování zadané implementace struktury.
• Odevzdáváte zprávu s naměřenými hodnotami a diskusí (jako PDF).

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. Triviální rostoucí pole (std::vector v C++ nebo list.append() v Pythonu) je ještě v pořádku, ale cokoliv složitějšího už ne. Pokud si nejste jistí, poraďte se s cvičícím.
• Všechny matematické věty, které použijete ve svých zprávách, je potřeba precizně formulovat a citovat jejich zdroj. Pokud věta zazněla na přednášce, stačí citovat přednášku.
• Pokud jste se kdekoliv inspirovali, citujte všechny zdroje. 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.