Cvičení z Algoritmů a datových struktur II

pátek od 12:20 v S7, ZS 23/24

K přednášce Algoritmy a datové struktury II Martine Mareše vedu cvičení, na kterém se zaměříme na procvičení a hlubší porozumění probírané látky formou řešení příkladů. Po dobré zkušenosti z minulého roku bude hlavní náplní cvičení řešení algoritmických úloh a příkladů k probíranému tématu ve skupinách po 3-4, které na začátku vyberu náhodně.

Pokud máte nějaký dotaz, pište na vesely (obmotané a) iuuk.mff.cuni.cz, případně se zeptejte při/po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Po domluvě mohu poskytnout konzultace.

Co jsme dělali

6. 10. Cvičil Vladan Majerech: tržnice datových struktur
13. 10. Vyhledávání jehly v kupce sena dle pánů Knutha, Morrise a Pratta + souvisejícící příklady (rýmy na str. 2 jsme neprošli)
20. 10. Vyhledávání více jehel v kupce sena a automat Aho-Corasickové. Příklady, z nichž jsme prošli prvních šest (zbylé jsou bonusové)
27. 10. Automaty KMP a Aho-Corasickové nad nekonstantně velkou abecedou (řešení pomocí BVS vs. řešení pomocí hešování). Toky v sítích, Ford-Fulkersonův algoritmus a použití na hledání hranově či vrcholově disjunktních cest. Příklady
3. 11. Toky v sítích, Dinicův algoritmus (jednotkové a celočíselné kapacity, příklady těsnosti analýzu) a aplikace toků (bipartitní párování a vrcholové pokrytí, odvodili jsme Königovu větu). Příklady (neprošli jsme pátý a bonusy)
10. 11. Toky v sítích: Goldbergův algoritmus. Příklady (prošli jsme první dva a třetí z části, zbytek třetí příkladu za DÚ :-)
17. 11. Boj za svobodu a demokracii (státní svátek)
24. 11. Diskrétní Fourierova transformace jako lineární zobrazení a matice tohoto zobrazení. Co udává 0-tá a (n/2)-tá složka výsledného vektoru? Převádění vektorů a převod kanonické báze vektorového prostoru nad komplexními čísly (na konci ukázka, jak z toho lze vydedukovat, jak vypadá inverzní zobrazení k DFT). Příklady, z nichž jsme prošli první čtyři.
1. 12. Hradlové a komparátorové (třídící) sítě. Příklady, z nichž jsme prošli prvních pět.
8. 12. Plán: Geometrické algoritmy

Podmínky zápočtu

Zápočet bude za 100 bodů. Hlavním zdrojem bodů bude řešení domácích úkolů; celkem bude za úkoly možné získat alespoň 150 bodů. 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 první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é). Nebudete-li mít na konci semestru dostatek bodů, ale nějaké přece (alespoň polovinu), můžeme se dohodnout na zápočtovém programu (tj. implementaci nějakého algoritmu; viz loňské cvičení).

Body budu rovněž dávat za předvedení řešení během cvičení. Pokud máte rádi soutěže, můžete též získat body za úspěchy v programovací soutěži ACM ICPC (až 5 bodů za vyřešenou úlohu).