Michal Opler

A PhD student of Discrete Models and Algorithms

© 2022. Hyde theme.

Algoritmy a datové struktury I

Cvičení k přednášce Algoritmy a datové struktury I [NTIN060] v letním semestru 2018/2019. Probíhá v pátek od 9:00 v T5.

Požadavky na zápočet

Tabulka výsledků

Co jsme dělali

22. 2. 2019
Rychlé zavedení RAMu, časové a paměťové složitosti. Jak asymptoticky porovnávat funkce a různá zákoutí óčkové notace. Pár konkrétních úloh. [Příklady 1-6]
1. 3. 2019
BubbleSort na RAMu, a různé aplikace binárního vyhledávání. [Příklady 1-5]
8. 3. 2019
Grafy a způsoby jejich reprezentace. Algoritmy BFS, DFS a z nich vycházející klasifikace hran. Použití prohledávacích algoritmů na příkladech. [Příklady 1-5]
15. 3. 2019
Hledání mostů a artikulací pomocí DFS. Jak najít topologické uspořádaní DAGu a k čemu všemu se dá použít. [Příklady 1-4]
22. 3. 2019
Odvození algoritmu pro rozklad na SSK. Kdy umíme zorientovat graf tak aby byl silně souvislý. Dijkstrův algoritmus a proč ho nechceme používat na grafech obsahujících záporné hrany. [Příklady 1-3]
29. 3. 2019
Djikstra, cesty minimalizující rozmanité parametry a přihrádková implementace. Obecný relaxační algoritmus, Bellman-Fordův algoritmus a Floyd-Warshallův algoritmus. Jak najít záporný cyklus. [Příklady 1-3, 6-7]
5. 4. 2019
Cvičil Miloš Chromý. Pár dalších aplikací nejkratších cest. Jarníkův a Borůvkův algoritmus na hledání nejmenší kostry. Aktualizace kostry po změně váhy hrany.
12. 4. 2019
Kontrahující verze Borůvkova algoritmu a její využití na rovinných grafech. Úvod do binárních vyhledávacích stromů. [Příklady 1-5]
26. 4. 2019
AVL a (a,b)-stromy. Jak rozšířit vyhledávací stromy o další operace a použití vyhledávacích stromů pro hledání nejdelší rostoucí podposloupnosti. [Příklady 1-4]
3. 5. 2019
Princip Rozděl a Panuj, na příkladu Mergesortu jsme odvodili Kuchařkovou větu (Master theorem). Řešení podobných rekurencí a pár dalších algoritmických příkladů (Karacubův algoritmus násobení, binární vyhledávání, Strassenův algoritmus). [Příklady 1-2]
10. 5. 2019
Pokračování v rekurzivních algoritmech. Quickselect a Linearselect. Dvojice nejbližších bodů na přímce a v rovině. [Příklady 1-3]
17. 5. 2019
Opakování třídících algoritmů, třídění polynomiálně velkých čísel. Hešování, hešování s otevřenou adresací, lineární přidávání. [Příklady 1-2, 5-6]
24. 5. 2019
Amortizace pomocí přímého upočítání, penízkové metody i potenciálové metody na příkladech nafukovacího pole a skoro vyvážených stromů. Na závěr pak jeden bonusový problém.

Domácí úkoly

Úkoly odevzdávejte buď osobně před začátkem cvičení nebo pomocí emailu. Pokud je to alespoň trochu možné, neodevzdávejte prosím přes mail naskenované ruční řešení (ideálně sázejte v $\LaTeX \text{u}$).

1. $\Theta + \Theta$ (do 1.3.) 5b.
Mějmě funkce $f$, $g$ a $h$ takové že $f(n) \in \Theta(h(n))$ a $g(n) \in \Theta(h(n))$. Dokažte, že $f(n) + g(n) \in \Theta(h(n))$.
2. Odmocnina (do 8.3.) 5b.
Navrhněte algoritmus na spočítání celočíselné odmocniny z čísla $x$. To je největší $y$ takové, že $y^2 \le x$.
3. Uvěznění roboti (do 15.3.) 5b.
Na vstupu dostanete dvě bludiště, což jsou čtvercové sítě rozměru $r \times s$ se seznamem zdí, kde zdí myslíme hranu mezi dvěma políčky. V každém z bludišť se nachází jeden robot (polohu dostaneme také na vstupu) a oba reagují na ovladač, kterým jim můžeme posílat povely pro posun o políčko na sever, jih, východ či západ. Na každý povel reagují oba roboti, robot ignoruje příkaz pouze pokud se ve směru jeho pohybu nachází zeď. Vymyslete algoritmus, který najde nejkratší posloupnost povelů, jež vysvobodí oba roboty. Ve chvíli kdy robot opustí bludiště, už ho zastavíme a povely dále ignoruje. Časovou a paměťovou složitost vztahujte k rozměrům bludišť, tj. $r$ a $s$.
4. $d$-degenerované grafy (do 22.3.) 5b.
O grafu řekneme, že je $d$-degenerovaný, pokud existuje pořadí odtrhávání vrcholů takové, že každý odtrhávaný vrchol má aktuální stupeň maximálně $d$. Například stromy jsou 1-degenerované (trháme od listů) a rovinné grafy jsou 5-degenerované. Pro zadaný neorientovaný graf najděte nejmenší $d$ takové, že $G$ je $d$-degenerovaný. Jde vyřešit v lineárním čase.
5. Šetříme na mýtu (do 29.3.) 5b.
Silnice v mapě máme ohodnocené dvěma nezápornými čísly: délkou a mýtem (poplatkem za projetí). Jak najít nejlevnější z nejkratších cest?
6. Poctivá směnárna (do 12.4.) 5b.
Směnárna obchoduje s $n$ měnami (měna číslo 1 je koruna) a vyhlašuje matici kurzů $K$. Kurz $K_{ij}$ říká, kolik za jednu jednotku $i$-té měny dostaneme jednotek $j$-té měny. Vymyslete algoritmus, který zjistí, zda existuje posloupnost směn, která začne s jednou korunou a skončí s více korunami.
7. Vrcholy v intervalu (do 26.4.) 5b.
Ukažte jak upravit vyhledávácí strom, aby navíc uměl efektivně provádět operaci Rank($x$,$y$), která odpoví, kolik vrcholů stromu leží v intervalu $[x, y]$. Složitost všech operací včetně této by měla být $O(\mbox{hloubka})$.
8. Podobný úsek (do 3.5.) 5b.
V posloupnosti čísel na vstupu najděte nejdelší souvislý úsek, ve kterém je rozdíl libovolných dvou prvků nejvýše $k$.
9. Inverze v posloupnosti (do 10.5.) 5b.
Inverze v posloupnosti $x_1,\ldots,x_n$ říkáme každé dvojici $(i,j)$ takové, že $i<j$ a současně $x_i > x_j$. Vymyslete algoritmus, který spočítá, kolik daná posloupnost obsahuje inverzí. Cílem je rekurzivní algoritmus pracující v čase $O(n \log n)$.
10. Hledání prvku (do 17.5.) 5b.
Dokažte že deterministický algoritmus v porovnávacím modelu, který nalezne zadaný prvek v $n$-prvkové uspořádané posloupnosti, použije v nejhorším případě $\Omega(\log n)$ porovnání.
11. Hešování s počítadly (do 24.5.) 5b.
Uvažujte hešování s lineárním přidáváním ($f(x) = (h(x) + i) \mod m$). Každá přihrádka $j$ má navíc počítadlo $c_j$, které určuje počet prvků v tabulce, pro které platí $h(x) = j$. Jak toto počítadlo využít a aktualizovat při implementaci jednotlivých operací?

Bonusové domácí úkoly

1. Neviditelní roboti (do 29.3.) 5b.
Stejný problém jako 3. domácí úloha (Uvěznění roboti), s tím rozdílem že neznáme počáteční polohu robotů. Chceme nalézt posloupnost pohybů, která vysvobodí oba roboty ať už se na začátku nacházeli kdekoliv. Tentokrát postačí nalézt libovolnou takovou posloupnost, ne nutně nejkratší.
2. Inverze matice (do 24.5.) 5b.
Navrhněte algoritmus typu Rozděl a panuj na výpočet inverze trojúhelníkové matice $n\times n$ v čase lepším než $\Omega (n^3)$. Můžete předpokládat, že $n$ je mocnina dvojky.
3. Okénkové minimum konstantně (do 28.6.) 5b.
Vymyslete jak spočítat okénkové minimum (viz. příklad 2) v čase konstantním v nejhorším případě na posun okénka.

Užitečné odkazy