Cvičení z ADS I, letní semestr 2017/18

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ň 2/3 celkového počtu bodů (za každý úkol bude bod).

Domácí úkoly můžete odevzdávat dvěma způsoby:

Elektronicky e-mailem
V tomto případě napište řešení do těla mejlu, přiložte textový dokument, případně pdf. Nepřijímám skenované ručně psané úkoly.
Ručně psané řešení na papíře.
V tomto případě mi odevzdejte úkol na cvičení, nebo předejte jiným způsobem fyzicky na papíře. Opravený úkol vám dám k nahlédnutí na cvičení (nebo kdykoli jindy po dohodě), ale originál pak uschovám u sebe pro archivní účely. V tomto případě je také možné mi současně s ručně psaným řešením psaným na papíře poslat i jeho sken, pak vám opravené řešení na papíře vrátím.

Celkem bude zadáno 11 domácích úkolů. K udělení zápočtu je nutné mít alespoň sedm bodů.

Obsah cvičení

1. cvičení (19. února 2018)

  1. Implementace operací member, insert, delete, min, max, succ, pred v jednoduše vázaném seznamu a ve dvojitě vázaném seznamu.
  2. Implementace zásobníku a fronty pomocí jednoduše vázaného seznamu.
  3. Implementace zásobníku a fronty pomocí dvojitě vázaného seznamu.

Domácí úkol k 1. cvičení

K tomuto cvičení není zadán domácí úkol, neboť podmínky zápočtu byly specifikované až po prvním cvičení.

2. cvičení (26. února 2018)

  1. Zavedena asymptotická notace \(O\), \(o\), \(\Omega\), \(\omega\), \(\Theta\).
  2. K následujícím dvojicím funkcí \(f(n)\) a \(g(n)\) doplňte, jaký je mezi nimi vztah (tj. zda \(f(n)=o(g(n))\), \(f(n)=\omega(g(n))\), nebo \(f(n)=\Theta(g(n))\)).
    \(\mathbf{f(n)}\)\(\mathbf{g(n)}\)
    \(3n^2+2n-4\)\(12n^2+1000n+50\)
    \(50n^3+6n-4\)\(12n^2+1000n+50\)
    \(7n-4\)\(12n^2+1000n+50\)
    \(n\log_2 n\)\(n\sqrt{n}\)
    \(\log_2 n\)\(\ln n\)
    \((\log_2 n)^5\)\(\sqrt[5]{n}\)
    \(2^n\)\(2^{n+1}\)
    \(2^n\)\(2^2n\)
    \(e^n\)\(2^n\)
    \(2^n\)\(n!\)
    \(n^{20}\)\({1{,}01}^{n}\)
    \(n^{n/2}\)\(2^{n\log_2 n}\)
    \(n^{\log_2 n}\)\(2^{(\log_2 n)^2}\)
  3. Napište pseudokód algoritmu třídění vkládáním („insertion sort“) a zdůvodněte jeho složitost v nejhorším případě (zdola i shora).

Domácí úkol k 2. cvičení

Popište algoritmus binárního vyhledávání v setříděném poli (napište jeho pseudokód), odhadněte a zdůvodněte shora i zdola jeho složitost v nejhorším případě.

3. cvičení (5. března 2018)

  1. Popište co nejefektivnější algoritmus, který v zadané matici s \(n\) sloupci a \(m\) řádky nalezne maximální souvislou nulovou podmatici (tedy nulovou podmatici s co největší plochou).
    1. Triviální řešení vede na čas \(O(n^2m^2)\) (to, které jsme zmiňovali na cvičení, ve skutečnosti vede na čas \(O(n^3m^3)\), ale lze jednoduše upravit na kvadratický čas).
    2. Pro každý prvek v matici si můžeme předpočítat, kolik je napravo něj nul — výpočet tohoto počtu pro všechny prvky v matici lze provést v čase \(O(nm)\).
    3. S využitím této informace můžeme popsat algoritmus, který pracuje v čase \(O(nm^2)\). Vzhledem k symetrii tak dostaneme algoritmus, který pracuje v čase \(O(nm\cdot\min(n, m))\).
    4. Dále můžeme uvážit, že každá maximální nulová podmatice je zleva, zprava, shora i zdola ohraničena nenulovým prvkem. Pokud si ke každému prvku předpočítáme počty nul nad a pod tímto prvkem, můžeme toho využít ke konstrukci algoritmu, který pracuje v čase \(O(nm)\).
  2. Na vstupu očekáváme čísla v trojúhelníku následujícího tvaru:
       3
      7 4
     2 4 6
    8 5 9 3
          
    Cílem je najít cestu v trojúhelníku od jeho vrcholu k podstavě po číslech s největším součtem. Cesta má postupovat vždy jen dolů, přičemž na následující řádce vybíráme pokračování ze dvou sousedních číslic (po úhlopříčce, např. 7 má dole sousedy 2 a 4). V uvedeném trojúhelníku je takovou cestou posloupnost 3+7+4+9=23, což je největší součet, jehož lze dosáhnout. Vaším úkolem je popsat algoritmus, který takovou cestu najde pro daný trojúhelník v co nejrychlejším čase (ideálně lineárně v počtu čísel v trojúhelníku).
  3. Chceme implementovat asociativní pole s použitím přímého adresování ve velkém poli \(A\). Na začátku není pole \(A\) nijak inicializované a může tedy obsahovat cokoli. Inicializaci na začátku nemůžeme vzhledem k jeho velikosti provést, trvala by moc dlouho. Popište, jak implementovat přímo adresované asociativní pole v \(A\). Každý uložený objekt by měl zabrat paměť velikosti \(O(1)\). Operace vyhledávání, vložení i vymazání prvku by měla zabrat konstantní čas, stejně jako inicializace.

Domácí úkol k 3. cvičení

Napište pseudokód algoritmu pro dělení (na papíře, který znáte ze školy). Vstupem jsou čísla \(A\), \(B\) daná jako pole číslic (můžete si vybrat, zda půjde o čísla ve dvojkové nebo desítkové soustavě). Výstupem pak má být dvojice čísel \(Q\) a \(R\), kde \(Q\) je celočíselný podíl čísel \(A\) a \(B\) je zbytek po celočíselném dělení (tj. \(A=QB+R\) a \(R\lt B\)). Můžete předpokládat, že další aritmetické operace, jako sčítání, odčítání, násobení a porovnávání máte k dispozici. Jaká je složitost vašeho algoritmu v závislosti na počtu číslic v číslech \(A\) a \(B\)?

4. cvičení (12. března 2018)

  1. Reprezentace grafu:
    • Matice sousednosti \(A\). Význam \(A^k, k=1, \ldots, n\).
    • Seznam sousedů
    • Seznam hran
    • Matice incidence \(I\). Význam \(I^{T}I\) a \(I{I}^T\).
  2. Prohledávání grafu do šířky.
  3. Test toho, zda je graf bipartitní.
  4. Je dán neorientovaný graf \(G=(V, E)\), popište algoritmus, který (v lineárním čase), určí posloupnost vrcholů (vrcholy se opakují), v kterém je potřeba vrcholy projít tak, abychom použili každou hranu právě dvakrát, jednou v každém směru. Čistící vůz má za úkol vyčistit všechny silnice ve městě, každou silnici mezi dvěma křižovatkami musí projet jednou v každém směru, ale z úsporných důvodů by neměl jezdit po již vyčištěném kusu silnice.

Domácí úkol k 4. cvičení

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í stupeň roven \(|V|-1\), jde tedy o univerzální stok. Algoritmus by měl pracovat v čase \(O(|V|\).

5. cvičení (19. března 2018)

V pondělí 19. března 2018 bude místo mne učit kolega Majerech. Vzhledem k jeho povinnostem, které má před cvičením, je pravděpodobné, že se opozdí.

6. cvičení (26. března 2018)

  1. Ukázka DFS na příkladu orientovaného grafu, probrána klasifikace hran
  2. Je dán orientovaný acyklický graf \(G=(V, E)\) a vrchol \(s\in V\). Popište algoritmus, která určí v lineárním čase pro každý vrchol \(v\in V\) hodnotu \(D(v)\), která je rovna délce nejdelší cesty z vrcholu \(s\) do vrcholu \(v\).
  3. Je dán orientovaný graf \(G=(V, E)\) a vrcholy \(s, t\in V\). Popište algoritmus, který v lineárním čase určí počet různých nejkratších cest z vrcholu \(s\) do vrcholu \(t\).
  4. Popište algoritmus pro konstrukci seznamu sousedů transponovaného grafu \(G^T\), je-li dán seznam sousedů orientovaného grafu \(G\).
  5. Ukázka běhu algoritmu pro konstrukci SSK na příkladu.

Domácí úkol k 6. cvičení

Řekneme, že orientovaný graf \(G=(V, E)\) je polosouvislý, pokud pro každé dva vrcholy \(u, v\in V\) platí, že existuje cesta z \(u\) do \(v\) nebo cesta z \(v\) do \(u\). Popište algoritmus, který v lineárním čase (\(O(|V|+|E|)\)) otestuje, zda je daný graf \(G\) polosouvislý.

7. cvičení (9. dubna 2018)

  1. Ukažte graf se zápornými vahami, ale bez záporných cyklů, na němž Dijkstrův algoritmus selže.
  2. Rozmyslete si, proč se nelze negativních hran v \(G\) zbavit přičtením dostatečně elké konstanty ke všem vahám hran.
  3. Předpokládejme, že v grafu \(G=(V, E)\) jsou nezáporné váhy přidělené jak hranám, tak vrcholům. Popište způsob, který umožní hledat nejkratší cesty v takto ohodnoceném grafu.
  4. Uvažme orientovaný graf \(G=(V, E)\), kde každá hrana má přiřazenou nezápornou váhu, jež reprezentuje její propustnost \(h(u, v)\). Například může jít o situaci, kdy hrany reprezentují silnice a váha hrany pak minimální světlou výšku mostu, který silnici překlenuje. Pro danou cestu \(P\) definujeme její propustnost jako minimální propustnost hrany na této cestě. Popište efektivní algoritmus, který pro daný vrchol \(s\in V\) určí maximální propustnost cesty z \(s\) do každého vrcholu v grafu \(G\).
  5. Nechť \(G=(V, E)\) je vážený orientovaný graf s nezápornou váhovou funkcí \(w: E\to\{0, \ldots, k\}\), kde \(k\) je celé kladné číslo (ne moc velké). Upravte Dijkstrův algoritmus tak, aby ze zadaného vrcholu \(s\) nalezl nejkratší cesty v čase \(\Theta(k|V|+|E|)\).
  6. Popište jednoduchou úpravu Dijkstrova algoritmu, která nám umožní zrekonstruovat nejkratší cesty z daného počátečního vrcholu \(s\) (tj. ne jen jejich délky).
  7. Pokud je v grafu \(G=(V, E)\) z daného vrcholu \(s\) dosažitelný záporný cyklus, pak tuto situaci v Bellman-Fordově algoritmu můžeme detekovat. Jak v tom případě nalezneme nějaký konkrétní záporný cyklus?

Domácí úkol k 7. cvičení

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 interpretujeme jako pravděpodobnost toho, že tímto kanálem 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\).

8. cvičení (16. dubna 2018)

  1. Nechť \(G=(V, E)\) je orientovaný graf. Tranzitivní uzávěr grafu \(G\) definujeme jako orientovaný graf \(G^+=(V, E^+)\), kde \((u, v)\in E^+\), právě když v grafu \(G\) existuje cesta z \(u\) do \(v\). Graf \(G^-=(V, E^-)\) je tranzitivní redukcí grafu \(G\), pokud \((G^-)^+=G^+\) a počet hran v \(E^-\) je minimální možný. Popište efektivní algoritmus, který ke grafu \(G\) zkonstruuje nějakou jeho tranzitivní redukci.
  2. Floydův-Warshallův algoritmus pro hledání cest mezi všemi dvojicemi vrcholů.
  3. Jak efektivně nalézt nejkratší cyklus v grafu?
  4. Uvažme neorientovaný graf \(G=(V, E)\) s váhami hran určenými funkcí \(w:E\to {\mathcal R}\) a jeho minimální kostru \(T=(V, E_T)\).
    1. Nechť \(\{u, v\}\in E_T\) je hrana a položme \(w'\) nové váhy, které se od \(w\) liší jen tím, že váha hrany \(\{u, v\}\) je snížena. Ukažte, že \(T\) je minimální kostrou i pro upravené váhy.
    2. Nechť \(\{u, v\}\in E\setminus E_T\) je hrana a položme \(w'\) nové váhy, které se od \(w\) liší jen tím, že váha hrany \(\{u, v\}\) je snížena. Ukažte, jak z \(T\) získat minimální kostru pro upravené váhy.
    3. Ke grafu \(G\) přidáme vrchol \(v\) a připojíme jej váženými hranami k některým vrcholům v \(V\). Popište, jak upravit \(T\) na minimální kostru nového grafu.
  5. Uvažme neorientovaný graf \(G=(V, E)\) s váhami hran určenými funkcí \(w:E\to{\mathcal R}\).
    1. Rozmyslete si, že pokud je hrana \(\{u, v\}\in E\) nejtěžší hranou nějakého cyklu v \(G\), pak tato hrana není v žádné minimální kostře. (Kromě případu, kdy jsou všechny ostatní hrany v cyklech s \(\{u, v\}\) stejně těžké, i pak ale platí, že existuje kostra, která \(\{u, v\}\) neobsahuje.).
    2. Ukažte, že následující algoritmus určí nejmenší kostru grafu \(G\) a popište jeho efektivní implementaci.
      1. Setřiď hrany sestupně podle vah.
      2. Pro každou hranu \(\{u, v\}\) v pořadí sestupně dle vah postupně proveď následující krok: Pokud je hrana součástí cyklu, odstraň ji.
  6. Ukažte, že druhá nejmenší kostra není nutně jednoznačně určena ani v případě, že váhy hran jsou po dvou různé.

Domácí úkol k 8. cvičení

Je dán graf $G=(V,E)$ s váhami na hranách a množina vrcholů $S\subseteq V$, popište algoritmus, který najde minimální kostru grafu $G$, v níž jsou vrcholy z $S$ listy (pokud je to možné).

9. cvičení (23. dubna 2018)

  1. Operace min, max, succ (následník) a pred (předchůdce) v binárním vyhledávacím stromě.
  2. Uvažte následující implementaci funkce print, která vypíše prvky daného stromu v rostoucím pořadí dle velikosti.
    procedure print(T)
    
    u=min(T)
    while(u≠nil)
    do
       write(u.key)
       u=succ(u)
    done
    
    end procedure
    
    Ukažte, že tato složitost tohoto algoritmu je \(\Theta(n)\), kde \(n\) označuje počet uzlů ve stromu \(T\).
  3. Předpokládejme, že v každém uzlu \(u\) si budeme uchovávat následující dodatečné informace:
    min
    minimální prvek v podstromu uzlu \(u\)
    max
    maximální prvek v podstromu uzlu \(u\)
    succ
    následník uzlu \(u\)
    pred
    předchůdce uzlu \(u\)
    size
    počet uzlů v podstromu uzlu \(u\)
    1. Popište, jak je třeba upravit operace insert a delete, aby bylo možno tyto informace v uzlech stromu udržovat bez zhoršení časové náročnosti těchto operací.
    2. Ukažte, že dané informace lze aktualizovat v dotčených uzlech i během rotace, tedy lze tyto informace udržovat i ve vyvážených binárních vyhledávacích stromech bez zhoršení asymptotické časové náročnosti jednotlivých operací.
    3. Popište efektivní algoritmus pro nalezení \(k\)-tého nejmenšího prvku v dané množině klíčů reprezentovaných binárním vyhledávacím stromem vylepšeným o výše uvedená data.
    4. Popište efektivní algoritmus, který pro daný prvek \(x\) určí počet prvků menších než \(x\), které jsou uložené v daném binárním vyhledávacím stromě, jenž je vylepšený o výše uvedená data.
  4. Nechť \(T_1\) a \(T_2\) označují dva binární vyhledávací stromy, jež reprezentují touž množinu \(n\) klíčů. Ukažte, že \(T_1\) lze na \(T_2\) převést jen s použitím \(\Theta(n)\) rotací.

Domácí úkol k 9. cvičení

Popište algoritmus, který spojí dva binární vyhledávací stromy \(T_1\) a \(T_2\) do jednoho (tj. provede sjednocení množin reprezentovaných stromy \(T_1\) a \(T_2\)). Algoritmus by měl pracovat v čase lineárním vzhledem k celkovému počtu prvků v obou stromech.

10. cvičení (30. dubna 2018)

  1. Mějme AVL strom použitý jako slovník, kde každému uzlu odpovídá celočíselný klíč a s ním asociovaná celočíselná hodnota. Upravte strukturu AVL stromu tak, aby bylo možné rychle zjistit pro daný interval \([a, b]\) maximální hodnotu mezi těmi, jež jsou asociované s klíči v intervalu \([a, b]\).
  2. Popište algoritmus, který čte posloupnost čísel a vždy po načtení čísla vypíše medián z posledních \(k\) načtených čísel, kde \(k\) je parametr. Čas strávený při načtení každého čísla je \(O(\log k)\).
  3. Popište operaci \(\mathrm{join}(T_1, x, T_2)\), která spojí dva AVL stromy \(T_1\) a \(T_2\) s prvkem \(x\) do nového AVL stromu \(T\). Předpokládáme, že všechny klíče v \(T_1\) jsou ostře menší než \(x\) a všechny klíče v \(T_2\) jsou ostře větší než \(x\). Časová složitost operace \(\mathrm{join}(T_1, x, T_2)\) by měl být \(O(|h(T_1)-h(T_2)|)\), kde \(h(T)\) označuje výšku stromu \(T\).
  4. Popište operaci \(\mathrm{split}(T, x)\), která rozdělí AVL strom \(T\) na dva AVL stromy \(T_1\) a \(T_2\), kde \(T_1\) obsahuje prvky s klíči ostře menšími než \(x\) a \(T_2\) obsahuje prvky s klíči ostře většími než \(x\). Časová složitost operace \(\mathrm{split}(T, x)\) by měla být \(O(\log |T|)\).
  5. Navrhněte dynamickou datovou strukturu pro reprezentaci množiny celých čísel \(Q\), která umožňuje v každém okamžiku efektivně určit hodnotu \begin{equation*} \mathrm{mingap}(Q)=\min_{a, b\in Q}|a-b|\text{.} \end{equation*}

Domácí úkol k 10. cvičení

Předpokládejme, že vyhledávání klíče \(k\) v binárním vyhledávacím stromě skončí v listu. Uvažme množiny \(A\) klíčů nalevo od vyhledávací cesty, \(B\) klíčů na vyhledávací cestě a \(C\) klůčů napravo od vyhledávací cesty. Dokažte nebo vyvraťte následující tvrzení: Pro každé tři prvky \(a\in A\), \(b\in B\) a \(c\in C\) platí, že \(a\leq b\leq c\).

11. cvičení (7. května 2018)

  1. Rozmyslete si nerekurzivní implementaci třídění sléváním (merge sort).
  2. S použitím kuchařky (\emph{master theorem)} vyřešte následující rovnice:
    1. \(T(n)=2T(\frac{n}{4})+1\)
    2. \(T(n)=2T(\frac{n}{4})+\sqrt{n}\)
    3. \(T(n)=2T(\frac{n}{4})+n\)
    4. \(T(n)=2T(\frac{n}{4})+n^2\)
  3. S použitím kuchařky odhadněte shora (případně i zdola) řešení rovnice \(T(n)=4T(\frac{n}{2})+n^2\log n\).
  4. Vyřešte následující rekurentní rovnice. \begin{align*} T(n)&=T(n-1)+(n-1)\\ T(n)&=T(n-2)+n^2 \end{align*}
  5. S použitím kuchařky odhadněte shora (případně i zdola) řešení rovnice \(T(n)=4T(\frac{n}{2})+n^2\log n\).
  6. Určete řešení následující rekurentní rovnice: \begin{equation*} T(n)=T(\frac{n}{3})+T(\frac{2}{3}n)+n\text{.} \end{equation*} Jak bychom ukazovali, že je řešení správné?
  7. Vyřešte rekurentní rovnici \(T(n)=3T(\sqrt{n})+\log n\) s použitím substituce vhodné funkce za proměnnou \(n\). Nejprve položte \(m=\log n\) a poté řešte novou rekurentní rovnici pro \(S(m)=T(2^m)\).
  8. Je dáno pole \(A[1\dots n]\) obsahující ostře rostoucí posloupnost čísel. Jak v čase \(O(\log n)\) zjistit, zda existuje index \(i\), pro které platí \(A[i]=i\)?
  9. Popište algoritmus, který v čase \(\Theta(n\log n)\) určí počet inverzí v dané permutaci (neuspořádaném poli délky \(n\) s čísly \(1\ldots n\)). Je-li vstup uložen v poli \(A\), pak inverzí rozumíme dvojici indexů \(i<j\), pro kterou platí, že \(A[i]>A[j]\).
  10. Mějme pole \(X\) a \(Y\), z nichž každé obsahuje \(n\) po dvou různých setříděných čísel. Popište algoritmus pracující v čase \(O(\log n)\), který najde medián všech \(2n\) prvků.

Domácí úkol k 11. cvičení

Šroubečky a matičky: Máme \(N\) různých šroubečků a \(N\) odpovídajících matiček. Umíme pro dvojici \((\mathrm{šroubeček}, \mathrm{matička})\) rozlišit stavy „pasují“, „šroub moc velký“, „šroub moc malý“. Vymyslete, jak šrouby s matičkami co nejrychleji spárovat. Postačuje randomizovaný algoritmus s průměrným časem \(\require{cancel}\cancel{O(\log N)}\), oprava: \(O(N\log N)\).

12. cvičení (14. května 2018)

  1. Testování čipů. Předpokládejme, že máme \(n\) čipů stejného typu, které jsou schopny testovat jiné čipy téhož typu. Chceme zjistit, které jsou vadné a které jsou v pořádku. Dobrý čip odpovídá vždy správně, u špatného čipu si nemůžeme být jisti, jestli odpověděl správně nebo špatně. K dispozici máme jednoduchý test, kdy vezmeme čipy \(A\) a \(B\) a necháme je otestovat navzájem. Pokud oba odpoví „v pořádku“, pak jsou buď oba v pořádku, nebo jsou oba špatné. Pokud odpoví každý jinak nebo oba odpoví, že ten druhý je chybný, pak pouze víme, že aspoň jeden z nich je špatný, ale nevíme, který to je.
    1. Ukažte, že pokud je více než polovina čipů špatných, pak se může stát, že se nám ani za pomoci libovolného množství testů nepodaří odhalit, které jsou špatné a které jsou v pořádku. Předpokládejte nejhorší případ, tj. jako by se špatné čipy dohodly, jak obalamutit testujícího.
    2. Popište algoritmus, který za předpokladu, že nadpoloviční většina čipů je v pořádku, nalezne jeden čip, který je v pořádku. Použijte metodu rozděl a panuj s tím, že za pomoci \(\lfloor\frac{n}{2}\rfloor\) testů vytvoříte podproblém stejného typu s nejvýše polovinou čipů.
      Protože více než polovina čipů je v pořádku, znamená to, že se musí vyskytnout alespoň jedna dvojice čipů, které odpoví oba „v pořádku“. Když vezmeme všechny dvojice tohoto typu, tak mezi těmito dvojicemi musí být nadpoloviční většina těch správných, to protože v ostatních dvojicích je vždy alespoň jeden špatný, takže celkově odstraníme ve dvojicích s různými odpověďmi alespoň tolik špatných jako dobrých čipů. Stačí tedy z každé takové dvojice vzít do podproblému jeden čip.
    3. Ukažte, že dobré čipy lze identifikovat jen za pomoci \(\Theta(n)\) testů za předpokladu, že nadpoloviční většina čipů je v pořádku. Popište a vyřešte rekurentní rovnici, která počet potřebných testů.
  2. Mějme \(n\) po dvou různých čísel \(x_1, \ldots, x_n\), s nimiž jsou asociované kladné váhy \(w_1, \ldots, w_n\), pro něž platí, že \(\sum_{i=1}^n w_i=1\). Prvek \(x_k\), pro který platí, že \begin{equation*} \sum_{x_i<x_k}w_i<\frac{1}{2}\hspace{1em}\text{a}\hspace{1em}\sum_{x_i>x_k}w_i\leq\frac{1}{2} \end{equation*} nazveme váženým mediánem. Popište algoritmus, který najde vážený medián dané n-tice čísel.

Domácí úkol k 12. cvičení

Problém umístění pošt definujeme takto. Máme \(n\) bodů \(p_1, \ldots, p_n\) s asociovanými váhami \(w_1, \ldots, w_n\). Chceme najít bod \(p\) (ne nutně jeden ze vstupních), který minimalizuje součet \(\sum_{i=1}^n w_i d(p, p_i)\), kde \(d(a, b)\) je vzdálenost mezi body \(a\) a \(b\).

  1. Ukažte, že vážený medián je nejlepším řešením pro případ, kdy \(p_1, \ldots, p_n\) jsou reálná čísla a vzdálenost je absolutní hodnota rozdílu.
  2. Najděte optimální řešení pro dvourozměrný případ, kdy vzdálenost je daná manhatanskou metrikou. Tj. \(d(a, b)=|a_1-b_1|+|a_2-b_2|\).

13. cvičení (21. května)

  1. Jak rychle vynásobit matici typu $kn\times n$ maticí typu $n\times kn$ s~použitím Strassenova algoritmu pro násobení čtvercových matic? Co když otočíme pořadí (typů) činitelů v~násobení?
  2. Algoritmus pro hledání nejbližší dvojice bodů v rovině. Na vstupu předpokládejme body \(p_1, \ldots, p_n\) v rovině, tedy každý bod má přiřazenou \(x\)-ovou souřadnici a \(y\)-ovou souřadnici, vzdálenost je daná euklidovskou metrikou. Cílem je určit dvojici bodů, které mají minimální vzdálenost. Lze použít postup rozděl a panuj. Na počátku setřídíme body podle \(x\)-ové souřadnice. V algoritmu rozdělíme vstupní posloupnost bodů na dvě poloviny \(L\) a \(R\) (dle \(x\)-ové souřadnice). Rekurzivně určíme minimální vzdálenost v každé polovině \(\delta_L\) a \(\delta_R\), určíme \(\delta=\min(\delta_L, \delta_R)\). Je potřeba ještě uvážit dvojice s prvky nalevo i napravo (napříč dělící přímkou). Rozmyslete si, že stačí projít body, které jsou ve vzdálenosti nejvýš \(\delta\) od dělící přímky. Navíc pro každý bod zleva existuje jen konstantní počet kandidátů napravo. Dvojice, které jdou napříč lze tedy projít v lineárním čase a dohromady dostaneme algoritmus se složitostí \(O(n\log n)\).
  3. 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\)? Můžete nejprve uvážit jednodušší variantu, v níž je \(T\) cesta. Navíc můžete uvážit případy, kdy hrany jsou ohodnocené nezápornými čísly a kdy hrany jsou ohodnocené celými čísly (i zápornými).
  4. Mějme množinu čísel \(x_1, \ldots, x_n\) a zadané číslo \(k\). Popište algoritmus, který v očekávaném čase \(O(n)\) zjistí, zda existuje dvojice indexů \(1\leq i\lt j\leq n\), pro kterou platí, že \(x_i+x_j=k\).

Domácí úkoly k 13. cvičení

Úkoly slouží i jako doplňkové pro případ, kdy nemáte dost bodů na zápočet.

  1. Popište lineární algoritmus, který pro zadané \(k\) a (neuspořádanou) posloupnost \(n\) po dvou různých čísel najde medián a \(k\) k němu nejbližších prvků.
  2. Popište algoritmus, který dostane na vstupu \(n\) čísel z rozsahu \(0, \dots, k\), vstup si předpřipraví do vhodné datové struktury tak, že lze v konstantním čase zodpovědět pro libovolný interval \(\langle a, b\rangle\), kolik je v tomto intervalu čísel ze vstupní posloupnosti.
  3. Popište algoritmus, který setřídí \(n\) čísel z rozsahu \(0, \dots, n^3-1\) v čase \(O(n)\).
  4. Průměr stromu \(T=(V, E)\) definujeme jako \(\max_{u, v\in V}\delta(u, v)\), kde \(\delta(u, v)\) je vzdálenost \(u\) a \(v\) ve stromě \(T\). Průměr je tedy délka nejdelší cesty ve stromě \(T\). Popište efektivní algoritmus, který zjistí průměr stromu \(T\).