Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst.

Při emailové komunikaci se mnou prosím vždy uveďte do předmětu text [ADS1_2016]. Pozor: pokud mi chcete psát cokoliv nesouvisejícího s domácími úlohami (organizační dotaz, žádost o konzultaci, poznámka ke cvičení, …), napište mi zvláštní email a do předmětu uveďte [ADS1_2016][!DU]. Pokud to neuděláte, mail může na delší dobu zapadnout mezi domácí úkoly. Díky.

Paralelní cvičení učí Jan Musílek, Jan Bok, Jirka Setnička a Radek Hušek, na jejichž webech se můžete inspirovat. Účast na cvičení není povinná.

• 1. cvičení
• 4. cvičení
  • Applet na hraní si s BVS + hezký souhrn/srovnání BVS a dalších datových struktur.

Úloha inverze (6b, plný počet do 14. 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 14. 3.)

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

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

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

Vstup je zadán jako už načtená pole jen ke čtení, nebo alternativně jako orakulum (funkce), které umí vrátit $i$-tý prvek z dané vstupní posloupnosti.

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

Úloha rovnováha (8b, plný počet do 28. 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 (8b, plný počet do 28. 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 datovka-2 (8b, plný počet do 18. 4.) Elektrikář si chce udržovat seznam klientů podle jejich identifikačních čísel (ID) a s údajem, zda se jedná o muže či ženu. Navrhněte datovku, která bude umět následující operace v $O(\log n)$:

• INSERT(K,C) — vloží nového klient $C$ s ID=$K$, označí ho jako ženu
• UPDATE(K) — klienta s ID $K$ přeznačí na muže
• FINDDIFF(K) — spočítej rozdíl počtu mužů a žen mezi klienty s ID $\leq K$.

*Úloha min-strom (8b, plný počet do 25. 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 25. 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í ukážeme (ukázali jsme) 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ý. ===== Požadavky na zápočet ===== Zápočet je za zisk 100 bodů z domácích úloh, opravování úloh a za případný zápočtový programu či práci. Domácích úloh bude vypsáno za cca. 170 bodů. Váš aktuální počet bodů bude uveden v tabulce na konci této stránky. Pozor: z důvodu ochrany osobních údajů nemůžu bez vašeho svolení v tabulce uvádět vaše jméno; proto mi v každém řešení domácí úlohy uveďte i svou přezdívku, pod kterou chcete být v tabulce uvedeni. Pokud přezdívku neuvedete, beru to jako implicitní souhlas k uvedení vašeho skutečného jména. 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í. K opravování úkolů: pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat navíc trojnásobek bodů tím, že se stanete korektorem pro tuto úlohu. (Např. když se stanete korektorem pro úlohu za 5b, dostanete navíc 15b.) Korektorem se můžete stát max. třikrát za semestr. Více o korektorství… 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: - programu implementující nějaký algoritmus z přednášky, - 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. ==== Korektorství ===== Pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, pošlete ho v emailu s předmětem začínajícím [ADS1_2016][korektor]. Já vaše řešení zhodnotím a pokud bude opravdu v pořádku, za opravení řešení vašich kolegů dostanete trojnásobek bodové hodnoty příkladu. Korektorem se můžete stát nejvýše třikrát za semestr. Naopak pokud si vyloženě nepřejete, aby někdo z vašich kolegů vaše řešení (jakožto korektor) četl, tzn. přejete si, abych vaše řešení opravoval osobně, pošlete email s předmětem začínající [ADS1_2016][!korektor]. Podotýkám ale, že se tak můžete připravit o často kvalitnější zpětnou vazbu, než vám dávám já. Technicky to bude fungovat tak, že když mi od někoho přijde řešení dané DÚ, přepošlu ho příslušnému korektorovi. Korektor si řešení pečlivě přečte a zhodnotí ho. Je toto řešení korektní? Pokud ne, kde udělal autor chybu? Čemu nerozumí a jak mu můžu pomoci – jakou otázkou ho nakopnu správným směrem? Dále – je toto řešení přehledné a srozumitelné? Prospělo by řešení rozdělit do více/méně odstavců? Zavést nějaké značení? Atd. Na základě tohoto zhodnocení pak korektor navrhne bodové ohodnocení. Například: <blockquote> Řešení je v zásadě správné, ale doporučil bych místo značení A, B, C, … používat indexované značení A_1, A_2, A_3, … Jinak byl důkaz poměrně přehledný. 4b </blockquote> Tyto poznámky pak korektor pošle autoru úlohy a v kopii též mě. Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a pokud budu s hodnocením souhlasit, zapíšu do tabulky získané body. Povinností korektora je opravit všechny zaslané úlohy do týdne od zaslání řešení. ==== Nápady na zápočťáky ==== - 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)**

1. 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.)
2. 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. 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.

[Časem budu doplňovat.]

Tabulka