Podmínky zápočtu

• Na každém cvičení bude zadán jeden úkol s odevzdáním do začátku dalšího cvičení.
• Všechny úkoly budou bodovány stejně a na zápočet je potřeba dosáhnout 60% z celkového počtu bodů.
• Úkoly odevzdávejte buď přímo na cvičení nebo přes mail jako nakskenované (vyfocené) obrázky/pdf nebo v pdf. Jako předmět uvádějte "ADS 1 - úkol [id úkolu]". (ideálně vysázené v $\LaTeX u$ nebo v poněkud jednodušším LyXu).

Zajímavosti

• Quickselect v lineárním čase naleznete v tomto pdf od Martina Mareše. Konkrétně kapitola 1.6 pro průměrný případ a 1.8 pro nejhorší případ.

Úkoly

1. Úkol (do 8.3.2017 12:19:59)
   Dokažte $f(n)\in \Omega(g(n))\Leftrightarrow g(n)\in O(f(n))$.
2. Úkol (do 15.3.2017 12:19:59)
   Dokažte, že následující algoritmus je kompletní a korektní. (zastaví se a vrátí největšího společného dělitele čísel $a$ a $b$)
   nsd(a,b)
   if (a==b) $\Rightarrow$ return a
   else if (a mod 2 == b mod 2 == 0)$\Rightarrow$ return 2*nsd(a/2,b/2)
   else if (a mod 2 == 0)$\Rightarrow$ return nsd(a/2,b)
   else if (b mod 2 == 0)$\Rightarrow$ return nsd(a,b/2)
   else if (a>b)$\Rightarrow$ return nsd(a-b,b)
   else $\Rightarrow$ return nsd(a,b-a)
   
3. Úkol (do 29.3.2017 12:19:59)
   Na cvičení jsme si ukázali, jak násobit dvě dlouhá čísla $X$ a $Y$ s $n$ ciframi školním algoritmem, který funguje v $\Theta(n^2)$. Druhý přístup, který jsme uvážili byl přístup pomocí metody Rozděl a panuj, který funguje následovně. Rozepíšeme si čísla $X=A*10^{n/2}+B$ a $Y=C*10^{n/2}+D$ Součin $XY$ můžeme tedy rozepsat $XY=AB*10^{n}+(AC+BD)*10^{n/2}+CD$, čímž jsme problém součinu rozložili na 4 problémy poloviční velikosti (sčítání a násobení základem soustavy umíme v lineární složitosti vzhledem k délce zápisu čísla). Bohužel jsme si tím nepomohli a dostali jsme se ke stejné časové složitosti $\Theta(n^2)$.
   Vaším úkolem je použít metodu Rozděl a panuj (najít rozložení na menší počet podproblémů) tak, abychom dostali lepší časovou složitost než $\Theta(n^2)$.
   Nápověda: koukněte se na to, jak využít součinu $(A+B)*(C+D)$ ke snížení počtu násobení a tedy i menšímu počtu podproblémů. Chceme tedy zmenšit počet podproblémů a ne jejich velikost.
   Při použití nápovědy narazíme na drobný problém a to ten, že součin $(A+B)*(C+D)$ může mít $n/2+1$ cifer, kvůli přenosu při sčítání. Jak se tohoto problému zbavit? Buď ukažte, že nám to při výpočtu složitosti nebude vadit nebo si pohrajte s danou nápovědou tak, aby přenos nemohl nastat.
   Úkol má tedy tři části:

   1. navrhněte algoritmus, který bude rychlejší než $\Theta(n^2)$,
   2. ukažte že je skutečně rychlejší (můžete ignorovat to, že podproblémy nejsou velikosti $n/2$ ale mohou být velikosti $n/2+1$) a
   3. ukažte, jak vyřešit problém většího podproblému.
4. Úkol (do 5.4.2017 12:19:59) Zadání úkolu se liší od zadání na cvičení.
   Na hromádce máte $N$ šroubů a $N$ matiček. Každý šroub je jinak velký a každá matička je jinak velká. Chtěli bychom co nejefektivněji spárovat šrouby a příslučné matičky k sobě. Jediné co můžeme dělat, je zkusit do sebe zasadit jeden šroub a matičku. Tak zjistím, jestli je matička moc velká, moc malá, a nebo pasuje. Nic jiného se šrouby a matičkami dělat nemůžeme, na pohled nejsou rozlišitelné. Jak šrouby a matice spárovat na co nejmenší počet porovnávání v průměrném případě?
5. Úkol (do 12.4.2017 12:19:59)
   Pro graf $G=(V,E)$ určete, zda je možné ho pokrýt grafy $K_{1,2}$ (vidlička, cesta délky 2). Navrhněte algoritmus, které toto pokrytí nalezne, pokud existuje a jinak vypíše nějakou chybu. (Můžete zkusit nejdřív algoritmus pro strom.)
6. Úkol (do 19.4.2017 12:19:59)
   Chceme zjistit, zda existuje pro orientovaný graf $\vec{G}$ topologické uspořádání (topologické uspořádání je funkce $T:\vec{V}\rightarrow\mathbb{N}$ taková, že pro každou hranu $(u,v)\in\vec{E}$ platí $T(u)<T(v)$). Navrhněte dva algoritmy, které toto uspořádání definují. Jeden algoritmus používá prohledávání (BFS nebo DFS) a druhý se musí obejít bez prohledávání (použijte nějaké šikovné vlastnosti).
   Topologické uspořádání existuje právě tehdy, když orientovaný graf $\vec{G}$ neobsahuje cyklus (nechci důkaz, berte jako fakt). V algoritmech by mělo být vyřešeno jak toto detekovat a nahlásit v průběhu algoritmu a ne speciání procedurou (ověřujeme tedy, jestli je $\vec{G}$ acyklický orientovaný graf). Zároveň u obou přístupů chceme časovou složitost.
   Orientované acyklické grafy si můžeme předsatvit jako nějaký graf závislostí a topologické uspořádání nám potom určuje, jak vyhotovit jednotlivé úkoly (reprezentované vrcholy grafu) tak, aby měl vyhotovovaný vrchol splněné všechny úkoly, na kterých je závislý. Pokud bychom definovali uspořádání neostré, pak můžeme řešit úkoly paralelně.
7. Úkol (do 26.4.2017 12:19:59)
   Nechť $G=(V,E)$ je neorientovaný graf (ne nutně souvislý). Artikulace $v\in V$ je vrchol grafu $G$ jehož odebráním se v grafu $G$ zvýší počet komponent souvislosti. Navrhněte algoritmus (a ukažte jeho správnost a časovou složitost), který nalezne všechny artikulace v souvislém grafu (nemusíte řešit případ nesouvislých grafů).
8. Úkol (do 3.5.2017 12:19:59)
   Mějme strom $T=(V,E)$ a DFS očíslování vrcholů $c:V\Rightarrow\mathbb{N}$ (čas otevření vrcholu, $\forall u,v$ takové, že $u$ je rodič $v$ platí $c(u)<c(v)$ ). Nyní uvažme robota, který se nachází ve vrcholu $a\in V$ a chce se dostat do vrcholu $b\in V$. Nalezněte algoritmus, který takovému robotovi poradí kam se vydat.
   Formálněji: Mějme strom $T=(V,E,c)$ dle definice $c$ výše. Pro vrcholy $a,b$, pro které platí, že cesta z $a$ do $b$ má délku $k$ nalezněte tuto cestu v času $\mathcal{O}(k)$.
9. Úkol (do 10.5.2017 12:19:59)
   Nechť $G=(V,E,c)$ je ohodnocený orientovaný graf s $c:E\rightarrow \{1,\ldots,L\}$ (hrany mají omezené hodnoty $1,\ldots,L$). Jakou časovou složitost bude mít Djikstrův algoritmus pro takovýto graf (navrhněte datovou strukturu, kteoru bude algoritmus využívat ke zlepšení časové složitosti). Součástí řešení by měl být pseudokód algoritmu, popis datové struktury a analýza časové složitosti.
10. Úkol (no deadline, mini-seminární práce 10b)
    Nechť $T$ je vyvážený binární vyhledávací strom (AVL nebo RB). Chceme, aby nám dotaz $\text{prvek}(T,k)$ vrátil $k.$ nejmenší prvek stromu $T$ v čase $\mathcal{O}(\log n)$. Navrhněte úpravu $T$ a proceduru $\text{prvek}(T,k)$. V rámci tohoto úkolu není správně jen řešení, ale i úroveň textu řešení.
    5b je za správné řešení úkolu a 5 bodů je za text. (Měl by to být souvislý text, který by pochopil některý z vašich spolužáků, kdyby se podle něj učil. ideální je délka 1-3 strany A4. Text nesmi byt psany rucne (musi byt vysazeny v latexu, lyxu, open/libre/ms word.)

Bonusové úkoly

1. Na vstupu máme pole $A=[a_1,\ldots,a_n]$, které definuje permutaci $\pi$ tak, že $\pi(i)=a_i$. (Platí tedy, $a_i\in \{1,\ldots,n\}$ pro všecha $i\in\{1,\ldots,n\}$.) Upravte MergeSort tak, aby dostal na vstupu pole $A$ definující permutaci $\pi$ a na výstupu dostaneme počet inverzí permutace $\pi$ (tedy počet dvojic $i<j$, pro které platí $a_i>a_j$). MergeSort by si měl zachovat svou časovou složitost. Ukažte tedy i to, že vaše modifikace tuto složitost neovlivní.
2. Chceme graf $G=(V,E)$ nakreslit za pomoci co nejméně tahů (tah je libovolná sekvence hran, které na sebe navazují tak, abychom nekreslili jednu hranu dvakrát, též můžeme chápat tak, že táhneme tužkou po papíře a chceme jí co nejméněkrát z papíru zvednout). Navrhněte algoritmus, který tento problém řeší (nalezne jednotlivé tahy).
3. Orientovaný graf $G$ je polosouvislý právě tehdy, když pro každé dva vrcholy $u,v$ existuje orientovaná cesta z $u$ do $v$ nebo z $v$ do $u$ (ne nutně oběma směry$. Navrhněte algoritmus, který určí, zda je graf polosouvislý. (Body za tento úkol jsou závislé na počtu spuštění prohledávání.)
4. Průměr stromu je roven délce nejdelší cesty. Popište algoritmus, který spočítá průměr ohodnoceného stromu. Dokažte jeho správnost.
5. Navrhněte algoritmus, který detekuje v grafu existenci záporného cyklu a v případě, že existuje alespoň jeden záporný cyklus, algoritmus vypíše jeden z nich. (za polovinu bodů můžete předpokládat, že záporný cyklus je dosažitelný z konkrétního vrcholu $u$, tedy z vrcholu $u$ existuje cesta do nějakého vrcholu na záporném cyklu). Ukažte správnost a časovou složitost algoritmu.