Vladan Majerech - NTIN060 Algoritmy a datové struktury
Last Modified: 5.6.2019
Index
zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8, cvičení 9, cvičení 10, cvičení 11, cvičení 12, cvičení 13
Pro získání zápočtu z NTIN060 je potřeba získat (2/3 z možných bodů za domácí úkoly zadávané v průběhu semestru). Byl zadán poslední úkol, celkem je tedy potřeba 110*2/3=73.333.. bodů.
Zápočtové příklady
Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů. Za úkoly odevzdané po termínu je možno získat jen poloviční počet bodů. Termínem je vždy datum a čas cvičení, mezi dnem stanovení termínu a termínem je vždy přinejmenším jedno cvičení (výjimky obou pravidel možná budou na konci semestru). U některých úloh nemusí být nastaven termín, zvláště pokud navazují na dosud neprobranou látku. Dokud nacházíte lepší řešení, můžete úlohy odevzdávat opakovaně, o již získané body tím nepřijdete.
| Kód | Body | 1. termín | Zadání |
|---|---|---|---|
| indukce | 10 | 15.3.2019 | Dokažte matematickou indukcí případy rekurence $t(n)\le cn^\alpha+\sum t(a_in)$ ($t(n)\le C$, pro $n\le n_0$) dle srovnání $\sum a_i^\alpha$ s $1$, užitečné je dokazovat vztah $t(n)\le c_1n^\alpha+c_2n^\beta$, kde $\sum a_i^\beta=1$, případně $t(n)\le c_1n^\alpha+c_2n^\alpha\log n$, vhodná $c_i$ zjistěte v průběhu důkazu. Hodí se za indukční předpoklad brát, že tvrzení platí pro všechna menší $n$. |
| řeka | 10 | 24.5.2019 | Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola, kde jedno je dosažitelné po proudu od druhého a jejichž vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví. |
| medián | 10 | 29.3.2019 | Je dán „komprimovaný“ seznam čísel. Nalezněte jejich medián. Komprimace spočívá v tom, že místo čísel dostáváme dvojice čísel, kde první udává hodnotu a druhé počet výskytů dané hodnoty v nekomprimované posloupnosti (stejná hodnota může být ve více dvojicích, dokonce ani není zakázáno její použití v ihned následující dvojici). Nemusíte popisovat jak se hledá medián v nekomprimovaném případě, ale můžete to využít jako podprogram. |
| rekur | 10 | 5.4.2019 | Zjednodušte popis funkce $t$ (stačí $\Theta(t)$) dané následující rekurencí: $t(n)=t(\lceil\sqrt n\rceil)+c$, pro $n\ge 3$ a kde $t(n)=n$ pro $1\le n\le 2$. |
| barvící pravidla | 10 | 12.4.2019 | Zdůvodněte, proč barvící algoritmus pro hledání minimální kostry nemůže žádnou hranu obarvit podruhé. |
| rekur2 | 10 | 7+19.4.2019 | Zjednodušte popis funkce $t$ (stačí $\Theta(t)$) dané následující rekurencí: $t(n)=2t(\lceil\sqrt n\rceil)+c$, pro $n\ge 3$ a kde $t(n)=n$ pro $1\le n\le 2$. |
| lrb | 10 | 7+26.4.2019 | Ukažte, jak je možno z libovolného binárního stromu vytvořit RB strom (zachovávající inorder pořadí) v lineárním čase a ukažte, že rychleji to nejde. |
| mult | 10 | 10.5.2019 | Ukažte, dva (podobné) algoritmy, jak je možno násobit $n$ ciferná čísla v čase $O(n^{\log_23})$. |
| perm2n | 5 | 17.5.2019 | Pro danou permutaci čísel od $1$ do $K$ nalezněte její „abecední“ pořadí mezi všemi takovými permutacemi (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| n2perm | 5 | 17.5.2019 | Nalezněte permutaci která je mezi permutacemi čísel od $1$ do $K$ na daném $n$ tém „abecedním“ pořadí (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| řeka2 | 10 | 24.5.2019 | Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola (mohou být na různých přítocích), jejichž (říční) vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví. |
| permBi | 10 | Algoritmicky popište zobrazení a k němu inverzní zobrazení, mezi čísly od 1 do K! a permutacemi čísel od 1 do K (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| A | 69 | indukce(10), medián(9), rekur(10), barvící pravidla(10), rekur2(10), mult(10/2), perm2n(3/2), n2perm(3/2), řeka(6), řeka2(6) |
| B | 86 | indukce(7), medián(8), řeka(10), rekur(10), barvící pravidla(10), rekur2(10), lrb(10), mult(5), perm2n(5), n2perm(5), řeka2(6) |
| C | 78 | řeka(10), medián(6), rekur(10), rekur2(10), barvící pravidla(10), lrb(10), mult(10), perm2n(3), řeka2(6), n2perm(3) |
| D | 78 | indukce(2), řeka(5), medián(9), rekur(10), barvící pravidla(10), lrb(10), rekur2(5), mult(10), perm2n(5), n2perm(5), řeka2(7) |
| E | 77 | indukce(6), medián(10), rekur(10), barvící pravidla(8/2), rekur2(10), lrb(10), mult(10), perm2n(4), n2perm(4), řeka(3), permBi(3), řeka2(3) |
| F | 9 | indukce(0), medián(6), rekur(0), rekur2(3), lrb(?) |
| G | 35 | řeka(1), medián(6), rekur(5), rekur2(10), barvící pravidla(7), lrb(?), n2perm(3), perm2n(3) |
| H | 77 | řeka(10), medián(9), rekur(10), rekur2(10), lrb(10), mult(10), n2perm(4), perm2n(4), permBi(10) |
| I | 63 | medián(6), rekur(10), barvící pravidla(10), rekur2(10), lrb(9), mult(3), n2perm(0), perm2n(0), řeka(8+2/2), řeka2(6) |
| J | 64 | medián(4), rekur(10), barvící pravidla(10), rekur2(10), lrb(10), mult(3), n2perm(3), perm2n(3), řeka(6), řeka2(5) |
| K | 5 | medián(5), rekur(0) |
| L | 74 | rekur(10), rekur2(10), barvící pravidla(10), lrb(10), n2perm(3), mult(10), řeka2(7), řeka(8), permBi(6) |
Odkazy na obdobné stránky
moje loňské cvičení, texty k cvičení Jana Hrice, cvičení Miloše Chromého, Michala Oplera, Jakuba Pekárka
Cvičení 1
Cvičení odcvičil Jiří Fink. Na cvičení byla počítána složitost několika úloh, pro mne překvapivě matematická úloha s mrakodrapem a vejci byla řešena jako programátorská úloha. Kromně toho byly řešeny úlohy na půlení intervalu, prefixové součty a jejich využití pro intervalové součty.
Cvičení 2
Cvičení bylo seznamovací, snažil jsem se studenty vyprovokovat k používání nestandardních postupů. V reakci na shrnutí předchozího cvičení, jsem krátce pověděl něco o zkratkách v zápisu $\varepsilon$, $\delta$ gymnastiky, a zmínil jsem kompaktnost zápisu $O$, $o$ notace pomocí limes superior. Pak, když už jsme hovořili o rozboru časové složitosti jsem navázal formulací poměrně obecné rekurence, která se při rozboru složitostí algoritmů často vyskytuje.
Napsal jsem řešenou rekurenci $t(n)\le cn^\alpha+\sum t(a_in)$ (s okrajovou podmínkou $t(n)\le C$, pro $n\le n_0$). Pak jsme si s rekurencí chvilku hráli. Zmínil jsem analogii s integrováním per partes v rozdělení výpočtu na hotové a rozpracované. V našem případě měla každá z těchto částí natolik homogenní strukturu, že nebylo potřeba psát příliš písmen a stačilo posčítat hotové. Jednotlivé řádky tvořili geometrickou posloupnost, takže při kvocientu $S=\sum a_i^\alpha<1$ byl součet konečný a dostali jsme $O(n^\alpha)$. V případě kvocientu $S=1$ jsme potřebovali odhadnout počet pater rekurence a vyšlo nám $O(n^\alpha \log n)$. V případě kvocientu $S>1$ jsem převedli úlohu na předchozí případ a hledali jsme $\beta$, pro nějž je $\sum a_i^\beta=1$. Pak je řešením $O(n^\beta)$. Vypozorované odhady je nejlépe dokázat matematickou indukcí (za body).
Zmínil jsem analogii s Diferenčními(i Diferenciálními) rovnicemi, kde řešení homogenní rovnice dostáváme lineární kombinací basických řešení. K těmto řešením se přičítá jedno řešení „nehomogenity“. Pokud se mezi těmito řešeními některé vyskytují vícekrát, přibývají alternativní formy. (U lineárních diferenčních rovnic vycházejí geometrické posloupnosti násobené polynomy. Nejvyšší exponent v polynomu je o jedna menší než násobnost řešení.) V této analogii jsme dostali $c_1n^\beta$, jako homogenní řešení a pravé straně odpovídalo $c_2n^\alpha$. Řešení bylo tedy ve tvaru lineární kombinace $n^\beta$ s $n^\alpha$, nás zajímá větší z nich. V případě, kdy je $\alpha=\beta$, dostáváme „dvojnásobný kořen“ a jako druhé řešení $c_2n^\alpha \log n$. Odbočku se vztahem matic a lineárních diferenčních rovnic umožňující efektivní počítání členů posloupnosti jsem přeskočil.
Jako příklady použití rekurence jsem vyjmenoval násobení matic, efektivní hledání konvexního obalu a hledání mediánu (je potřeba velice často například dvakrát pro ten konvexní obal).
Pro algoritmus hledání $k$-tého prvku pomocí pivota, kde za pivota bereme aproximaci mediánu vyšla rekurence uvedeného typu. Znalost řešení nám umožnila rozhodnout se správně pro způsob aproximace mediánu (medián mediánů pětic vítězí nad mediánem mediánů trojic).
Na algoritmus násebení matic bylo málo času, tak jsem alespoň naznačil vnější vrstvu Kirkpatrick-Seidel algoritmu na hledání konvexního obalu. Znalost odvození výsledku rekurence zde umožnila odhad $O(n\log h)$, kde $h$ je počet bodů tvořících konvexní obal. Jednalo se o binární rekurenci, kde každá vrstva přispívala stejně a příspěvky vrcholů ve vyšších vrstvách byly větší než ve vrstvách nižších. Strom s $h$ vrcholy přispívá nejvíc, je-li vyvážený, tedy $\log h$ patrový. To že podprogram nalezne horní most v lineárním čase vyplyne z rekurence $t(n)\le t(3n/4)+cn$. To ale již „zazvonil zvonec“.
Cvičení 3
Na cvičení jsme nejprve dokončili Kirkpatrick-Seidel algoritmus ukázkou prune and search vyhledávání horního mostu. Ukázali jsme, jak z dvojic bodů a jejich směrů vybrat mediánový, jak porovnat mediánový směr se směrem mostu. A jak z toho vyvodit, kterých n/4 bodů nemá vliv na řešení úlohy. Vše jsme v lineárním čase zvládli a tak nám rekurence $t(n)\le t(3n/4)+cn$ skutečně vyšla.
Pak jsme se zabývali prohledáváním grafů. Uvědomili jsme si nevýhody prohledávání do šířky (nelokalita, paměťová náročnost zvláště na implicitních grafech), uvědomili jsme si nevýhody prohledávání do hloubky (může bloudit daleko od hledaného cíle). Bavili jsme se o implementacích na implicitních (velkých) grafech a jako dobrý kompromis vycházelo postupné prohledávání. U velkých implicitních grafů pak nejlépe s heuristickým odhadem nutné dosud nezapočtené délky. Ten je možno použít k prořezávání neperspektivnívh větví prohledávání.
Pak jsme načrtli program na hledání topologického uspořádání, popsali si typy hran, vyskytujících se při prohledávání do hloubky neorintoného grafu.
Na konci hodiny jsme si ukázali jak najít nejdražší cestu v celými čísly ohodnoceném stromě.
Cvičení 4
Na začátku hodiny jsme se věnovali prohledávání do hloubky. Bez důkazu jsem popsal algoritmus hledání silně souvislých komponent. Pak jsme dospěli k tomu, jak detekovat komponenty hranové a vrcholové dvousouvislosti. (Uvědomili jsme si, že u vrcholové dvousouvislosti je potřeba odložit zpracování zpětných hran, až za test artikulace a případné zpracování hran komponenty). Potřebovali jsme k tomu evidovat $\hbox{low}$ hodnoty. Jako informaci s naprosto zanedbatelným náznakem jak, jsem upozornil na testování rovinnosti, případně vnořování grafu do roviny v lineárním čase pomocí dvou průchodů do hloubky (využívající $\hbox{low2}$ hodnoty).
V další části hodiny jsme se věnovali hledání nejlacinějších cest, tahů a sledů. Začali jsme v nezáporně ohodnoceném grafu, kde tyto pojmy splývají. Popsali jsme Dijstrův algoritmus a detekovali rozhraní datové struktury, které bychom pro něj potřebovali.
V poslední čtvrthodině jsme se věnovali popisu datové struktury s daným časovým (amortizovaným) rozborem. Stihli jsme probrat operace Insert, FindMin a DeleteMin, s tím, že implementační detaily především FindMin by si zasloužily víc pozornosti.
Cvičení 5
Na začátku cvičení jsem dopověděl, jak je možno realizovat FindMin efektivně, pak jsme probrali i Decrement. Dobře bylo, že jsme se na chvíli pozastavili nad tím, jaký je rozdíl ve složitosti v nejorším případě a v amortizované složitosti, kde nás zajímá celkový čas strávený vnějším algoritmem (poskytujeme takový popis, aby bylo možno celkový čas spočítat, a abychom jej zbytečně nenadhodnotili ... šetření času na budoucí využití je v tomto kontextu OK).
Pak jsme se věnovali algoritmům Bellman Ford a Floyd Warshal. Doplnili jsme „invarianty“, co algoritmy mají spočítáno na začátku a co na konci $i$-tého vnějšího cyklu. S těmito invarianty není těžké ověřit, že programy počítají to, co mají počítat.
V případě BellMan Ford byl invariant „na začátku $i+1$-ní (a na konci $i$-té) fáze jsou $d_x$ ceny existujícího sledu ze startovacího vrcholu do vrcholu $x$, ale nejvýš hodnota nejlacinějšího sledu ze sledů používajících nejvýš $i$ hran“. Složitost $O(mn)$. Efektivnější implementace v průměrném případě (nikoli worst case) by si počítala množinu vrcholů, kde došlo v $i$-té fázi ke změně $d_x$ a $i+1$-ní fáze by zpracovávala jen tyto vrcholy.
V případě Floyd Warshala pak „na začátku $i+1$-ní (a na konci $i$-té) fáze máme matici nejlacinějších sledů mezi souřadnicemi danou dvojicí vrcholů, používající jako vnitřní vrcholy sledů pouze vrcholy z prvních $i$“. Složitost $O(n^3)$. Pokud nás zajímá jen podmatice výsledku, můžeme řádky či sloupce, které ve výsledku nepotřebujeme odstranit z dalších fází výpočtu po zpracování příslušného vrcholu. (Je výhodné zracovávat tyto vrcholy dříve, ale asymptotickou složitost tím nevylepšíme).
Cvičení 6
Tématem cvičení bylo hledání minimální kostry. Začali jsme vyslovením nedeterministického barvícího algoritmu (řezy bez modrých hran umožňují obarvit najlacinější hranu modře, cykly bez červených hran nejdražší červeně, v příadě shody cen jsou preferovány neobarvené hrany). Nezabývali jsme se důkazem korektnosti algoritmu (Proč skončí? Nemůže obarvit nějakou hranu podruhé?).
Pak jsme se věnovali Kruskalovu algoritmu. Rozmysleli jsme si, jaké má požadavky na datovou strukturu a dostali jsme interface Disjoint Find Union. Verzi DFU s amortizovanou složitostí jednotlivých operací $\alpha(n)$ jsme probrali, jen poměrně náročný důkaz složitosti jsme vynechali. Každopádně představu o pomalosti funkce $\alpha$ související s rychlostí Ackermanovy funkce jsme si chvíli povídali.
Pro případ, kdy nemáme hrany setříděné a jejich třídění by bylo pomalé je vhodnější použít Jarníkův(= Primův či Dijkstrův) algoritmus. Můžeme ale zajít dál a použít algoritmus Fredman-Tarjan, který využívá toho, že jediná nekonstantní operace u Fibonacciho hald je Delete(Min).
Algoritmus pracuje ve fázích. Do $i$-té fáze vstupuje $n_{i-1}$ stromů (do první fáze jednovrcholové $n_0=n$). Každý strom je reprezentován jediným „stromovrcholem“. Stanoví se maximální velikost haldy $t_i$, pro níž je povoleno DeleteMin provádět tak, aby výpočet jedné „fáze“ vyšel $O(m)$. Vhodná volba je $t_i=2^{2m/n_{i-1}}$. Ve chvíli kdy již nemůže DeleteMin provést, označí stromovrcholy stromu novým číslem stromu a začne pěstovat další strom. Pokud FindMin vrátí stromovrchol jenž již má přiřazeno číslo stromu $s$, je aktuální strom ke stromu $s$ připojen (stromovrcholy dostanou toto číslo). Poslední variantou je, že se halda vyprázdní a našli jsme minimální kostru příslušné komponenty. V takovém případě strom nedostane číslo a dalších fází algoritmu se nezúčastní.
Na konci fáze jsou přihrádkovým tříděním seřazeny hrany podle čísel stromů mezi nimiž vedou v čase $O(m+n_i)$, kde $n_i$ je počet stromů očíslovných během $i$-té fáze. Pak jsou odstraněny „smyčky“ a z intervalu hran vedoucích mezi stejnou dvojicí stromů je vždy ponechána jen ta najlacinější (červené barvící pravidlo). Tím vznikne vstup pro další fázi. Během fáze $n_i$ krát překročila velikost haldy $t_i$. Za tato překročení zodpovídá $n_i\cdot t_i$ různých orientovaných hran. Odtud $n_i\cdot t_i\le 2m$. Odtud $t_i\le 2m/n_i$ a $t_{i+1}=2^{2m/n_i}\ge 2^{t_i}$. Nejpozději ve chvíli, kdy $n_{i-1}\le t_i$ je $i$-tá fáze poslední. Vzhledem k tomu, že $n_{i-1}\le n$, jakmile $2^{2^{2^{\dots}}}\ge n$ pro $i$-patrový zápis, musí algoritmus nejpozději v $i$-té fázi skončit. Počet fází je tedy nejvýš $\log^*(n)$ a celková složitost algoritmu $O(m\log^*(n))$.
Cvičení 7
Vzhledem k tomu, že na přednášce je stále ještě probírána minimální kostra, mohli jsme se vrátit k řešení úloh ne příliš souvisejících s přednáškou. Vrátili jsme se k úloze s vajíčky a mrakodrapy a ukázali, jak ji správnou matematizací vyřešit na papíře, místo abychom psali pomalý algoritmus. (Vyšlo nám, že počet vyřešitelných pater na $h$ pokusů s $k$ vajíčky je $\sum_{i=0}^{\min(k,h)}{h\choose i}$.)
Pak jsme řešili hledání čtverce barvy 0 v obrázku.
Skončili jsme hledáním $n$ tého v pořadí součtu tvaru $a_i+b_j$ z hodnot daných v polích $a$, $b$ délky $n$. Předpokládáme, že pole $a$ i $b$ jsou seřazeny vzestupně. Postupně jsme přes algoritmy se složitostí $O(n^2)$, $O(n\log n)$ dostali k řešení podúlohy, jak rychle jsme schopni otestovat zda daný parametr S je menší, větší či rovný pořadovanému součtu. Tu jsme nejprve vyřešili v čase $O(n\log n)$, pak jsme „přeskočili“ složitost $O(n)$ a dostali se rovnou na složitost $O(\sqrt{n}\log n)$. Tento podproblém (a reprezentaci dat) jsme pak použili při hledání $k$-tého součtu pomocí pivota. Pivota jsme volili jako vážený medián (komprimovaný medián) mediánů $O(\sqrt n)$ intervalů. Plocha zbývajících prvků po každé aplikaci pivota klesne o čtvrtinu, dostaneme tak rekurenci $t(s)\le t(3s/4)+c\sqrt{n}\log n$, kde $s$ začíná na $n\log n$. Hloubka rekurence nepřekročí $\log s$ a dostáváme tak složitost $O(\sqrt{n}\log^2 n)$, což znamená, že algoritmus si ani nestihne přečíst všechna čísla vstupních polí $a$, $b$.
Cvičení 8
Na přednášce byly probírány binární vyhledávací stromy a tak jsme jim věnovali i cvičení. Začali jsme na tržnici, kde jsme se snažili vynachválit na co jsou vyhledávací stromy vhodné. Kromě základních množinových operací excelují vyhledávací stromy v odpovědích na intervalové dotazy či průniky takových dotazů.
Pak jsme se věnovali binárním stromům obecně a později i technikám omezení hloubky stromu. Povídali jsme si o AVL a RB stromech (pozor na definice pomocí nestandardně definovaných pojmů). Srovnali jsme jejich maximální možnou hloubku, srovnali jsme je i s ohledem na velikost změny v datové struktuře při aktualizaci.
Na konci hodiny jsme se věnovali řešení konfliktů RB stromů. Stihli jsme insert, ale Delete jsme teprve začali.
Cvičení 9
V první části hodiny jsme se věnovali Strassenově algoritmu. Redukující násobení matic na 7 násobení matic polovičních rozměrů, vedoucí tak k rekurenci $t(n)=7t(n/2)+cn^2$, tedy $t(n)\in O(n^{\log_27})$, kde $n$ je rozměr matice. (Cvičení na vhodnou symboliku, díky níž je možno důkaz provést bez dlouhého psaní. Ukázali jsme si jinou variantu než originální Strassen, volili jsme koeficienty tak, aby daná podmatice mohla být použita vždy jen se dvěma možnými koeficienty, kde jeden je nulový a druhý má absolutní hodnotu 1. Díky tomu nám stačilo jen sledovat, která místa „tenzorového součinu“ mají nenulový koeficient. (Podle toho, kde není použita nula vybíráme součinem podmatici stejné matice. Při aditivní kombinaci součinů tak pouze sledujeme, kolikrát je použita která pozice.) Vždy když se nám podařilo nakombinovat součiny tak, aby jediné dvě nenulové hodnoty byly na správných místech, podívali jsme se zda vznikly v kobinaci se stejným znaménkem (a vždy byly s různým). To nám dává omezení na to, jaká znaménka koeficientů jsou přípustná. Ukazuje se, že tyto $4$ podmínky jsou na sobě závislé a splnění prvních $3$ vynucuje splnění čtvrté, takže máme 2^8/2^3=2^5 možností jak v daném schématu zvolit znaménka.)
Ve zbytku hodiny jsme se věnovali vyvažování RB stromů a AVL stromů. Zbývá nám dokončit delete v AVL stromech.
Cvičení 10
Na cvičení jsme si nejprve volně povídali o třídících algoritmech. (Málokdy třídíme kvůli tomu, abychom vypsali setříděný výstup, spíš budujeme uspořádanou množinu pro další opakované používání. Málokdy je vstupem zcela náhodná permutace, častěji se vstup skládá z několika úseků již setříděných posloupností, proto je zajímavé měřit složitost se zohledněním pravděpodobností jednotlivých vstupů. Pokud musíme třídit na místě, přidávají se komplikace s organizováním přemísťování.) Pak jsme se věnovali dolním odhadům pomocí rozhodovacích stromů. Ukázal jsem, že je možno danou techniku použít i na případ zjištní na základě porovnávání, zda v dané $n$-prvkové množině čísel je nějaké číslo víckrát. Zároveň jsem ukázal, že existuje algoritmus nezaložený na porovnávání, který funguje v randomizovaném čase $O(n)$.
Pak jsme se věnovali problémům nejmenší prázdný podinterval, nejmenší vzdálenost mezi čísly či body v rovině.
Cvičení 11
Na cvičení jsme si nejprve povídali o hashování (faktor naplnění, kaňkování, randomizace, univerzálnost, dynamické měnění velikosti amortizovaně/worst case). (Datová struktura, kde se kombinuje více rozměrů měření složitosti dohromady ... v průměrném případě či randomizovaně, kombinováno s amortizací).
Následně jsme řešili vyhodnocování shody podle pravidel hry logik/master-mind.
Pak jsme se věnovali povídání o domácích úkolech (stihli jsme probrat jen ten první).
Cvičení 12
Na cvičení jsme se věnovali povídání o ostatních domácích úkolech jimž vypršela lhůta na odevzdání za plný počet bodů (stihli jsme probrat všechny).
Cvičení 13
Na cvičení jsme se věnovali povídání o ostatních domácích úkolech jimž vypršela lhůta na odevzdání za plný počet bodů (stihli jsme probrat oba).