Cvičení z Algoritmů a datových struktur I (čtvrtek 10:40, N5)

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.

Cvičení je bohužel již plné (dokonce víc než plné), zvažte prosím zápis na jiné cvičení, popř. paralelku Jana Hrice.

Pokud máte nějaký dotaz, pište na vesely+ads1 (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení (či po přednášce). 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 před cvičením, ale můžeme se domluvit i jinak). Můžete mě též najít v kanceláři S323 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře, zhruba naproti učebně S3), ale je lepší se ozvat předem.

Co jsme dělali

17. 2.	Úvod, podmínky zápočtu (viz níže), příklady na procvičení algoritmického myšlení.
24. 2.	Cvičení na model RAM, příklady (probrali jsme prvních pět).
3. 3.	Asymptotická složitost, BFS a DFS, příklady (probrali jsme prvních pět, řešení zbylých dvou si řekneme na začátku příštího cvičení).
10. 3.	DFS: hledání artikulací, orientované grafy: topologické uspořádání a jeho aplikace. Příklady (probrali jsme první čtyři, další dva budou příště)
17. 3.	Nejkratší cesty a Dijkstrův algoritmus. Příklady (zvládli jsme probrat všech sedm, tedy vyjma bonusových)
24. 3.	Nejkratší cesty se zápornými hranami. Příklady: na konci jsme stručně probrali řešení příkladů 1, 2, 3, 5 a 6, přičemž nalezení záporného cyklu pomocí Bellman-Forda necháme na příště. Když tak se zeptejte v Sově, kdyby vám nebylo něco jasného.
31. 3.	Minimální kostry. Příklady (stihli jsme prvních šest)
7. 4.	BVS. Příklady (stihli jsme probrat prvních pět)
14. 4.	BVS 2: AVL stromy a (a,b)-stromy. Příklady (stihli jsme probrat první tři; obzvláště první příklad je důležitý)
21. 4.	Trie, intervalové stromy a LLRB BVS. Příklady (stihli jsme probrat první čtyři, řešení jeřábu necháme na příště)
28. 4.	Hešování, amortizace. Příklady (stihli jsme probrat prvních pět)
5. 5.	Rozděl a panuj (hlavně rekurence pro časovou složitost). Příklady (stihli jsme probrat první tři, čtvrtý bude příště)
12. 5.	Rozděl a panuj, dynamické programování. Příklady (první čtyři příklady, pátý bude příště).
19. 5.	Dynamické programování, Quick{Select,Sort}. Příklady (probrali jsme první tři).

Zápočet

Zápočet bude za domácí úkoly, konkrétně za 2/3 bodů ze standardních úkolů (budou zadány i bonusové). 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; pokud nemáte přístupový token, dejte mi vědět (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).

Zápočet bude za alespoň 78 bodů.

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