Tohle je stranka cviceni z Algoritmu a datovych struktur 1 2011/2012, ktera se kona kazde utery na Male Strane (MS) v 15:30 v ucebne S10. Cviceni je vedeno podle prednasky pana profesora Kucery.
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 2 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 všechny, tedy 2 domácí úlohy.
Ř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, respektive ktera nebyla probirana v prednasce z ADS1 nebo na Programovani.
Každé téma by se mělo vyskytnout nejvýše jednou. Nápady na programy můžete najít např. na stránce Martina Mareše, dalsi napady jsou nize v seznamu. Tak či tak uvítám vaši vlastní tvořivost.
Nektere napady mimo seznam pana doktora Marese jsou nize. Opravdu se nebojte si neco najit sami a prijit za mnou se svym napadem.
- left-leaning red-black trees (implementace/popis)
- binomialni haldy (popis)
- Fibonacciho haldy (i/p), troufnete-li si
- leftist haldy (i/p)
- splay stromy (implementace)
- B* stromy (implementace)
Studijní materiály
- Martin Mareš nechává studenty sepisovat poznámky z přednášek ADS1, které letos ale nejsou. Můžete si tedy najít výpisky z roku 2010/2011.
- Výborná kniha o ADS je Dasgupta, Papadimitrou, Vazirani - Algorithms. V češtině bohužel není, ale je dostupná v angličtině.
- Další klasikou je Introduction to Algorithms, která je hodně strukturovaná podle technik a obsahuje obvykle detailní popisy algoritmů.
- Algovize, ale o té už jste slyšeli.
Prubeh cviceni
- Prvni cviceni bylo o vypocetnich modelech.
- Druhe cviceni, pocitali jsme v polich a maticich.
- Treti cviceni za mne zaskocil Lukas Mach, bylo o RMQ a LCA.
- Ctvrte cviceni bylo o intervalovych a segmentovych stromech.
- Páté cvičení bylo o amortizaci.
- Seste cvičení bylo o RB, B a dalsich vyhledavacich stromech.