Tohle je stranka cviceni z Algoritmu a datovych struktur 2 2010/2011, ktera se kona kazde pondeli na Male Strane (MS) v 17:20 v ucebne S10. Cviceni je vedeno podle prednasky pana profesora Kucery. Prvni cviceni 4.10.2010.

Abyste jej uspesne absolvovali, musim o vas vedet. Pokud jste napsani nize na teto strance v seznamu, vim o vas. Pokud ne, napiste mi email nebo prijdte na cviceni. Deadline je 13.10.2010, (14 dni po zacatku semestru), pak uz vas neznam :o)

Konzultace budou, kdyz si o ne reknete pres email.

Zapocet

Zapocet dostanete, pokud si jej zaslouzite :o) Budete muset projit dvema sity, konkretne vypracovat domaci ukoly a vypracovat zapoctovy program.

Domací úkoly

Během semestru se objeví v CodExu 3 domací úlohy. Úlohy budou trochu obtížnější, ale bude na ně dostatek času - 3-4 týdny na každou. Abyste úkol splnili, je třeba v CodExu mít úspěšnost aspoň 100%. Na řešení úlohy bude třeba aplikovat některý algoritmus z přednášky, resp. cvičení.

Abyste získali zápočet, je třeba udělat 3 domácí úlohy. Ovšem! Aktivní účast na cvičení (nejvýše 3 absence, vědět, co se dělalo na přednášce) se rovná jednomu "domácímu" úkolu. Pokud tedy budete chodit pravidelně na cvičení, stačí vám dva domácí úkoly ze tří.

Řešení budu kontrolovat a objeví-li se dvě identická/opsaná, nemá ani jeden "autor" nárok na zápočet.

Zápočtový program/práce

Jako na jiných cvičeních bude třeba vytvořit, odladit a zdokumentovat zápočtový program nebo práci.

Zápočtový program by se měl týkat rozumně obtížného algoritmu/datové struktury a důraz je na čitelnost a asymptotiku implementace, nikoli na to, kolik různých formátů vstupu váš program umí načíst. I tak by algoritmus měl být otestovatelný.

Pokud vám programování domácích úkolů stačilo, můžete sepsat (PDF, třeba TeXaný) několikastránkový dokument o nějakém nevšedním neprobíraném algoritmu a nebo zobecněních. Tento textík by měl být napsaný tak, aby se z něj mohli učit lidé jako vy. U složitějšich struktur důkazy správnosti netřeba, u jednodušších spíše ano. I v práci bez důkazů by mělo být zhruba nastíněno, proč daná struktura/algoritmus funguje a proč zrovna takto rychle. Preferuji témata, která se neobjevují ve skriptech pro ADS.

Každé téma by se mělo vyskytnout nejvýše jednou. Nápady na programy naleznete níže, ale uvítám vaši vlastní tvořivost. Seznam prací.

Deadline na specifikaci (krátký odstavec o tom, co budete vytvářet) je 15.11.2010 12:00. Deadline na implementaci je 14.3.2011 12:00. Pozor, oba termíny nejsou splněny potom, co odešlete práci, avšak potom, co vám práci (specifikaci) schválím! V praxi to znamená, že byste měli odevzdávat specifikaci aspoň o den dříve a implementaci aspoň o týden dříve. Čím dřív, tím lépe pro vás.

Prubeh cviceni

Nulte

Predkrm: Nezavisla mnozina ve strome, dominujici mnozina v grafu, 2^n mrizka s vykousnutym polickem, nxn mrizka s libovolne vykousnutymi policky.

Hlavni chod: opakovani toku v sitich, Ford-Fulkersonuv algoritmus.

Prvni

Predkrm: Lexikograficky nejmensi rotace retezce, lexikograficke trideni retezcu.

Hlavni chod: Pripomenuti algoritmu KMP, AC. Opakovani, proc funguje v linearnim case (potencialy a.k.a. placeni penizku). Proc u AC muze byt slozitost vetsi nez linearni oproti velikosti vstupu, ale je uz linearni i s poctem vyskytu. Problem cenzora; proc obnovovani stavu funguje pro KMP, ale kazi slozitost u AC.

Druhe

Predkrm: Najit vsechny dvojice palindromu, jejichz zretezeni tvori take palindrom.

Hlavni chod: Vyreseni problemu cenzora u AC pomoci teorie automatu (vytvoreni vice nez jedne zpetne hrany). Suffixove stromy -- proc jsou linearni a proc jsou uzasne. Prevody nekolika problemu na snadne vyreseni suffixovymi stromy.

Dezert na doma: O suffixovych stromech se vice doctete v KGA nebo v tomto pojednani o stringovych algoritmech.

Treti

Predkrm: Slozitost pricitani jednicky k libovolne dlouhemu cislu.

Hlavni chod: Goldberguv algoritmus. Jak funguje, jak funguje na jednotkove siti, jakou ma slozitost a jak se da vylepsit.

Dezert na doma: O Goldbergovi je psano treba zde.

FAQ

Q: Mohu dostat zapocet dva dny pred koncem semestru, pokud jsem dosud nic neudelal?

A: Ne.

Účast

Nápady na záp. program/práci

Další příklady naleznete na stránkách dalších cvičících. Fantazii se meze nekladou. Tedy, musíte vymyslet něco, co schválím :o) Například budu rád, pokud se daný algoritmus neprobíral detailně na cvičení (ale rozšíření/zobecnění něčeho, co jsme měli, být může).