Paralelní cvičení učí Dušan Knop a Tomáš Gavenčiak, s nimiž se budeme snažit obsah cvičení i podmínky zápočtů přibližně sjednotit. Účast na cvičení není povinná.

1. Příklady z 1. cvičení
2. Probírali jsme O-notaci a AVL-stromy.
3. Bavili jsme se o:
   • Univerzálním hashování (přednáška z MIT)
   • Left-leaning Red-Black stromech (prezentace, článek) a proč možná nejsou tak úžasné, jak se z prezentace zdá: LLRB considered harmful
   • (a,b)-stromech, B-stromech, 2-3-4-stromech a R-B-stromech)
   • Aplet na hraní si s BVS
4. Zaskakoval Tom Gavenčiak:
   • Násobení dlouhých čísel v $n^{1.6}$
   • Hanojské věže - převod mezi dvěma konkrétními stavy pomocí rekurze: pokud je třeba přeložit největší disk, pak je potřeba přeskládat $k-1$ disků na třetí trn, a pak zas $k-1$ disků z třetího trnu do cílové pozice.
   • Majorita posloupnosti čísel je prvek, který se vyskytuje na více než polovině pozic (takový nemusí existovat). Na majoritu jsme nejdřív vymysleli pár normálních algoritmů (AVL stromy, hashe) a pak analyzovali jednoduchý algoritmus v čase $O(n)$ a prostoru $O(1)$ registrů.
5. Příklady z 5. cvičení
6. Příklady z 6. cvičení

Úloha inverze (6b, plný počet do 13. 3.)

Navrhněte algoritmus, který spočte počet inverzí zadané permutace p, tedy „dvojic ve špatném pořadí“: $\{(a,b)|a<b,p(a)>p(b)\}$.

Úloha unikum (6b, plný počet do 13. 3.)

Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje.

Úloha medián (8b, plný počet do 13. 3.)

Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností?

Vstup je zadan jako už načtená pole jen ke čtení, nebo alternativně jako orakulum (funkce), ktere umi vratit $i$-tý prvek z dane vstupni posloupnosti.

Hint: Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností.

Úloha rovnováha (9b, plný počet do 20. 3.)

Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený. Nemáte dost paměti na to, abyste si mohli pořídit ještě jednu kopii prvků – kromě stromu si smíte pamatovat $O(1)$ hodnot (pointerů, počitadel do $n$, kopií hodnot).

Úloha merge (10b, plný počet do 20. 3.)

Navrhněte algoritmus pro sloučení dvou AVL stromů $A$ a $B$, kde všechny prvky $A$ leží před všemi prvky $B$, do jediného AVL stromu $C$. Hledáme řešení s lepší složitostí než $O(min(|A|,|B|))$.

Úloha rekurence-1 (5b, plný počet do 3. 4.)

Mějme rekurzivní algoritmus pracující v čase $T(n)$ na datech velikosti $n$. Jeho rekurence je popsána jako $$T(n) = k T(n/k) + c k n.$$

Odvoďte uzavřenou formulku pro funkci $T(n) = f(c,k,n)$ a zapište v $O$ notaci.

Kdybyste měli k dispozici tři verze tohoto algoritmu, pracující s $k = 2,3$ nebo $4$, který byste si vybrali?

Úloha rekurence-2 (6b, plný počet do 3. 4.)

Odvoďte uzavřenou formulku pro funkci $$T(n) = \frac{2}{n}(T(0) + T(1) + \cdots + T(n − 1)) + c,$$ kde $T(0) = 0$, a zapište ji v $O$ notaci.

Úloha min-strom (8b, plný počet do 3. 4.)

Minimový binární strom $M(a)$ pro zadanou posloupnost $a=(a_1\dots a_n)$ bez opakujících se prvků je definován takto:

Buď $a_i$ minimální prvek $a=(a_1\dots a_n)$; pak kořen $M(a)$ je $a_i$, jeho levý podstrom je $M(a_1\dots a_{i-1})$ a pravý podstrom $M(a_{i+1}\dots a_n)$. $M(\emptyset)$ je prázdný strom.

Pro zadanou posloupnost postavte minimový strom v čase $O(n)$.

Úloha tridena-majorita (5+5b, plný počet do 3. 4.) Majorita posloupnosti je prvek, který se v ní vyskytuje na více než polovině pozic (posloupnost tedy má jednu nebo žádnou majoritu). Na cvičení jsme dělali příklad, kdy je úkolem najít majoritu, pokud existuje, s pamětí $O(1)$ (resp. $O(\log n)$ na RAMu) v čase $O(n)$.

Pokud je posloupnost setříděná, lze zda má majoritu zjistit a zároveň ji najít mnohem rychleji, a to v čase $O(\log n)$. Popište takový algoritmus.

Pro 5 bodů navíc dokažte, že rychleji toto není možné zjistit. Pro plný počet by tento důkaz měl být jasný a úplný.

Úloha stříhání (7b, plný počet do 17. 4. 14:00)

Mějme souvislý graf $G$. Jak graf ostříhat, tedy v jakém pořadí můžeme postupně (po jednom) smazat všechny jeho vrcholy tak, aby byl po každém kroku mazání graf stále souvislý? Miřte na složitost $O(n+m)$ nebo velmi blízkou a rozeberte, jestli je to možné udělat pro každý souvislý graf nebo ukažte nějaký, kde to nepůjde.

Úloha zakázka (10b, plný počet do 17. 4. 14:00)

Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a nezáporné celočíselné váhy hran $w(u,v)$ (kde $w(u,v)=w(v,u)$) spočítal nejkratší cesty z vrcholu $s$ do všech ostatních vrcholů. Konkrétně má Láďa spočíst dvě funkce: $d(v)$ má být délka nejkratší cesty z $s$ do $v$ (nebo $\infty$, pokud taková není), a $\pi(v)$ má být předposlední vrchol na nějaké nejkratší cestě z $s$ do $v$ (nebo $\mathrm{NIL}$, pokud taková není).

Olga ale moc nevěří Láďově pečlivosti, a tak si chce výsledky ověřit, což se jí zdá jednodušší, než si je spočíst sama. Konkrétně ověří následující podmínky:

1. $d(s)=0$
2. $\pi(s)=\mathrm{NIL}$
3. $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$
4. $\forall v\in V: \pi(v)\neq\mathrm{NIL}\Rightarrow d(v) = d(\pi(v)) + w(\pi(v),v)$
5. $\forall v\in V, v\neq s: d(v) < \infty \Rightarrow \pi(v) \neq\mathrm{NIL}$

Jak může Láďa Olze dát data $d$ a $\pi$, která nejsou korektní podle Olžina zadání, ale splňují tyto ověřovací podmínky? Konkrétně: najděte takový graf, funkci $w$, vrchol $s$ a funkce $d$ a $\pi$, nebo ještě lépe popište takové případy obecněji. Za druhé upravte či doplňte podmínky tak, aby už každé řešení splňující tytpo podmínky popisovalo nejkratší vzdálenosti a cesty.

Zápočet je za zisk 100 bodů z domácích úloh a případného zápočtového programu či práce. Domácích úloh bude vypsáno za cca. 170 bodů, zveřejňovány budou výše na stránce. Na odevzdání za plný počet bodů máte 14 dní od zadání, finální termín odevzdání je konec výuky v letním semestru (konec května) krom několika posledních sérií.

Domácí úlohy odevzdávejte emailem nejlépe jako čistý text či jako PDF. Neposílejte mi fotky ručně psaného textu, ale dobře nafocené obrázky jsou v pořádku. Pokud nechcete být uvedeni ve veřejné tabulce bodů či preferujete přezdívku (nechcete třeba být vyhledatelní), napište přezdívku ke každému vašemu řešení.

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, Java, C#, hezké C, Pascal, Haskell, Lisp, Prolog, Lua; 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.

1. 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. Úlohu předrezervuji Petru Mánkovi, protože vychází z jeho nápadu; pokud o ni nebude stát, může ji mít kdokoliv.
2. 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:
   1. Implementovat ho pro několik variant parametru mezery (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně.
   2. 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.)
   3. 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.
3. ZAMLUVENO 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.)
4. Implementujte Tarjanův algoritmus na hledání silně souvislých komponent v orientovaném grafu.
5. Implementujte Rabinův-Karpův algoritmus na vyhledávání podřetězce v řetězci pomocí hashování.
6. 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.
7. Implementujte algoritmus, který rozhodne, jakou má graf modulární šířku. Tohle je poměrně čerstvá oblast výzkumu, na Internetu toho o ní moc nenajdete, nejradši to vysvětlím osobně :) 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.)

[Časem budu doplňovat.]

Tabulka