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

Ú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)>b(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|))$.

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.

[Časem budu doplňovat.]