MK's wiki

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Cvičení z algoritmů a datových struktur I 2013/14 ======

Paralelní cvičení učí [[http://kam.mff.cuni.cz/~knop/vyuka/|Dušan Knop]] a [[http://gavento.ucw.cz/|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á.

===== Co se dělalo na cvičení =====
  - {{:teaching:ads1_01-cv.pdf|Příklady z 1. cvičení}}
  - Probírali jsme O-notaci a [[https://en.wikipedia.org/wiki/AVL-tree|AVL-stromy]].
  - Bavili jsme se o:
    * Univerzálním hashování ([[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-8-universal-hashing-perfect-hashing/|přednáška z MIT]])
    * Left-leaning Red-Black stromech ([[http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf|prezentace]], [[http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf|článek]]) a proč možná nejsou tak úžasné, jak se z prezentace zdá: [[http://read.seas.harvard.edu/~kohler/notes/llrb.html|LLRB considered harmful]]
    * [[https://en.wikipedia.org/wiki/(a%2Cb)-tree|(a,b)-stromech]], [[https://en.wikipedia.org/wiki/B-tree|B-stromech]], [[https://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree|2-3-4-stromech]] a [[https://en.wikipedia.org/wiki/Red_black_tree|R-B-stromech]])
    * [[http://people.ksp.sk/~kuko/bak/index.html|Aplet na hraní si s BVS]]
  - 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ů.
  - {{:teaching:ads1_05-cv.pdf|Příklady z 5. cvičení}}
  - {{:teaching:ads1_06-cv.pdf|Příklady z 6. cvičení}}
  - DFS a BFS -- opakování, vertex cover na stromech, průměr stromu, duch v bludišti, bludiště se dvěma roboty ovládanými jedním ovladačem.

===== Domácí úkoly =====

**Ú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:

  - $d(s)=0$
  - $\pi(s)=\mathrm{NIL}$
  - $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$
  - $\forall v\in V: \pi(v)\neq\mathrm{NIL}\Rightarrow d(v) = d(\pi(v)) + w(\pi(v),v)$
  - $\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.

**Úloha housenka (9b, plný počet do 24. 4. 14:00)**
Najděte v zadaném stromě housenku na co nejvíce vrcholech. <i>Housenka</i> je podgraf, který se skládá z cesty
na jejímž každém vrcholu jsou až čtyři listy (nožičky), ale můžou tam být i vrcholy bez nožiček. Není to totéž,
co nejdelší cesta, protože nejde o housenku co nejdelší, ale na největším počtu vrcholů (tedy i s nožičkami). Řešení by mělo být v $O(n)$.

**Úloha kůň (8b, plný počet do 24. 4.)**
Na jedné šachovnici $N\times N$ žil byl kulhavý kůň. To je je šachová figurka, která v sudém tahu táhne
jako jezdec, v lichém jako pěšec (o 1 dopředu, vždy stejným směrem). Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?

**Úloha polosouvislost (9b, plný počet do 15. 5.)**

Řekněme, že orientovaný graf $G$ je //polosouvislý//, když pro každé dva vrcholy $u$ a $v$ platí, že existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Toto je silnější vlastnost, než slabá souvislost grafu, ale slabší vlastnost, než silná souvislost grafu. Jak v čase $O(m+n)$ zjistit, zda je $G$ polosouvislý?

**Úloha holubi (9b, plný počet do 15. 5.)**
Každý poštovní holub, je-li vypuštěn se zprávou, s ní doletí jen na jedno místo, které je pro konkrétního holuba pevné. Ve spolku pěstitelů holubů má každý člen holuby, kteří mohou doručit zprávu k několika dalším členům. Svolat všepěstitelské setkání je možné jen tak, že ho jeden ze členů vyhlásí rozesláním zpráv všem členům, na které má holuby, a ti pak pošlou zprávu dál svými holuby.

Když znáte strukturu spolku, v čase lineárním s počtem zúčastněných holubů a členů zjistěte, zda vůbec existuje někdo, kdo má možnost setkání všech členů svolat.

**Úloha abeceda (9b, plný počet do 22. 5.)**
Nalezli jste knihovnu ztracené civilizace a zkoumáte její abecedu o $n$ prapodivných znacích.
Každá kniha má na svém hřbetu nápis touto abecedou a doufáte, že jsou knihy seřazené abecedně (lexikograficky).
Rádi byste věděli, jestli z pořadí knížek lze zjistit jednoznačné pořadí znaků abecedy, jestli je pro to
informací málo, či zda dokonce takové pořadí nemůže existovat (a knihovnu tedy někdo přeházel).

Zadání si představte třeba jako seznam slov bez mezer z abecedy "a-z", otázkou je pak pořadí znaků "a-z"
v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete
předpokládat, že se každé písmeno mezi nápisy vyskytne.

**Úloha negative-floyd (8b, plný počet do 22. 5.)**

Co udělá F-W algoritmus na grafu se zápornými vahami, ale bez záporných cyklů?
A co udělá F-W na grafu se záporným cyklem? Svá tvrzení dokažte.

Pro bonus vysvětlete (potenciálně chybný) výsledek algoritmu a význam získaných hodnot
(tedy zda výsledná čísla přeci jen něco popisují).

**Úloha cheating (7b, plný počet do 22. 5.)**

Závod bludištěm z živých plotů! Jste rozhodnuti vyhrát a to i za cenu malé ... zkratky, kterou
pravidla zapomněla zmínit. Nejste ale ochotni se křovím prodrat víc než jednou, ještě by si toho někdo
všiml a mohl by to ... špatně pochopit.

Bludiště je popsáno grafem se startem, cílem, délkami hran a dvěma typy hran; chodby bludištěm
a zkratky křovím, kterými se ještě jde prodrat. Navrhněte algoritmus pro nejkratší cestu do cíle
v co nejlepším čase.

**Úloha listy-kostry (10b, plný počet do 22. 5.)**

Máme dánu $U$ jako podmnožinu vrcholů souvislého grafu $G$ s váhami hran $w$.
Najděte minimální kostru $G$ ze všech takových koster, které mají vrcholy z $U$ jako listy.
Algoritmus by měl být stejně rychlý jako jiné vám známé algoritmy na min. kostru a měl by
rozpoznat situaci, že taková kostra neexistuje.

===== Požadavky na zápočet =====

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:
  - 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, 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.


{{page>teaching:bits:ads_zapoctaky}}


===== Body za úkoly =====

[[https://docs.google.com/spreadsheet/ccc?key=0Aoow9Tms8HyddFUxWW5lZGFEMFo1ZXpwN1ozeUNUOEE&usp=sharing|Tabulka]]



{{url>https://docs.google.com/spreadsheet/pub?key=0Aoow9Tms8HyddFUxWW5lZGFEMFo1ZXpwN1ozeUNUOEE&single=true&gid=0&output=html&widget=true}}