[home]

ADS I (2021/2022)

Cvičení k přednášce Algoritmy a datové struktury I

Doporučená literatura

• Průvodce labyrintem algoritmů
• Pro zájemce o složitější grafové algoritmy - Krajinou grafových algoritmů

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna $\frac{10}{3}$ body (více aktivity na jednom cvičení je stále $\frac{10}{3}$ bodů).

Body

Body budou zapsané v SISu.

Probrané příklady

14.2.

• Organizační info.
• Úsek s největším součtem, nejkratší text s výskytem všech písmen, nejdelší text bez opakování písmen.
• Dvojice se zadaným součtem.

21.2.

• Zopakovali jsme asymptotickou notaci pro třídy $O, \Omega, \Theta, o, \omega$. Dokázali jsme některá jednoduchá tvrzení a porovnali některé funkce.

28.2.

• Začali jsme s BFS. Časová složitost BFS při použití matice sousednosti. Zamysleli jsme se nad tím, kolik různých nejkratších cest může existovat.
• Vysvětlili jsme si prohledávání stavového prostoru oproti procházce po grafu.

7.3.

• DFS, odkrokování, klasifikace hran v (ne)orientovaných grafech.
• Hledání artikulací pomocí low(v).

14.3.

• Topologické uspořádání a DAG. Příklady na topologickou indukci.
• Začali jsme s Dijkstrovým algoritmem. Distukovali jsme zda nám vadí záporné hrany a cykly.

21.3.

• Zakončení nejkratších cest. Obecný relaxační algoritmus se zastaví. Bellman-Ford a jeho varianty.
• Floyd-Warshall - odkrokování, detekce záporných cyklů.

28.3.

• Minimální kostry, Jarník, Borůvka, Kruskal včetně union-find struktury. Odkrokování, jak se vypořádat s neunikátními hranami.
• Mosty leží ve všech kostrách. Jak rychle najít min. kostru při změně váhy jedné z hran.

4.4.

• BVS - vypsání in-order, postavení dokonale vyváženého BVS ze setříděného pole, operace Split a Join
• AVL - rotace

11.4.

• Odpadá

25.4.

• (a,b)-stromy, odkrokování vkládání, operace join, náznak operace split (doladění detailů je za úkol).
• Příprava na hešování - vytvoření generátoru náhodných čísel pomocí ideální mince.

2.5.

• Hešování - odkrokování řetízkového hešování a hešování s otevřenou adresací.
• Začátek algoritmů rozděl a panuj. Připomenutí master theorem a jaké typy rekurentních rovnic umí vyřešit.

9.5.

• Dokončili jsme algoritmy "rozděl a panuj". K-tý nejmenší prvek v lineárním čase, medián ze 2 setříděných posloupností, rozmotání spletitého kabelu.
• Pokud chcete na poslední hodině vidět řešení některého z úkolů zadaných během semestru, napište mi mailem zadání.

16.5.

• Dynamické programování - neejdelší rostoucí podposloupnost.
• Opakování příkladů z minula - a,b-tree split, roboti v bludišti

Úkoly

Na řešení úkolů jsou vždy dva týdny. Úkoly je možné odevzdávat mailem (preferovaná varianta) nebo na papíru na cvičení. Každý úkol musí obsahovat zdůvodnění, proč je řešení korektní (např. samotný pseudokód nestačí). Pokud je úkolem navrhnout algoritmus, pak je také vždy zapotřebí uvést časovou a prostorovou složitost, včetně zdůvodnění.

14.2. (do 28.2.)

• Součet úseku: Je dána posloupnost $x_1, \dots , x_n$ kladných čísel a číslo $s$. Hledáme $i$ a $j$ taková, že $x_i + \dots + x_j = s$. Navrhněte algoritmus pracující v čase $\mathcal{O}(n)$.
• Lokální minimum: Je dána posloupnost $+\inf = x_0, x_1, \dots , x_n, x_{n+1} = +\inf$. O prvku $x_i$ řekneme, že je lokálním minimem, pokud $x_{i−1} \geq x_i \leq x_{i+1}$. Navrhněte algoritmus, který nějaké lokální minimum najde v lepším čase než $\mathcal{O}(n)$.
• Úsek posloupnosti je $k$-hladký (pro $k \geq 0$), pokud se každé dva jeho prvky liší nejvýše o $k$. Popište algoritmus pro hledání nejdelšího $k$-hladkého úseku v čase lepším než $\mathcal{O}(n^2)$.

21.2. (do 7.3.)

• Najděte co nejlepší asymptotický odhad funkce $log_n(n!)$
• Dokažte alespoň 2 z následujících tvrzení.
  • $f(n) \in O(g(n)) \iff g(n) \in \Omega(f(n))$
  • $f(n) \in O(g(n)) \wedge h(n) \in O(i(n)) \implies f(n) + h(n) \in O(g(n) + i(n))$
  • $f(n) \in O(g(n)) \wedge h(n) \in O(i(n)) \implies max(f(n), h(n)) \in O(max(g(n), i(n)))$
  • $n \log(n) \not\in O(n)$
  • $\log(n) \in O(n^\epsilon), \forall \epsilon > 0$

28.2. (do 14.3.)

• Upravte BFS algoritmus, aby hledal nejenom nejkratší cestu, ale i kolik nejkratších cest do vrcholu vede. Zachovejte časovou složitost.
• Koupili jste na inzerát dvojici skvělých robotů. Lacino, neboť jsou právě uvěznění v bludišti (čtvercová síť s některými políčky blokovanými). Znáte jejich polohy a můžete jim rádiem vysílat povely pro posun o políčko na sever, jih, východ či západ, abyste je dostali na okraj bludiště. Háček je ale v tom, že na každý povel reagují oba roboti. Vymyslete algoritmus, který najde nejkratší posloupnost povelů, jež vysvobodí oba roboty. Dodejme ještě, že robot ignoruje povel, který by způsobil okamžitý náraz do zdi nebo do druhého robota, a že jakmile se robot dostane na okraj, odchytíme ho a další povely neposlouchá.

  Pokud se vám zdá zadání příliš jednoduché, zkuste vyřešit variantu, kdy počáteční polohy robotů neznáte. To je ovšem mnohem obtížnější a potřebná „univerzální posloupnost povelů“ mnohem delší.

• Hrdina Théseus se vypravil do hlubin labyrintu a snaží se najít poklad. Chodbami labyrintu se ovšem pohybuje hladový Mínótauros a snaží se najít Thésea. Labyrint má tvar čtvercové sítě, jejíž každé políčko je buďto volné prostranství, anebo zeď. Známe mapu labyrintu a počáteční polohy Thésea, Mínótaura a pokladu. Théseus se v jednom tahu pohne na vybrané sousední políčko. Poté se vždy dvakrát pohne o políčko Mínótauros: pokaždé se pokusí zmenšit o 1 rozdíl své a Théseovy x-ové souřadnice, pokud to nejde, pak y-ové, pokud nejde ani to, stojí. Poraďte Théseovi, jak má dojít k pokladu a vyhnout se Mínótaurovi.

7.3. (do 21.3.)

• Vyvážená orientace: Hranám grafu chceme přiřadit orientace tak, aby z každého vrcholu vycházelo stejně hran, jako do něj vchází. Navrhněte algoritmus, který takovou orientaci nalezne, a ukažte, že to lze, kdykoliv všechny vrcholy mají sudé stupně.
• Asfaltování: Máme mapu městečka v podobě neorientovaného grafu. Parta asfaltérů umí za jednu směnu vyasfaltovat dvě na sebe navazující ulice (hrany). Mezi směnami mohou asfaltéři libovolně přejet do jiné části města. Jak vyasfaltovat každou ulici právě jednou? Jde to pokaždé, když je ulic sudý počet?
• Strážníci: Mapa městečka má tvar stromu. Na křižovatky chceme rozmístit co nejméně strážníků tak, aby každá ulice byla z alespoň jedné strany hlídaná.

14.3. (do 28.3.)

• Na mapě města jsme přiřadili každé silnici čas na průjezd a každé křižovatce průměrnou dobu čekání na semaforech. Jak hledat nejrychlejší cestu?
• Mějme mapu města ve tvaru orientovaného grafu. Každou hranu ohodnotíme podle toho, jaký nejvyšší kamion po dané ulici může projet. Po cestě tedy projede maximálně tak vysoký náklad, kolik je minimum z ohodnocení jejích hran. Jak pro zadané dva vrcholy najít cestu, po níž projede co nejvyšší náklad?

21.3. (do 4.4.)

• Kritická hrana budiž taková, která leží na všech nejkratších cestách. Tedy ta, jejíž prodloužení by ovlivnilo vzdálenost. Navrhněte algoritmus, který najde všechny kritické hrany.
• 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.
• Vymyslete algoritmus, který nalezne všechny hrany, jež leží na alespoň jedné nejkratší cestě.

28.3. (do 11.4.)

• Naimplementujte jeden z algoritmů pro hledání minimální kostry - Jarník, Borůvka, Kruskal. Snažte se držet časové složitosti ze skript. Můžete použít libovolný programovací jazyk.

4.4. (do 18.4.)

• Úsporné stromy: Obvyklá reprezentace BVS v paměti potřebuje v každém vrcholu 3 ukazatele: na levého syna, na pravého syna a na otce. Ukažte, jak si vystačit se dvěma ukazateli. Původní 3 ukazatele by z těch vašich mělo jít spočítat v konstantním čase.
• Dokažte, že u dokonale vyváženého BVS mohou chybět prvky pouze na nejnižší hladině.
• Upravte AVL stromy tak, aby dokázaly pro libovolné $k$ najít $k$-tý nejmenší prvek. Pokud doplníte nějaké další informace do vrcholů stromu, nezapomeňte, že je musíte udržovat i při vyvažování.

25.4. (do 9.5.)

• Navrhněte operaci Split($T$, $x$), která zadaný (a, b)-strom $T$ rozdělí na dva (a, b)-stromy. V jednom budou klíče menší než $x$, v druhém ty větší. Pokuste se o logaritmickou časovou složitost.
• Nevýhodou (a, b)-stromů je, že plýtvají pamětí – může se stát, že vrcholy jsou zaplněné jen z poloviny. Navrhněte úpravu, která zaručí zaplnění z alespoň 2/3.

2.5. (do 16.5.)

• Mějme množinu ne nutně seřazených přirozených čísel a číslo $x$. Chceme zjistit, zda množina obsahuje dvojici prvků se součtem $x$. Pokuste se o lineární časovou složitost.
• Pro každý ze třech typů chování Master Theorem nalezněte nějaký algoritmus, který mu odpovídá. Pokud vás nenapadne užitečný algoritmus, který už znáte, můžete vymyslet i nějaký neužitečný algoritmus.
• Řešte rekurenci $T(n) = 2T(n/2) + \Theta(n log n)$, $T(1) = 1$.

9.5. (do 23.5.)

• Inverze v posloupnosti $x_1, \dots , 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í v čase $O(\log n)$
• Šroubky a matičky: Na stole leží $n$ různých šroubků a $n$ matiček. Každá matička pasuje na právě jeden šroub a my chceme zjistit, která na který. Umíme ale pouze porovnávat šroub s matičkou – tím získáme jeden ze tří možných výsledků: matička je příliš velká, příliš malá, nebo správně velká. Nalezněte co nejefektivnější algoritmus.
• Proč ve funkci LinearSelect na hledání $k$-tého nejmenšího prvku používáme zrovna pětice? Fungoval by algoritmus s trojicemi? Nebo se sedmicemi? Byl by pak stále lineární?

16.5. (do září)

• Kopcem nazveme podposloupnost, která nejprve roste a pak klesá. Vymyslete algoritmus, který v zadané posloupnosti nalezne nejdelší kopec.
• Mějme posloupnost $n$ knih. Každá kniha má nějakou šířku $s_i$ a výšku $v_i$. Knihy chceme naskládat do knihovny s nějakým počtem polic tak, abychom dodrželi abecední pořadí. Prvních několik knih tedy půjde na první polici, další část na druhou polici, a tak dále. Máme zadanou šířku knihovny $S$ a chceme rozmístit police tak, aby se do nich vešly všechny knihy a celkově byla knihovna co nejnižší. Tloušťku polic a horní a spodní desky přitom zanedbáváme.
• Dokažte, že editační vzdálenost dvou řetězců $L(x, y)$ se chová jako metrika: je vždy nezáporná, nulová pouze pro $x = y$, symetrická ($L(x, y) = L(y, x)$) a splňuje trojúhelníkovou nerovnost $L(x, z) \leq L(x, y) + L(y, z)$.