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.

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í.

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.

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ě.

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.

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.

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.

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.

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.