Algoritmy a datové struktury I – cvičení

V letním semestru vedu cvičení k přednášce Pavla Veselého z Algoritmů a datových struktur I (ADS1). Cvičení probíhá každé pondělí od 15:40 v učebně N6 (pavilon IMPAKT v Tróji).

Účast na cvičení je dobrovolná, je na Vašem zvážení, jestli se na zkoušku připravíte efektivněji třeba samostudiem. Pokud se nechcete připravit o body z písemky, nebudu se zlobit, pokud cvičení opustíte hned po ní.

Hlavním smyslem cvičení je Vám pomoct s pochopením látky a přípravou na zkoušku. Proto budu rád, když se ozvete, pokud Vám cokoli nebude jasné, a uvítám návrhy na jaké věci byste se rádi na cvičení zaměřili. Pro komunikaci se mnou můžete využít emailovou adresu , případně Matrix @jakoma02:jakoma02.cz nebo Discord jakoma02.

Průběh cvičení

Na začátku každého cvičení se píše malý testík. Hlavní náplní cvičení je řešení úloh na procvičení látky z přednášky ve skupinách. Řešení úloh se ukazují na cvičení a obecně je neplánuji sepisovat. Pokud máte o řešení některé z úloh zájem, napište si o něj, nebo si o něj řekněte na cvičení.

Datum Téma Úlohy
19. 2. 2024 Asymptotika, algoritmické úlohy Úlohy na cvičení

Byly vysvětleny podmínky získání zápočtu obdobně, jako jsou napsány na této stránce. Cvičení bylo před první přednáškou, zopakovali jsme \(\mathcal{O}\) notaci a asymptotické vztahy mezi funkcemi. Pak jsme se přesunuli k algoritmickým úlohám a seznámili se s technikou dvou pointerů na řešení úloh v lineárním čase.

Na cvičení jsme stihli ukázat řešení úloh 1, 2, 4 (bez bonusu) a 5.

26. 2. 2024 Počítání na RAMu Úlohy na cvičení

V testíku jsme si zopakovali způsoby adresace na RAMu. Ve skupinách se pak řešily úlohy na překlad složitějších konstrukcí na RAM a způsoby “zneužití” konstantní ceny za operace s libovolně velkými čísly.

Řešení některých úloh si ukážeme na dalším cvičení.

4. 3. 2024 Prohledávání do šířky Úlohy na cvičení

V testíku se zopakovalo fungování prohledávání do šířky. Ukázali jsme řešení některých úloh z minulého cvičení – úlohy 1 až 4 z handoutu pro toto cvičení.

Ve skupinách se řešily úlohy na seznámení se s BFS, aplikace na hledání nejkratších cest a prohledávání stavového prostoru. Ukázání správných řešení opět přeteklo na další cvičení.

Na konci cvičení byl zadán druhý domácí úkol (viz Owl) a byl posbírán anonymní feedback na cvičení. Pokud chcete nějaký přidat, pošlete mi prosím třeba anonymní email.

11. 3. 2024 Prohledávání do hloubky Úlohy na cvičení

V testíku se zopakovaly definice mostu a artikulace. Ukázali jsme řešení některých úloh k BFS z minulého cvičení, viz handout.

Z přednášky jsme zopakovali DFS klasifikaci hran a algoritmus pro nalezení všech mostů v neorientovaném grafu pomocí počítání hodnot \(in(v)\) a \(low(v)\) při DFS.

Stihli jsme ukázat řešení úlohy 5 a rozmysleli jsme, kdy je artikulací kořen DFS stromu. Algoritmus na hledání artikulací úlohy na topologické uspořádání dokončíme příště.

18. 3. 2024 Topologické uspořádání, souvislost Úlohy na cvičení

V testíku se zopakovaly pojmy DAG, topologické uspořádání a jejich vztah. Ukázali jsme řešení úlohy na hledání artikulací.

Ve zbytku cvičení jsme se věnovali řešení úloh na procvičení topologického uspořádání a silné souvislosti. Na tabuli jsme ukázali řešení úloh 2 a 3. Řešení některých dalších úloh ukážeme na začátku přístího cvičení.

Na závěr jsme ukázali řešení druhého domácího úkolu. Do konce týdne platí možnost ukázané řešení sepsat, odevzdat a získat za něj až 3 body.

25. 3. 2024 Nejkratší cesty Úlohy na cvičení

V testíku se zopakovalo fungování Dijkstrova algoritmu na hledání nejkratší cesty. Ukázali jsme řešení dvou vybraných úloh z minulého cvičení, viz handout. Pokud vás zajímá řešení některé z ostatních úloh, řekněte si o něj na cvičení.

V úlohách jsme procvičovali zejména Dijkstrův algoritmus a jeho modifikace. U tabule jsme ukázali řešení úloh 3, 4, 5, 6 a 7.

Na závěr jsme ukázali řešení domácího úkolu s hledáním housenky.

8. 4. 2024 Minimální kostry, vyhledávací stromy Úlohy na cvičení

V testíku se zopakovaly algoritmy na hledání minimální kostry v grafu.

Ve zbytku cvičení jsme se věnovali úlohám na minimální kostry a úlohám na vyhledávací stromy. U tabule jsme ukázali řešení úloh 1, 2, 3 a 5 a načrtli jsme řešení úlohy 4.

Na konci cvičení jsme ukázali řešení domácího úkolu s hledáním šéfa a byl posbírán anonymní feedback na cvičení. Pokud chcete nějaký přidat, pošlete mi prosím třeba anonymní email.

15. 4. 2024 AVL, \( (a, b) \)-stromy Úlohy na cvičení

V testíku se zopakovaly podmínky na podobu AVL stromu a \( (a, b) \)-stromu. Ukázali jsme řešení třech úloh z minulého cvičení na vyhledávací stromy, viz handout.

Úlohy do skupin byly zaměřené na AVL stromy, \( (a, b) \)-stromy a aplikace vyhledávacích stromů, stihly se zejména úlohy na AVL stromy. U tabule jsme ukázali řešení úloh 4 a 5.

Na konci cvičení jsme ukázali řešení domácího úkolu s hledáním nejrychlejšího spojení.

Feedback jsem tentokrát sbíral na začátku cvičení zejména od těch, kteří ze cvičení odcházejí dříve. Pokud na cvičení nechodíš vůbec, budu rád, pokud mi feedback na úkoly (a klidně i pokud ti na cvičení něco schází) pošleš třeba anonymním emailem.

22. 4. 2024 Trie, intervalové stromy Úlohy na cvičení

V testíku se zopakovala trie a součtový intervalový strom. Ve skupinách se dořešily a u tabule ukázaly řešení třech úloh z minula, viz handout.

Ve zbytku cvičení jsme se věnovali úlohám na trie a intervalové stromy. U tabule jsme ukázali řešení úloh 4, 5 a 6.

Na konci cvičení jsme na tabule ukázali řešení domácího úkolu.

29. 4. 2024 Plán: Hešování, amortizace Úlohy na cvičení
6. 5. 2024 Plán: Hešování, rekurence Úlohy na cvičení
13. 5. 2024 Plán: Rekurence Úlohy na cvičení
20. 5. 2024 Plán: Dynamické programování Úlohy na cvičení

Podmínky zápočtu

Pro získání zápočtu je potřeba získat alespoň 100 bodů z minimálně 150 možných. Většina získatelných bodů bude udělena za domácí úkoly (~120 bodů), další body je možné získat z testíků na začátku cvičení (~30 bodů) a za aktivitu na cvičení. Pokud Vám budou na konci semestru nějaké body na zápočet chybět, můžeme se domluvit na zadání individuálních úkolů nebo projektu.

Domácí úkoly

Každý týden bude zadaný jeden domácí úkol a na jeho řešení bude čas 13 dní (deadline bude v neděli před cvičením 23:59). Do uplynutí termínu je možné řešení odevzdávat opakovaně. Pokud řešení stihnete odevzdat už v průběhu prvního týdne, nejpozději do následující středy ho opravím a dostanete tak šanci případné nedostatky řešení odstranit. Na cvičení po uplynutí deadlinu ukážu řešení a ještě po dobu jednoho týdne nabízím za precizní sepsání odprezentovaného řešení 1/3 původního počtu bodů (zaokrouhleno dolů).

Řešení domácích úkolů je potřeba psát jasně a srozumitelně, abych ho při opravování pochopil. Všechna tvrzení, která ve svém řešení používáte a nezazněla na přednášce, dokažte. Řešením bude typicky vymyslet nějaký algoritmus, dokázat jeho správnost a zanalyzovat časovou složitost. Algoritmus popište nejlépe pseudokódem, slovní popis je také možný, bude-li z něho algoritmus zřejmý. Za obzvlášť hezká řešení je možné udělit i vyšší než maximální počet bodů. K psaní řešení napsal Václav Končický hezký návod.

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 máte s řešením některého z úkolů problémy, včas si se mnou domluvte konzultaci a ke správnému řešení se Vás pokusím popostrčit.

Odevzdávání a opravování úkolů probíhá pomocí poštovní sovy.

Testíky

Na začátku každého cvičení bude zadán krátký testík, jehož smyslem je motivovat a ocenit připravenost na cvičení. Testy budou většinou testovat definice nebo pochopení základních pojmů a konceptů z přednášky, nebudu se ptát na žádné důkazy nebo drobné technické detaily. Přiměřenou přípravou na testík by měla být účast na přednášce (popř. samostudium probrané látky) a 15–20 minut na připomenutí před cvičením.

Užitečné odkazy