MK's wiki

Zápočtová práce může mít podobu:

1. programu implementující nějaký algoritmus z přednášky,
2. teoretického rozboru algoritmu, který vás zaujme.

V prvním případě jde o implementaci nějaké varianty datové struktury či algoritmu z přednášky. Jazyk je omezen jen schopnostmi cvičícího (tedy [v pořadí preferencí] Python, Lua, Java, C#, hezké C, Pascal, Haskell, Lisp, Prolog,; na další se případně zeptejte), implementace musí být funkční a obsahovat krátký popis (co a jak je implementováno) a testovací data či testovací kód (knihovna tedy nemusí řešit načítání dat ze souboru a pod.). Za tento druh práce budu udělovat max. 30b, pokud se bude jednat o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.

V druhém případě, tedy zejména pokud bude algoritmus či datová struktura složitější, bude práce jen teoretická, tzn. očekávám důkaz správnosti, rozbor složitosti a pseudokód. Za tento druh práce můžete očekávat do 40b, to zejména v případě, kdy si vyberete nějaký akademický článek a převyprávíte ho do mně (nezasvěcenému) srozumitelné podoby. Opět platí, že půjde-li o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.

Termín na domluvení programu je do 15. června, termín odevzdání hotové verze pak konec června. Ostatní domácí úlohy mají až na výjimky termín do konce května.

• Implementovat R-B-stromy a (2,4)-stromy a graficky ukazovat jejich korespondenci. Za prostou implementaci datové struktury dám 30b, pokud vytvoříte interaktivní aplikaci, ve které bude uživatel zadávat operace na stromech a aplikace bude zobrazovat změny datových struktur a jejich korespondenci, dám 40b. Zcela ideální platformou by byl (kvůli přístupnosti) Javascript nebo cokoliv webového; přijmu to ale i v jakémkoliv jiném (výše zmíněném) jazyce. Řešení Petra Mánka. Řešení Honzy Kytky.
  • Nedávno se objevil článek A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm, který tvrdí, že popisuje variantu RB stromů, která je k výuce vhodnější a v praxi efektivnější, než LLRB. Naimplementujte je a popište jejich funkci tak, aby to bylo srozumitelné i spolužákům.
• Shellsort je velice zajímavý třídící algoritmus. Je v jistém smyslu zkřížením bubblesortu a insertsortu, ale může mít lepší časovou složitost. Možností, co byste s ním mohli dělat, je několik:
  • Implementovat ho pro několik variant parametru mezery (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně. (Hotovo, github)
  • Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, … (vizte poslední odstavec této podkapitoly); toto bylo zjištěno experimentálně. Ověřte správnost těchto výsledků pro co největší čísla (aktuálně je známo jen prvních osm členů této posloupnosti, kdybyste přišli na devátý, dostanete celý zápočet ;). Pokud byste si vybrali toto témai, jistě by nebylo těžké vám zařídit přístup k výpočetní kapacitě fakulty.)
  • Co kdyby se měl Shellsort přednášet? Sestavte co nejzajímavěji materiál k výkladu na hodinu a půl (jako přednáška z ADS), kde se ukáže princip fungování tohoto sortu a pak dokáže několik (jednodušších) odhadů na časovou složitost pro různé hodnoty parametru mezery. Nejvhodnějším médiem by byl IPython notebook (rád předvedu, jak funguje), protože do něj lze psát matematickou notaci i kód a interaktivně vše zkoušet.
• Splay tree je velice zajímavá datová struktura. Jedná se o binární vyhledávací strom, který se přizpůsobuje dotazům, které na něj přichází – pokud přichází mnoho dotazů na tytéž prvky, strom je vynese blízko ke kořeni, aby se k nim dalo přistupovat rychle. Samozřejmě má i svoje nevýhody. Implementujte ho a napište k němu několik generátorů posloupnosti operací, které budou demonstrovat, v čem je Splay strom lepší než jiné stromy (AVL, R-B, …) a kde naopak selhává. (Generátorem posloupnosti operací myslím nějakou funkci, které řeknu, kolik operací INSERT/FIND/DELETE chci na stromu udělat [třeba za účelem testování] a on mi je vygeneruje.)
• Implementujte Rabinův-Karpův algoritmus na vyhledávání podřetězce v řetězci pomocí hashování.
• Implementujte kterýkoliv exponenciální algoritmus z přednáškových poznámek Jeffa Ericksona a pochopte důkaz správnosti a časové/prostorové složitosti dostatečně, abyste mi ho uměli vysvětlit na tabuli.
• Implementujte algoritmus, který najde modulární rozklad grafu v lineárním čase dle článku Linear-time modular decomposition of directed graphs. Pokud úkol splníte, dám za něj 45b (+5b za prezentaci); i pokud se vám to nepodaří úplně, nebude bodová odměna malá. (Potenciálně je to taky dobrý základ pro ročníkový projekt nebo bakalářskou práci do příštích let.)

• Samuel Slavkovský napsal porovnávač třídících algoritmů (rar s .net kódem), který doporučuji ke shlédnutí :)
• Úkoly ze cvika na Dijkstrův algoritmus. Vypracoval Tomáš Pavlín.
• Implementovat shellsort pro několik variant parametru mezery (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně. (Hotovo, github)

Obecně je dobrým zdrojem konference SOSA, která se soustřeďuje na *hezké* (jednoduché) algoritmy, ačkoliv i tak mohou být přístupné spíš magisterským studentům.

• nastudovat a popsat Hashlife: wiki, lifewiki, existující dobrý popis.
• Hledání modulárního rozkladu grafu v lineárním čase, Linear-time modular decomposition of directed graphs