Předmět končí klasifikovaným zápočtem, který bude udělen za vypracování, odevzdání a následné ústní obhájení čtyř úloh a za ústní vysvětlení (chcete-li, vyzkoušení ze znalostí) jednoho z témat probraného na přednášce.

Obhajoba úloh proběhne během semestru online v termínech vypsaných v is stag v týdnech: 5., 7., 9., 11., ve 13. týdnu bude náhradní/opravný termín. Do nedělní půlnoci předchozího týdne pošlete vypracovanou úlohu e-mailem, odevzdané řešení nemusí obsahovat zadání úlohy, ale musí obsahovat odkaz na ročník, sérii a číslo úlohy (ve tvaru kódu uvedeného u zadání, např. 34-Z2-3).
Vysvětlení algoritmu/datové struktury proběhne v termínu vypsaném ve zkouškovém období v is stag. Dovolí-li to časové možnosti, bude studentům dána možnost toto vysvětlení podat během výuky.

Úlohy si student/ka vybere z úloh z korespondenčního semináře v programování (http://ksp.mff.cuni.cz) z letošního i z proběhlých ročníků:
Tři úlohy student/ka vybere z praktických úloh, vypracuje je v Pythonu, otestuje na cvičišti (pozor, nespleťte si ho s odevzdávátkem, které je určeno pro soutěžící středoškolské studenty), kde si zřídí účet.
Jednu úlohu student/ka vybere z teoretických úloh.
Není možné odevzdat a obhájit úlohu, která byla předtím vysvětlena na cvičení či přednášce.

Témata z algoritmů/datových struktur jsou:
1. Binární vyhledávání v seřazeném souboru dat. Základní metody řazení: vkládáním (InsertSort), výběrem (SelectSort), QuickSort (první z rychlejších algoritmů), sléváním (MergeSort). Časová složitost algoritmu, symbol O, pomalejší algoritmy (InsertSort, SelectSort) jsou O(n^2), rychlejší jsou O(n log(n)).
2. Vysvětlení základních pojmů teorie grafů (vrchol, hrana, cyklus, cesta, souvislost, strom). Vysvětlení algoritmů na prohledávání grafu (prohledávání do hloubky, DFS, prohledávání do šířky, BFS), datové struktury zásobník (LIFO), fronta (FIFO).
3. Graf s ohodnocenými hranami, algoritmy na hledání nejkratší cesty v grafu (Bellmann-Ford, Dijkstra), nejen jak fungují, ale i proč vydají správný výsledek. Vysvětlení datových struktur fronta, halda.
4. Kostra grafu, minimální kostra v grafu s ohodnocenými hranami, řezové lemma a jeho důkaz. Jarníkův algoritmus na hledání minimální kostry, datová struktura halda. Stručně o Kruskalově a Borůvkově algoritmu a algoritmu union-find - škrtám.

Bodové hodnocení:
Body za úlohy kategorie KSP-Z jsou dle zadání, body za úlohy kategorie KSP-H o tři body více, než je v zadání uvedeno. Plný počet získáte u praktické úlohy za vysvětlení vašeho kódu, proč dává požadovaný výsledek a všech programovacích konstrukcí v kódu uvedených a dále je třeba úspěšně kód otestovat na cvičišti. U teoretické úlohy získáte plný počet za vysvětlení algoritmu, důkaz, že výsledek algoritmu řeší zadanou úlohu a rozbor časové složitosti algoritmu. Úlohy, ke kterým na ksp dosud nebylo zveřejněno řešení (čtvrtá série do 2. dubna a pátá série do začátku června) mají maximální bodové hodnocení dvojnásobné.

Za téma z přednášky při prvním pokusu můžete získat až 20 bodů. Téma bude určeno losem (pravděpodobně hodem kostkou). Nebudete-li spokojeni s bodovým hodnocením, budete mít možnost opravy, vylosované téma vám ale zůstává a maximální počet bodů se při opravě snižuje na 10 bodů. Můžete si sami zvolit téma už na prvním pokusu, máte tím automaticky hranici na deseti bodech.
Jestli se vám systém přezkoušení z teorie zdá složitý, tak vězte, že do loňského roku jsem vůbec teoretické otázky k absolvování předmětu nepožadovala, dávala jsem důraz na získání praktických dovedností. Vyzkoušení z teorie jsem tedy zařadila letos poprvé, ale stále dávám přednost rozvoji kompetencí před znalostmi a věřím, že důkladnou přípravou na jedno téma, byť by to bylo dle vašeho výběru, tyto kompetence získáte (jinak řečeno, dávám přednost dobré znalosti jednoho tématu před povrchní znalostí všech). V požadavcích ke státní závěrečné zkoušce jsou všechna témata a pevně věřím, že kompetence získané absolvováním tohoto předmětu vám při přípravě na SZZ pomůžou lépe, než letošní povrchní znalost teorie.

Hodnocení:
75 a více bodů výborně
70 až 74 bodů výborně mínus
65 až 69 bodů velmi dobře
60 až 64 bodů velmi dobře mínus
55 až 59 bodů dobře

Poznámka k výběru úloh:
nejlehčí úlohy jsou za 8 bodů a jsou na úrovni UDP, proto jsem je vloni zakázala, ale ke konci semestru jsem změnila názor a úlohu z páté série jsem za 2x8 bodů povolila. Letos takové omezení nedávám, ale doporučuji. Dále jsem vloni měla požadavek na alespoň jednu úlohu před zveřejněním řešení, i tato podmínka zůstává pro letošek jen jako doporučení. Moje představa výběru lehkých úloh je: praktické úlohy za 10, 10, 2x8 bodů, dohromady 36 bodů. Teoretické úlohy jsou zpravidla za 14 bodů, k absolvování předmětu potřebujete ještě 19 bodů, počítám-li zhruba 10 bodů za vyzkoušení z teorie, pak vám stačí zhruba 9 bodů z teoretické úlohy. Na lepší hodnocení než dobře je třeba vybírat obtížnější úlohy a lépe se připravit na přezkoušení z teorie.