Cvičení z ADS I, letní semestr 2013/14

Petr Kučera, KTIML MFF UK

Základní informace

Podmínky zápočtu

Na každém cvičení zadám domácí úkol. Termín odevzdání bude vždy do začátku dalšího cvičení. K udělení zápočtu bude nutné úspěšně vyřešit alespoň 1/2 celkového počtu bodů (za každý úkol bude bod).

Bylo zadáno celkem 10 úkolů a počet bodů nutný k dosažení zápočtu je tedy 5 bodů. Zápočty k této chvíli jsem zapsal do SISu. Po posledním cvičení umístím dolů na tuto stránku doplňkový úkol pro ty, kdo nemají dost bodů.

Domácí úkoly

1. cvičení (20. února 2014)

Popište implementaci zásobníku (operace push a pop) a fronty (operace enqueue a dequeue). K reprezentaci dat můžete použít buď pole nebo lineární spojový seznam. Operace by měly mít konstantní složitost.

2. cvičení (27. února 2014)

Nechť $T_1$ a $T_2$ jsou dva binární vyhledávací stromy popisující touž množinu $n$ klíčů, ukažte, že potom $T_1$ lze na $T_2$ převést s pomocí $O(n)$ rotací.

3. cvičení (6. března 2014)

Popište, jak upravit červenočerný strom tak, aby bylo možné v konstantním čase zjistit maximální/minimální prvek a ke každému uzlu následníka/předchůdce. Nápověda: Stačí si v každém uzlu pamatovat navíc maximální/minimální prvek v podstromu a odkazy na následníka/předchůdce. Jak upravit operace insert a delete a vyvažovací operace tak, aby se jejich asymptotická časová složitost nezhoršila a spravovat max/min/následník/předchůdce?

4. cvičení (13. března 2014)

Ukažte s pomocí matematické indukce, že pro funkci $T(n)$ definovanou rekurentní rovnicí $T(n)=2T(\lfloor\frac{n}{2}\rfloor+17)+n$ platí, že $T(n)=O(n\log_2n)$.

5. cvičení (20. března 2014)

Popište algoritmus, který spočítá počet inverzí v dané permutaci. Permutace $n$ prvků je dána jako pole $A$ s $n$ prvky z rozsahu $\{1, \dots, n\}$, inverzi tvoří dvojice indexů $i<j$ s $A[i]>A[j]$.

6. cvičení (27. března 2014)

Uvažme body $p_1, ..., p_n$ na reálné ose, tedy $n$-tici reálných čísel a uvažme s nimi asociované nezáporné váhy $w_1, ..., w_n$. Označme dále součet vah $W=\sum_{i=1}^nw_i$. Úkolem je najít bod na reálné ose $p$, který minimalizuje vážený součet vzdáleností od ostatních bodů. V tomto jednorozměrném případě jde o součet $\sum_{i=1}^nw_i|p-p_i|$. Ukažte, že tento bod $p$ je váženým mediánem bodů $p_1, ..., p_n$ s vahami $w_1, ..., w_n$.

7. cvičení (3. dubna 2014)

Mějme strom $T$ s ohodnocenými hranami a číslo $k$, jak zjistit, zda v $T$ existuje cesta se součtem prvků přesně $k$? Doporučuji nejprve uvážit jednodušší variantu, v níž je $T$ cesta (pokud vyřešíte alespoň tu, dostanete půl bodu).

8. cvičení (10. dubna 2014)

Popište algoritmus, který pro orientovaný graf $G=(V, E)$ zadaný pomocí matice sousednosti zjistí, zda v něm existuje vrchol $v\in V$, který má výstupní stupeň nulový a vstupní roven $|V|-1$, jde tedy o univerzální stok. Algoritmus by měl pracovat v čase $O(|V|)$.

9. cvičení (17. dubna 2014)

Popište algoritmus, který dostane na vstupu orientovaný (acyklický) graf $G=(V,E)$ a vrchol $s$ a pro každý vrchol $v\in V$ určí počet různých cest, které do něj vedou z vrcholu $s$. Algoritmus by měl pracovat v čase $O(|V|+|E|)$.

10. cvičení (24. dubna 2014)

Orientovaný graf $G=(V,E)$ nazveme polosouvislý, pokud pro každé dva vrcholy $u$ a $v$ platí, že v $G$ existuje cesta z $u$ do $v$ nebo z $v$ do $u$ (nebo obě). Popište algoritmus, který v lineárním čase zjistí, zda je daný graf polosouvislý.

Doplňkový úkol

Máme orientovaný graf $G=(V, E)$ v němž je s každou hranou $(u, v)\in E$ asociované reálné číslo $r(u, v)$, pro něž platí $0\leq r(u, v)\leq 1$. Tato hodnota reprezentuje spolehlivost komunikačního kanálu z vrcholu $u$ do vrcholu $v$, kterou si představujeme jako pravděpodobnost toho, že dojde k úspěšnému přenosu signálu z $u$ do $v$. Předpokládáme, že tyto pravděpodobnosti jsou nezávislé. Popište efektivní algoritmus, který pro dva zadané vrcholy $s$ a $t$ nalezne nejspolehlivější spojení z $s$ do $t$.