Cvičení z Datových struktur 1, úterý 15:40 v S6 přes Zoom, ZS 2021/2022

\( \def\cO{\mathcal{O}} \def\cH{\mathcal{H}} \def\cU{\mathcal{U}} \def\LCP{\mathrm{LCP}} \def\reals{\mathbb{R}} \)

Rozbalit všechna řešení a ostatní skryté části níže.

4. 1. 2022

Zkuste si ve hře The Deadlock Empire střídavě krokovat kódy více vláken tak, aby došlo k nějaké nechtěné situaci -- souběžné vykonání kritické sekce, deadlock, zacyklení, porušení assertu, ... Jiné příklady nejsou, od minulého cvičení se nekonala žádná přednáška. Poslední cvičení tak můžeme věnovat dotazům.

21. 12. 2021

Příklady:

• Mějme zjednodušený dvourozměrný intervalový strom, tedy binární strom podle souřadnice x, který má v každém vrcholu pole bodů z daného x-ového intervalu seřazené podle y. Dvourozměrné intervalové dotazy (na počet bodů v obdélníku) zde trvají $\cO(\log^2 n)$, protože potřebujeme binárně vyhledávat v $\cO(\log n)$ polích. Ukažte, že přidáním (lineárně mnoha) pointerů z každého pole na správná místa v obou polích v synech můžeme složitost snížit na $\cO(\log n)$. Pro $d$-rozměrný strom pak dostaneme $\cO(\log^{d-1} n)$.
  Pro každý vrchol $v$ a jeho syna $w$ povede z každého prvku pole ve vrcholu $v$ pointer na stejný prvek nebo největší menší v poli $w$. Binární vyhledávání poté provedeme jen v největším poli v kořeni. Pro nalezení odpovídajících hranic v poli v synovi pak stačí jen použít pointery a příp. se posunout o jeden prvek vedle. Během vyhledávaní ve stromě řazeném podle x-ové souřadnice tak jen s konstantním zpomalením udržujeme hranice v poli v aktuálním vrcholu. Této metodě se říká Fractional cascading a obecně umožňuje i propojování polí se stejným řazením ale různými prvky.
• Mějme 2-d strom, tedy binární strom, kde rozdělujeme rovinu střídavě podle os x a y. Ukažte, že dvourozměrný intervalový dotaz (na počet bodů v obdélníku) může trvat až $\Omega(\sqrt{n})$, konkrétně najděte množinu bodů uloženou ve stromě a dotaz, který bude trvat takto dlouho.
  Do stromu uložíme množinu $\{(i,i)\mid 1 ≤ i ≤ n\}$ a budeme vyhledávat $\{0\}\times \reals$. Při porovnání podle x se musíme vydat vždy doleva, při porovnání podle y musíme pokračovat v obou podstromech. Na každé druhé úrovni se nám tak zdvojnásobí počet vrcholů, které musíme projít. Celková složitost pak je $\Theta(2^{\log n\over 2}) = \Theta(\sqrt{n})$.
• Mějme sufixové pole $S$ pro text $T$. Předpočítat pole $L$ délek nejdelších společných prefixů (LCP) sousedních řetězců v $S$ lze přímočaře v kvadratickém čase (každé dva sousední porovnáme znak po znaku). Ukažte, že při předpočítávání v pořadí od nejdelšího sufixu po nejkratší můžeme dostatek porovnání přeskočit, aby jich bylo jen lineárně.
  Nejprve si vytvoříme reverzní pole $R$: $S[R[i]]=T[i:]$. Spočítáme LCP celého $T$ a jeho následníka v $S$, tedy $L[R[0]]\leftarrow \LCP(T,S[R[0]+1])$. Máme-li dva sousední sufixy v $S$ a odřízneme od každého první znak, dostaneme jiné dva sufixy, které opět musí být v $S$ ve stejném pořadí a jejich společný prefix je právě o 1 menší. Mezi nimi můžou být v $S$ i jiné prvky, ale všechny budou mít aspoň prefix této délky stejný. Máme-li tedy spočítáno $L[R[i]]$ víme, že $L[R[i+1]] \ge L[R[i]] - 1$ a tedy stačí začít porovnávat $S[R[i+1]]$ a $S[R[i+1]+1]$ až od tohoto znaku. Nakonec bude potřeba maximálně $2|T|$ porovnání, protože všechny sufixy mají délku maximálně $|T|$ a v každém z $|T|$ kroků se posuneme maximálně o jedničku zpět.

14. 12. 2021

Přiklady:

• Vymyslete algoritmus na nalezení všech výskytů podřetězce $P$ délky $n$ v textu $T$ délky $m$ pomocí hešování v průměrném čase $\cO(n+m+kn)$, kde $k$ je počet výskytů. (Možná jste jej už viděli na ADS2.)
  Jde o Rabin-Karpův algoritmus. Jako hešovací funkci použijeme $h_a(x) = \sum_{i=1}^{|x|} x_i a^{|x|-i}\mod p$, kde $x$ je řetězec. Spočítáme hash $P$ a poté jej porovnáváme s heši všech podřetězců $T$ stejné délky. Využijeme toho, že z heše jednoho podřetězce lze určit hash o jeden znak vedle odečtením odebíraného znaku vynásobeného $a^{|x|-1}$, pronásobením $a$ a přičtením nového znaku (vše $\mod p$). Hešování nám samo o sobě může dávat falešně pozitivní výsledky (stejně jako třeba Bloomovy filtry), takže je třeba při shodě ještě podřetězec porovnat s $P$ znak po znaku.
• Vymyslete algoritmus na nalezení podřetězce $P$ délky $n$ v textu $T$ délky $m$ v čase $\cO(n+\log m)$, máte-li předpočítané sufixové pole $S$ k $T$ a pro každou dvojici sufixů $T$ umíte zjistit délku jejich nejdelšího společného prefixu (LCP) v konstantním čase. (Tohle se ukázalo, že asi není úplně stihnutelné během cvičení, část řešení později označena za nápovědu.)
  V sufixovém poli máme všechny sufixy $T$ lexikograficky seřazené, takže v něm můžeme binárně vyhledávat a zajímá nás takový sufix, jehož prefixem je právě $P$. Při porovnávání řetězců musíme porovnávat jen ty správné části, aby nás stála jen $\cO(n)$ všechna porovnání dohromady namísto každého z nich. Cílem tedy je využívat informace o společných prefixech mezi prvky $S$ k udržování informací o společném prefixu $P$ s relevantními řetězci v $S$.
  Během binárního vyhledávaní máme vždy minimální $i_{left}$ a maximální $i_{right}$ index v S, které nám určují zmenšující se oblast, v níž ještě vyhledáváme, a střední index $i_{mid} = \lfloor(i_{left}+i_{right})/2\rfloor$, podle kterého dělíme. Zároveň si udržujeme délku společného prefixu $P$ s hraničními sufixy $d_{left}=\LCP(P, S[i_{left}])$, $d_{right}=\LCP(P, S[i_{right}])$, tu na začátku spočítáme porovnáním znak po znaku.

  ---

  Krok binárního vyledávání: Vybereme hranici s delším společným prefixem s $P$ ($d_{left}$ vs. $d_{right}$), zjistíme $\LCP$ hranice se středem $S[i_{mid}]$. Z výsledku buď umíme rovnou určit $\LCP(P, S[i_{mid}])$ a jestli pokračujeme v levé nebo pravé části, nebo začneme porovnávat $S[i_{mid}]$ a $P$ od prvního znaku, kde by se mohly lišit -- tento znak je dále než v předchozí iteraci, takže dohromady dostaneme jen $\cO(n)$ porovnání.

  Předpokládáme, že $d_{left} \lt |P|$ a $d_{right} \lt |P|$, jinak už bychom měli podřetězec nalezený.

  • $d_{left} \ge d_{right}$:
    • $\LCP(S[i_{mid}], S[i_{left}]) \lt d_{left}$: Na prefixu délky $d_{left}$ je $S[i_{mid}]$ lexikograficky větší než $S[i_{left}]$ a tedy i než $P$, pokračujeme v levé části. $i_{right} \leftarrow i_{mid}$ $d_{right} \leftarrow \LCP(S[i_{mid}], S[i_{left}])$
    • $\LCP(S[i_{mid}], S[i_{left}]) \gt d_{left}$: Na prefixu délky $\LCP(S[i_{mid}], S[i_{left}])$ je $P$ lexikograficky větší než $S[i_{left}]$ a tedy i než $S[i_{mid}]$, pokračujeme v pravé části. $i_{left} \leftarrow i_{mid}$ $d_{left}$ beze změny
    • $\LCP(S[i_{mid}], S[i_{left}]) = d_{left}$: $P$ a $S[i_{mid}]$ se shodují minimálně na prefixu délky $d_{left}$, pokračujeme v jejich porovnávání od dalšího znaku, dokud nenajdeme odlišnost. Je-li $P$ prefixem $S[i_{mid}]$ končíme, jinak upravíme $i_{left}$ nebo $i_{right}$ a příslušné $d_{?}$ nastavíme na právě zjištěnou délku shodého prefixu s $P$.
  • $d_{left} \lt d_{right}$: Symetricky.

  Řešení lze upravit pro získání lexikograficky nejmenšího/největšího sufixu s daným prefixem a tím i všechny výskyty $P$ v $T$.

  ---

  (Převzato ze starších poznámek M. Kouckého.)
• V lineárním čase lze k $S$ dopočítat pole LCP (Longest Common Prefix) $L$, které obsahuje pro každý sufix textu $T$ délku nejdelšího jeho prefixu, který je shodný s následujícím sufixem v $S$ (viz příští cvičení). Ukažte, že pak lze v lineárním čase dopočítat LCP všech dvojic sufixů, které by mohl potřebovat algoritmus z předchozího příkladu.
  Všechny stavy binárního vyhledávání lze popsat binárním stromem v jehož listech jsou možné výstupy; tento strom má $\cO(T)$ vrcholů a každý z nich má pevně přiřazené hodnoty $\LCP(S[i_{mid}], S[i_{left}])$ a $\LCP(S[i_{mid}], S[i_{right}])$, které by nás mohly zajímat. Těchto hodnot je tedy také jen lineárně a vždy představují minimum v příslušném intervalu pole $L$: $LCP(S[i], S[j]) = \min_{k=i}^{j-1} L[k]$ pro $i\lt j$. Hodnoty v listech lze spočítat v konstantním čase z pole $L$, hodnoty ve vnitřních vrcholech lze spočítat také v konstantním čase z využitím hodnot v synech. Během binárního vyhledávání se pak musíme současně pohybovat v tomto stromě, což nám složitost nezhorší.

  ---

  Alternativně můžeme nad $L$ vybudovat datovou strukturu odpovidající na Range minimum queries, která dokáže hledat minimum v $L$ pro libovolné intervaly a tedy odpovídat na LCP mezi libovolnými dvěma prvky $S$ a to i v konstantním čase s lineárně velkými předpočítanými daty. O RMQ se můžete dočíst i ve skriptech Krajinou grafových algoritmů od Martina Mareše v kapitole Dekompozice stromů, příp. doslechnout na jeho přednášce Grafové algoritmy.

7. 12. 2021

Úkol není, deadline pro hash_experiment se posouvá na tři týdny od zadání. Pro univerzalitu a nezávislost hešovacích funkcí používáme rozšíření značení z přednášky. Příklady:

1. Dokažte, že pokud je $\cH$ $c$-přibližně 2-nezávislý, pak je i $c$-přibližně univerzální.
   Z definice 2-nezávislosti nás zajímají jen případy, kdy dojde ke kolizi: $∀x_1,x_2∈\cU, x_1\ne x_2, ∀a∈[m]: Pr_{h∈\cH}[h(x_1) = a \land h(x_2) = a] ≤ c/m^2$. Sečteme pravděpodobnost kolize ve všech přihrádkách: $Pr_{h∈\cH}[h(x_1) = h(x_2)] = \sum_{a∈[m]} Pr_{h∈\cH}[h(x_1) = a \land h(x_2) = a] ≤ m\cdot c/m^2 = c/m$.
2. Dokažte, že pokud je $\cH$ $c$-přibližně $k$-nezávislý pro $k>1$, pak je i $c$-přibližně $(k-1)$-nezávislý.
   Stejně jako v předchozím příkladu sečteme přes možné výběry jedné z přihrádek: $∀x_1, \dots, x_k ∈ \cU$ navzájem různá a $∀a_1, \dots, a_{k-1} ∈ [m]:$ $\;\;\;Pr_{h∈\cH}[h(x_1) = a_1 \land \dots \land h(x_{k-1}) = a_{k-1}] =$ $\;\;\;=\sum_{a_k∈[m]} Pr_{h∈\cH}[h(x_1) = a_1 \land \dots \land h(x_k) = a_k] ≤ m\cdot c/m^k = c/m^{k-1}$.
3. Mějme systém $\cH_1 = \{h(x) = x\}$ o jedné funkci, kterou je identita (tedy $\cU = [m]$). Je $\cH_1$ $c$-přibližně univerzální pro nějaké $c$? Je $\cH_1$ $c$-přiblizně $k$-nezávislý pro nějaká $k$ a $c$?
   U různých prvků nemůže nastat kolize, systém je univerzální pro libovolnou konstantu $c$: $∀x,y∈\cU, x\ne y: Pr_{h∈\cH_1}[h(x) = h(y)] = 0 ≤ c/m$ pro lib. $c$. Každý prvek má pevně danou přihrádku, systém tak není ani 1-nezávislý pro žádnou konstantu $c$: $∀x∈\cU, ∃a∈[m]: Pr_{h∈\cH_1}[h(x) = a] = 1 > c/m$ pro lib. pevně zvolené $c$ a dostatečně velké $m$.
4. Mějme systém $\cH_2 = \{h_a(x) = a\mid a∈[m]\}$ všech konstantních funkcí. Dokažte, že $\cH_2$ je (přesně) 1-nezávislý? Dokažte, že $\cH_2$ není ani přibližně 2-nezávislý ani přibližně univerzální.
   Je 1-nezávislý: $∀x∈\cU, ∀a∈[m]: Pr_{h∈\cH_2}[h(x) = a] = 1/m$. Není 2-nezávislý, protože výběrem přihrádky pro libovolný prvek máme určenou přihrádku i pro všechny ostatní: $∀x,y∈\cU, x\ne y, ∀a∈[m]: Pr_{h∈\cH_2}[h(x) = a \land h(y) = a] = Pr_{h∈\cH_2}[h(x) = a] = 1/m > c/m^2$ pro lib. pevně zvolené $c$ a dostatečně velké $m$. Není univerzální, protože kolize dvou prvků nastane vždy: $∀x,y∈\cU, x\ne y: Pr_{h∈\cH_2}[h(x) = h(y)] = 1 > c/m$ pro lib. pevně zvolené $c$ a dostatečně velké $m$.

30. 11. 2021

Budete-li se učit ze skript Martina Mareše, tak pozor na to, že používá trochu jinou definici univerzality a nezávislosti. Příklady:

1. Ukažte, že v hešovací tabulce velikosti $m=n^2$ s $n$ prvky dojde ke kolizi s pravděpodobností maximálně $1/2$, předpokládáme-li zcela náhodnou hešovací funkci.
   $Pr[\text{kolize}] = Pr[∃i\ne j∈[n]: h(i)=h(j)] \le {n\choose 2}\cdot {1\over m} \le {n^2\over 2}\cdot {1\over n^2} = {1\over 2}$
2. Spočítejte jaký nejmenší počet lidí $n$ se musí sejít, aby byla pravděpodobnost aspoň 1/2, že někteří dva z nich mají narozeniny ve stejný den. Předpokládejte $m=365$ dní v roce s rovnoměrným rozdělením pravděpodobnosti, že neznámý člověk bude mít ten den narozeniny. Překvapivě malý výsledek se označuje jako narozeninový paradox.
   Spočítejte nejprve pro konkrétní $n$ pravděpodobnost, že nenastane kolize; dosazováním poté najděte správnou hodnotu. Z přesného vzorce nemusí být vidět, jakou hodnotu $n$ zvolit, zkuste k němu spočítat jednodušší horní odhad.
   $n=23$
   Pravděpodobnost, že nenastane kolize pro konkrétní $n$, je $p_n = 1 \cdot \left(1-{1\over m}\right) \cdot \left(1-{2\over m}\right) \cdots \left(1-{n-1\over m}\right)$; postupně pronásobujeme pravděpodobnosti, že následující člověk nezpůsobí kolizi. Pro zjištění přibližného $n$ odhadneme pravděpodobnost následovně: $p_n\le 1 \cdot e^{-{1\over m}} \cdot e^{-{2\over m}} \cdots e^{-{n-1\over m}} = e^{-{1\over m}(1 + 2 + \cdots + n-1)} = e^{-{n(n-1)\over 2m}} \le e^{-{(n-1)^2\over 2m}}$. Pravděpodobnost omezíme $1/2$: $e^{-{(n-1)^2\over 2m}} \le 1/2$ $-{(n-1)^2\over 2m} \le \ln{1/2}$ $(n-1)^2 \ge 2m\ln{2}$ $n \ge \sqrt{m\ln{4}} + 1 \approx 23.5$ Podmínku tedy určitě splňuje skupina 24 lidí, dosazením do přesného vzorce zjistíme, že i 23, ale 22 už ne: $p_n = {m\over m} \cdot {m-1\over m} \cdot {m-2\over m} \cdots {m-n+1\over m} = {m!\over (m-n)!\cdot m^n}$, $p_{23} \approx 0.49,$ $p_{22} \approx 0.52.$

23. 11. 2021

Cvičení se koná přes zoom, příklady nakonec nejsou, takže půjde spíš o konzultace.

16. 11. 2021

Příklady:

1. Ukázat, že LRU není kompetitivní s OPT, mají-li stejnou paměť.
2. Spočítat I/O složitost rekurzivního násobení matic.
   Matice dělíme na čtvrtiny a rekurzivně provádíme pronásobení příslušných podmatic s přičtením výsledku do cílové matice -- veškeré přístupy do paměti se tak dějí až na nejnižší vrstvě. Předpokládáme vysokou cache (M ∈ O(B^2)). Zaostříme na úroveň rekurze, kde se nám vlezou do paměti všechny tři matice. S vysokou keší má každá rozměr Θ(√M)×Θ(√M). Celkem máme na této úrovni Θ((N/√M)^2) podmatic a každou zpracováváme Θ(N/√M)-krát; jako při násobení matice o rozměrech Θ(N/√M)×Θ(N/√M). Načtení jednoho řádku podmatice nás stojí O(√M/B). Vysoká cache nám mj. zajistí, že je to aspoň jeden blok, takže nepotřebujeme aditivní jedničku. Špatné zarovnání vyřešíme dvojnásobnou konstantou v O. Načtení jedné podmatice nás pak vyjde na O(M/B). Celkem dostaneme I/O složitost O((N/√M)^3 ⋅ M/B) = O(N^3/(B√M)), nevlezou-li se do paměti všechny matice najednou; jinak odpovídá složitost sekvenčnímu čtení. Za předpokladu vysoké keše tedy máme složitost O(N^3/(B√M) + N^2/B + 1). (Sekvenční přístup zároveň potřebujeme pro počáteční vynulování cílove matice.)

9. 11. 2021

Příklady:

1. Spočítat časovou a I/O složitost rekurzivního transponování, když v každém kroku rekurze provedeme zvlášť prohození podmatic a rekurzivní transpozici.
2. Spočítat I/O složitost merge sortu, kde máme vždy v jednom poli za sebou setřízené posloupnosti a po dvojicích je sléváme do posloupností dvojnásobné délky ve druhém poli. (Základem je tedy cyklus, ne rekurze.)
3. Spočítat I/O složitost (a časovou) k-cestného merge sortu. Ten narozdíl od předchozího algoritmu slévá vždy k posloupností současně a pro výběr minima používá k-prvkovou haldu. Předpokládáme M ≥ 2k⋅B, aby se nám do paměti vlezla halda i potřebné části rozečtených posloupností.

2. 11. 2021

Cvičení se prezenčně nekoná; ve stejném čase je možnost konzultací přes zoom, bližší informace rozeslány mailem (napište pokud nedošel).

26. 10. 2021

Ukázána varianta (a,b)-stromu, která má hodnoty i ve vnitřních vrcholech (každý klíč je ve stromě jen jednou), viz skripta Martina Mareše. Příklady:

1. Provést zadané operace na daném (2,3)-stromu.
2. Jaký je potenciál splay stromu, který je cesta?
3. Jaký je potenciál splay stromu, který je úplný binární strom hloubky k.

19. 10. 2021

Pro účely cvičení a úkolu zavedena naivní implementace splay stromů, která provádí jen jednoduché rotace. Příklady:

1. Navrhnout posloupnost operací, která vytvoří strom lineární hloubky v naivní i standardní implementaci.
2. Navrhnout posloupnost k operací s celkovou složitostí Ω(kn) v naivní implementaci. Co se stane při použití stejné posloupnosti ve standardní implementaci?
3. Navrhnout operace split a join s logaritmickou amortizovanou složitostí. Split ve vrcholu strom rozdělí na strom se všemi menšími prvky a strom se zbylými prvky. Join dvou stromů, z nichž jeden má všechny prvky menší než každý prvek ve druhém, tyto stromy spojí do jednoho.
4. Navrhnout alternativní implementaci insert/delete využívající split/join.

12. 10. 2021

Ukázali jsme si, jak funguje operace splay a kdy ji použít. Amortizovanou logaritmickou složitost jsem jen zmínil bez důkazu. Dvojrotace je možné poskládat ze dvou jednoduchých rotací, jen pozor na jejich pořadí. Rotace je lepší vztáhnout k hranám -- rotování konkrétní hrany je jednoznačná (a možná i intuitivnější) operace narozdíl od rotování vrcholu nebo ve vrcholu, kde potřebujeme znát i směr. Příklady:

1. Provést splay v daném stromě.
2. Amortizace delete v líně vyvažovaných stromech.
3. Složitost projití celého binárního stromu pomocí funkce následníka.

5. 10. 2021

Úvodní informace. Příklady:

1. Úprava natahovacího pole, aby se umělo i zmenšovat.
2. Amortizovaná složitost binárního inkrementování (v počtu překlopených bitů).