[home]
ADS I (2022/2023)
Cvičení k přednášce Algoritmy a datové struktury I
Doporučená literatura
Organizace
K získání zápočtu je nutno nasbírat 80 bodů.
Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (za vyřešení více úkolů z jednoho cvičení je stále 10 bodů). Deadline pro odevzdání úkolu je vždy 14 dní.
Aktivita na cvičení bude odměněna $2,5$ body (více aktivity na jednom cvičení je stále $2,5$ bodů).
Úkoly i získané body nalezne na poštovní sově. Token pro zapsání bude zveřejněn na první hodině a rozeslán první týden semestru hromadným mailem. Pokud jste se k našemu cvičení přidali později, napište si o token přímo mě.
Probrané příklady
- 17.2.
- Podívali jsme se na model RAM. Jak zakódovat více čísel do jedné buňky, pokud není omezena velikost čísel. Jak pomocí instrukcí RAM definovat cyklus a funkci.
- Připomněli jsme si definice $O$, $\Omega$, $\Theta$ a seředili pár základních funkcí.
- 24.2.
- 3.3.
- DFS a BFS, klasifikace hran u obou algoritmů. Ukázali jsme jaké z hran neexistují v neorientovaných grafech.
- Opakování algoritmu pro hledání mostů v grafu.
- Prohledávání grafu vs prohledávání stavového prostoru.
- 10.3.
- DAG, topologické uspořádání a kdy je jednoznačné, topologická indukce
- Opakování nalezení silně souvislých komponent. Polosouvislost grafů.
- Dijkstrův algoritmus a jak se chová na grafech se zápornými hranami a zápornými cykly. Příště budeme s Dijkstrou pokračovat.
- 17.3.
- Dijkstrův algoritmus, odkrokování a časová složitost s různými datovými strukturami.
- Obecný relaxační algoritmus, náznak důkazu, že se nakonec vždy zastaví (pokud v grafu nejsou záporné cykly).
- 24.3.
- Dokončili jsme hledání nejkratších cest. Navíc jsme ukázali Floyd-Warshallův algoritmus pro hledání minimálních vzdáleností mezi všemi vrcholy.
- Minimální kostry - Jarník, Borůvka, Kruskal. Časové složitosti, zda vadí neunikátnost vah.
- 31.3.
- Binární vyhledávací stromy. Operace find, výpis (inorder, preorder, postorder), následník.
- Jak dokonale vyvážit BVS v lineárním čase.
- Důkaz, že dokonale vyváženým BVS chybí vrcholy pouze na poslední hladině.
- Operace Join a Split pro BVS.
- Úsporné stromy, kde každý vrchol obsahuje pouze 2 pointery místo 3.
- 14.4.
- Dokončení vyhledávacích stromů. (a,b)-stromy a operace na nich, včetně Join.
- Okénkový medián. Hledání k-tého nejmenšího prvku pomocí AVL stromu.
- 21.4.
- Hešování s přihrádkami a s otevřenou adresací.
- Konstrukce 1-univerzálního systému funkcí pomocí lineární kongurence.
- 28.4.
- Algoritmy rozděl a panuj.
- Hanojské věže. Spočítání časové složitosti se zdůvodněním, že to lépe nejde. Převádění mezi tahem a jeho pořadím.
- Kuchařková věta pro rekurentní rovnice.
- 5.5.
- Pokračování rozděl a panuj. Spletitý kabel s neadaptivním řešením. Počet inverzí v posloupnosti a jak to souvisí se tříděním čísel.
- Strassenovo násobení matic.
- 12.5.
- 19.5.
- Dynamické programování. Nejdelší rostoucí podposloupnost, editační vzdálenost.
- Diskuze o ChatGPT.