Datové struktury I, obecné informace k domácím úkolům

Základní pravidla

  • Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší "inspirace".
  • Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí "inspirací". Výjimku tvoří odevzdání kódu.
  • Povolená jsou řešení v jazycích C/C++ (doporučený jazyk), Java a C#.
  • Zadané datové struktury i algoritmy musí být implementovány efektivně, zejména asymptotické složitosti vašich implementací nesmí být horší než je probíráno na přednáškách. Na druhou stranu doslovné opsání pseudo-kódu ze skript nebo slajdů nemusí dát nejlepší program.
  • Cílem tohoto předmětu je porozumět datovým strukturám a algoritmům a umět je implementovat. Proto není povoleno používat cizí implementace ve vašich řešeních. Můžete tedy používat (názvy knihoven jsou z jazyka C/C++, v ostatních jazycích postupujte podobně)
    • standardní konstrukce vašeho programovacího jazyka
    • standardní knihovny pro práci se soubory (například stdio, iostream), pamětí (stdlib, memory), řetězci (string), časem (chromo, time), generátory náhodných čísel (stdlib, random) a pomocné knihovny (exception, functional, iterator, limits, tuple, type_traits, utility a podobně).
    Naopak nesmíte používat
    • knihovny datových struktur (vector, map, set, queue, deque a další)
    • algoritmy (například knihovna algorithm, zejména je zakázaná funkce std::sort).
  • Řešení musí být odevzdáno webovým formulářem.
  • Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

Při vypracovávání používejte mozek. Není možné, aby zadání popisovalo naprosto přesně, co máte dělat, a zakazovalo všechny nesmysly, které je možné vymyslet. V popisu vždy můžete napsat, jak jste postupovali a proč jste tak postupovali.

Některé úkoly mohou vyžadovat zpracování netriviálně velkých testovacích dat. Nicméně by jednotlivé testy měli trvat maximálně jednotky minut (desítky minut v případě externího třídění). Pokud vám test běží několik hodin, pak máte velmi neefektivní implementaci nebo test provádíte nevhodným způsobem. Například data je nutné ukládat na disk pouze v příkladu na externí třídění. V žádném případě není nutné hledat super-paralelní hyper-počítač. Počítače dostupné v u-labu jsou plně postačující k vyřešení domácích úkolů.

Hodnocení

Každý příklad je hodnocen 100 body. S výjimkou prvního příkladu budou body rozděleny takto:
  • 20 bodů za graf
  • 20 bodů za popis
  • 20 bodů za kvalitu zdrojových kódů
  • 40 bodů za splnění zadání

Základní kritéria

  • Řešení musí splňovat zadání a kód musí být funkční.
  • Je možné poslat opravené řešení, ale bude započteno penále 10 bodů za neúspěšný pokus.
  • Řešení musí být odevzdáno ve stanoveném termínu (penále 1 bod za 1 hodinu zpoždění).

Grafy (netýká se prvního příkladu)

Cílem je nakreslit graf, ze kterého bude zřejmé chování zadané datové struktury. Proto graf musí být přehledný a všechny křivky i osy musí být jednoznačně popsány. Používejte logaritmická měřítka tam, kde jejich použití lépe zobrazí naměřená data.
Výstupem vašeho programu mají být naměřené hodnoty požadované v zadání úlohy. K vytvoření grafů z naměřených hodnot můžete použít libovolný program.

Popis výsledků (netýká se prvního příkladu)

Zdůvodněte naměřené hodnoty. Můžete bez opakování důkazů využívat teoretické poznatky z přednášek a cvičení. Všímejte si trendů křivek (asymptotického chování) i absolutních hodnot (multiplikativních konstant). Dále srovnejte chování datových struktur, vlivů zadaných parametrů i různých typů vstupních dat.

Zdrojové kódy

Hodnoceny budou i vaše zdrojové kódy podle obvyklých kritérií.