IV003 Algoritmy a datové struktury II (jaro 2018)

Sady problémů

Problémy můžete řešit buď samostatně anebo ve dvojicích. Všechny příklady jedné sady musíte řešit stejným způsobem, tj. buď všechny samostatně anebo všechny se stejným spoluřešitelem. V případě, že příklady řešíte ve dvojici, získavají oba řešitelé celý počet bodů (body se nedělí).

Spolupráce většího počtu studentů není povolena, stejně tak jako opisování cizího řešení. Případy nedovolené spolupráce a plagiarizmu budou postoupeny disciplinární komisi FI a studenti budou hodnoceni známkou nevyhověl (F).

Typy pro vypracování řešení

Typicky je problém formulován jako Navrhněte efektivní algoritmus pro ... Vaše řešení by mělo obsahovat

Jasný popis algoritmu (pseudokód anebo matematicky přesná čeština). Můžete použít algoritmy, které byly diskutovány na přednášce jako podprogramy, musíte ale jednoznačně specifikovat jejich vstup a výstup. Váš popis musí byt jednoznačný tak, aby osoba znalá programování dokázala na základě Vašeho popisu algoritmus korektně naprogramovat.
Nepište kód algoritmu v žádném programovacím jazyce.
Dokažte, že Váš algoritmus je korektní. Algoritmus bez řádného zdůvodnění nemůže být hodnocen plným počtem bodů.
Analyzujte složitost Vašeho algoritmu (krok po kroku). Složitost vyjádřete v O-notaci.

Instrukce pro psaní řešení jsou velice přehledně shrnuty v dokumentu z UC Berkley.

Vzorová řešení příkladů

Řešení příkladů budou diskutována na cvičeních, využijte je! Návrh algoritmů se dá naučit jedině navrhováním algoritmů. :-)

Dotazy k příkladům

Pro dotazy a diskusi k zadaným příkladům využívejte, prosím, diskusní fórum předmětu v ISu. Odpovědi na dotazy položené na jiných diskusních fórech negarantujeme, i když se snažíme všechna fóra sledovat.

Zadání příkladů a odevzdávárny

Pro zápis svého řešení použijte, prosím, připravenou šablonu (nezapomeňte vyplnit své jméno a UČO). Vygenerovaný pdf soubor vložte do příslušné odevzdávárny. V případě, že příklady řešíte ve dvojici, odevzdává (se svým jménem) řešení pouze jeden z dvojice a složení dvojice nám sdělíte pomocí odpovědníku. Opravené řešení bude mít ve svém poznámkovém bloku přístupné student, jehož UČO je uvedené na řešení. Jiný způsob odevzdávání řešení nebude akceptován.