Stránky mého cvičení z Algoritmů a datových struktur 1 (ADS1, NTIN060) v letním semestru 2023/2024. Scházíme se v pondělí 15:40 v učebně N4 (na IMPAKTu v Tróji). Přednáška má stránku na webu přednášejícího.
Nutnou a postačující podmínkou pro zápočet je získání 100 bodů z domácích úkolů (bude zadáno minimálně 150 bodů) a případně z bonusových písemek.
Úkoly: Jsou zadávány v sovičce, přístup jste dostali e-mailem. Sovička používá (pokud neodevzdáváte úlohy jako PDF přílohu) Markdown a matematiku „z TeXu“. Nezdráhejte se tedy své řešení hezky naformátovat (abych mohl dát body, potřebuji vaše řešení pochopit, navíc u hezky napsaného řešení spíše přimhouřím oči nad jeho nedostatky). Nezapomeňte, že čeština podporuje featuru „interpunkce“. K řešení DÚ sepsal hezký návod Václav Končický
Na každý úkol budou dva týdny (do začátku cvičení), deadline je striktní, na cvičení se předvede jeho řešení. Do té doby si své řešení můžete libovolně opravovat (budu se snažit dávat zpětnou vazbu rychle). Proto to nenechávejte řešení úkolu na poslední chvíli (naopak ze svých zkušeností doporučuji začít řešit cca. hned po zadání).
O úkolech je povoleno s kýmkoliv diskutovat, každý však své řešení musí sepsat sám a plně ho chápat! Pokud budete v řešení používat něco externího (např. obrázek z internetu) je třeba uvést zdroj (nic takového by však nemělo být potřeba). Podvádění proti těmto pravidlům nebude tolerováno.
Písemky: Na začátku každého (kromě prvního) cvičení bude zadána písemčička za 3 bonusové body na téma, které se bralo na předcházející přednášce. Cílem je rychle si zopakovat přednášku a ověřit, že jste na ní dávali pozor. Očekávejte tedy rychlé otázky stylu „Jak proběhne Bubble sort na posloupnosti [1, 2, 3, 4, 5, 6]?“ nebo „Asymptoticky jak dlouho trvá INSERT prvku do haldy?“.
Jak už bylo zmíněno, na začátku cvičení proběhne písemka. Následně si bleskově zopakujeme přednášku a případně ukážeme řešení domácího úkolu. Pak se (náhodně) rozdělíme do skupin a budeme řešit úlohy k tématu z přednášky. Já vás budu obcházet a průběžně ukazovat řešení těchto úloh.
(Úlohy nejsou vlastní tvorby, vykradl jsem minulé ročníky ADS1.)
Kromě dlouhého organizačního povídání, jehož obsah je plus mínus výše, jsme si (vzhledem k tomu, že nebyla přednáška) hráli s nějakými zajímavými úložkami, ke kterým nejsou potřeba žádné speciální algoritmy nebo datové struktury. Výjimečně je i řešení, najdete ho v sovičce.
Po připomenutí RAMu a Levenštejnovy (neboli editační) vzdálenosti, jsme řešili úlohy úlohy. Prošli jsme (i když možná někde moc krátce) řešení 2–6 a 8.1–8.3, ještě se k tomu v rychlosti vrátíme příště.
Tentokráte jsme si připomněli BFS, a poté na úložkách pořádně procvičili, asymptotickou časovou složitost a BFS (s trochou DFS).
Trochu jsme si ucelili pohled na to, o čem ADSka jsou (že to není programování, tedy není třeba odevzdávat kód řešící všechny okrajové případy, ale spíše se zaměřovat na myšlenky, které jsou za takovým kódem; a že se neobejdeme bez časové složitosti). Pak jsme si ještě jednou zopakovali BFS a zopakovali jsme si DFS, mosty, artikulace, DAGy a TU. Toho jsme pak využili při řešení úložek.
Po opakování předchozího cvičení (jak má vypadat řešení DÚ, hledání mostů a artikulací + opakování BFS) a řešení domácího úkolu jsme se vrhli na silně souvislé komponenty a Dijkstrův algoritmus. Ten jsme si procvičili na úložkách, kde jsme hlavně zjistili, že záporné hrany jsou problém a že spoustu úloh jde vyřešit vyměněním uspořádání (např. na lexikografické, či inverzní) datové struktury, kterou Dijkstrův algoritmus používá.
Tentokráte jsme si hráli s relaxačními algoritmy (s obecným, s Dijkstrovo algortimem a s Bellman–Fordovým). Všechny jsme si procvičili na úložkách. Tím pádem jsme se například naučili hledat záporné cykly, jak si můžete přečíst u Pavla Veselého
Velikonoční pondělí, tudíž cvičení není. Velikonoční domácí úkol (a bonusová úložka) čekají v sovičce.
Po Velikonocích jsme měli co dohánět. Po předvedení řešení obou domácích úkolů a zopakování obou přednášek (tři algoritmy na hledání koster: 1., 2., 3.; AVL stromy a jejich rotace) jsme se pustili do úložek ohledně koster a BVS. Řešení se však nestihla.
Vzhledem k tomu, že se minule nestihla vzorová řešení úložek na cvičení, po krátkém zopakování přednášky (BVS, AVL, (a, b)-stromy) se hlavně předváděla řešení minulého cvičení. Avšak měli jsme i nové úložky.
Toto cvičení jsem bohužel organizoval soustředění M&M, tudíž se pouze řešili úložky. (Místo písemky je bonus v předchozím domácím úkolu.)
Po mé absenci jsme toho měli hodně co dohánět. Zopakovali jsme LLRB tree (dokonce i červeno-černé stromy), trie, intervalové stromy, hashovací tabulky (s kolizí řešenou spojovým seznamem, otevřenou adresací a otevřenou adresací s dvojím hashováním) a amortizaci. A ukázali jsme si řešení minulých úložek. Úložky na toto cvičení jsme moc nestihli.
Na tomto cvičení jsme si ukazovali řešení mnoha domácích úkolů, zmínily se myšlenky úložek z minulého cvičení a lehce se zopakovala Kuchařková věta (k myšlence rozděl a panuj). Pak jsme na Kuchařkovou větu a odhady rekurencí počítali úložky.
Před tímto cvičením nebyla přednáška, tedy úložky se řešily ty z minulého cvika, ale hlavním tématem byla amortizovaná časová složitost (a jak ji spočítat za pomoci ukládání si mincí).
Poslední cvičení.