Cvičení z Algoritmů a datových struktur I (čtvrtek 15:40, N5, LS 23/24)

Ke své paralelce přednášky z ADS 1 povedu cvičení. Na cvičení se zaměříme hlavně na procvičení algoritmického myšlení a technik z přednášky pomocí řešení algoritmických úloh. Podobné úlohy se mohou vyskytnout i na zkoušce.

Pokud máte nějaký dotaz, pište na vesely+ads1 (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení. Také budu rád, když se během cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo po cvičení (vhodný čas je třeba po cvičení, ale můžeme se domluvit i jinak). Během konzultace můžeme projít řešení příkladů nějaké staršího cvičení, pokud jste chyběli (většinou řešení nesepisuji). Můžete mě též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře naproti učebně S3), ale je lepší se ozvat předem.

Cvičení bude v zásadě vždy navazovat na předchozí přednášku (až případné na nedodělky z minula).

Co jsme dělali

22. 2.	Plán: Úvod, podmínky zápočtu (viz níže), příklady na procvičení algoritmického myšlení a model RAM, z nichž jsme stihli první čtyři. Další tři budou příště.
29. 2.	Triky s velkými čísly na RAMu, tedy příklady 5-7 z minula. Asymptotická notace a BFS: příklady, ze kterých jsme stihli první tři.
7. 3.	BFS, DFS a jejich aplikace: příklady (z části z minula), ze kterých jsme stihli prvních šest.
14. 3.	Dokončení TU, silná souvislost a Dijkstrův algoritmus: příklady (jeden z minula), ze kterých jsme stihli sedm (tedy vše kromě bonusových).
21. 3.	Hledání nejkratších, nejvyšších, nejpravděpodobnějších, atd. cest a záporných cyklů. Příklady, z nichž jsme prošli prvních šest (řešení detekce a výpisu záporného cyklu, tedy šestého příkladu).
28. 3.	Hledání minimálních koster. Příklady, z nichž jsme prošli prvních pět.
4. 4.	BVS. Příklady, z nichž jsme prošli prvních šest.
11. 4.	(a,b)-stromy a AVL stromy + související úlohy. Příklady, z nichž jsme prošli prvních pět.
18. 4.	Další stromové DS: Trie, LLRB a intervalové stromy. Příklady, z nichž jsme prošli všech sedm (tedy až na ten bonusový).
25. 4.	Hešování a amortizace. Příklady, z nichž jsme prošli všech sedm (tedy až na bonusové).
2. 5.	Rozděl a panuj. Příklady, z nichž jsme prošli první čtyři.
9. 5.	Cvičení (i moje přednáška) odpadá
16. 5.	Dynamické programování. Příklady, z nichž jsme prošli všech šest na první straně.
23. 5.	Výběr k-tého nejmenšího v lineárním čase deterministicky, tedy QuickSelect, když se pivot vybere jako medián z mediánů pětic [Pruv 10.8]. Příklady, z nichž jsme prošli všechny čtyři na první straně.

Zápočet

Zápočet bude za 100 bodů, přičemž bude možné získat alespoň 150 bodů. Hlavní zdrojem bdů bude řešení domácích úkolů. Na každý úkol (typicky algoritmickou úlohu) je čas cca 13 dní, tj. do začátku cvičení za dva týdny. I poté je možné řešení odevzdat, jen dostanete max. polovinu bodů (ale zase vám mohu poskytnout nějakou nápovědu). Úkoly jsou zadávány a odevzdávají se přes Sovu; po prvím cvičení pošlu přístupový token (pokud byste chtěli odevzdávat na papíře před cvičením, mohlo by to být také možné).

Nezakazuji řešit příklady spolu, ale řešení musí každý sepsat sám a chápat, co sepsal. Ř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ý. K sepisování řešení sepsal dobrý návod Václav Končický.

Kromě domácích úkolů budu dávat body za aktivitu, tedy předvedení řešení příkladu na cvičení (cca 2-3 za příklad).