ADS I (2019/2020)

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 80 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 5 body (více aktivity na jednom cvičení je stále 5 bodů).

Vzhledem k současné situaci jsou cvičení prováděna online přes Zoom.

Body

Body budou zapsané v SISu.

Probrané příklady

21.2.
28.2.
6.3.
13.3.
20.3.
27.3.
3.4.
17.4.
24.4.
8.5.
15.5.
22.5.
29.05.

Ú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í.

21.2. (do 6.3.)

Najděte co nejlepší asymptotický odhad funkce $log_n(n!)$
Dokažte, že $log (n) \in O(n^\epsilon)$ pro každé $\epsilon > 0$
Máte zadanou posloupnost čísel (ne nutně seřazenou) a číslo $k$. Nalezněte dvojice čísel z posloupnosti, které se sečtou na $k$. Vyřešte v čase lepším než $O(n^2)$

28.2. (do 13.3.)

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, a že jakmile se robot dostane na okraj, odchytíme ho a další povely neposlouchá.
Mějme mapu Manhattanu: čtverečkovaný papír, křížení čar odpovídají křižovatkám, úsečky mezi nimi jednotlivým streets a avenues, z nichž některé jsou neprůjezdné kvůli dopravní zácpě. Zrovna se nám v jedné ulici porouchalo auto a nyní dovede pouze jezdit rovně a odbočovat doprava. Nalezněte nejkratší cestu do servisu (na zadanou křižovatku).
Upravte BFS tak, aby pro každý dosažitelný vrchol zjistilo, kolik do něj vede nejkratších cest z počátečního vrcholu. Zachovejte lineární časovou složitost.

6.3. (do 20.3.)

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. Jak vyasfaltovat každou ulici právě jednou? Jde to pokaždé, když je ulic sudý počet? Řešte v O(n+m).
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á. Řešte v O(n+m).
Trojúhelníky: Spočítejte v rovinném grafu trojúhelníky, tedy trojice vrcholů spojené každý s každým. Řešte v O(n+m).
Mafiáni: Mapa městečka ve tvaru stromu, v některých vrcholech bydlí mafiáni. Chceme do vrcholů rozestavět co nejméně strážníků tak, aby se mafiáni nemohli nepozorovaně domlouvat, tedy aby mezi každými dvěma mafiány stál aspoň jeden strážník. Postavíme-li strážníka do vrcholu s mafiánem, zabráníme mu v kontaktu se všemi ostatními mafiány. Řešte v O(n+m).

13.3. (do 27.3.)

Nechť délky hran leží v množině ${0, \dots , L}$. Navrhněte datovou strukturu založenou na přihrádkách, s níž Dijkstrův algoritmus poběží v čase $O(nL + m)$. Pokuste se vystačit s pamětí $O(n + m + L)$.
Upravte Bellmanův-Fordův algoritmus, aby uměl detekovat záporný cyklus dosažitelný z vrcholu $v_0$. Uměli byste tento cyklus vypsat?
Dokažte, že v grafu bez záporných cyklů se obecný relaxační algoritmus zastaví, ať už vrchol k uzavření vybíráme libovolně.
Jak z výsledku Floydova-Warshallova algoritmu zjistíme, kudy nejkratší cesta mezi nějakými dvěma vrcholy vede?
Lze se v algoritmech na hledání nejkratší cesty zbavit záporných hran tím, že ke všem ohodnocením hran přičteme nějaké velké číslo $k$?
Vymyslete algoritmus, který nalezne všechny hrany, jež leží na alespoň jedné nejkratší cestě.
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.

20.3. (do 3.4.)

Nalezněte 2. nejmenší kostru. Kromě postupu jak takovou kostru nalézt je potřeba i dokázat, že tento postup funguje.
Implementujte libovolný ze tří algoritmů na hledání minimální kostry. Jejich detailní popis najdete ve skriptech. Jazyk můžete použít libovolný rozumný a čitelný (C/C++, C#, Java, Pascal, Python, ...). Snažte se dosáhnout co nejlepší časové složitosti. Datové struktury můžete použít z knihoven.

27.3. (do 10.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.
Na cvičení jsme dokázali dokonale vyvážit BVS v lineárním čase tím, že jsme ho vypsali do pole (seřazeného) a toto pole jsme přetvořili na dokonale vyvážený BVS. Vyřešte toto cvičení tak, aby vám kromě zadaného stromu stačilo logaritmické množství paměti.
Ve skriptech je ukázáno, že dokonale vyvážený strom o $2^k−1$ vrcholech je úplný – všech $k$ hladin obsahuje nejvyšší možný počet vrcholů. Dokažte, že ostatní dokonale vyvážené stromy mají podobnou strukturu, jen na poslední hladině mohou některé vrcholy chybět

3.4. (do 17.4.)

Navrhněte operaci Join($X,Y$), která dostane dva ($a,b$)-stromy $X$ a $Y$ a sloučí je do jednoho. Může se přitom spolehnout na to, že všechny klíče z $X$ jsou menší než všechny z $Y$ . Zkuste dosáhnout složitosti $O(log |X| + log |Y|)$.
Navrhněte operaci Split($T,x$), která zadaný ($a,b$)-strom $T$ rozdělí na dva stromy. V jednom budou klíče menší než $x$, v druhém ty větší. Pokuste se o logaritmickou časovou složitost.
Dokažte, že budeme-li reprezentovat množiny binárními vyhledávacími stromy, nelze sjednocení provést rychleji než lineárně v nejhorším případě. Platí to dokonce i tehdy, máme-li na vstupu zaručený dokonale vyvážený strom a výstup může být jakkoliv nevyvážený.
Okénkový medián: Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních k čísel. Dosáhněte časové složitosti $O(log\:k)$ na operaci. Jako bonusovou variantu (bez odměny navíc) zkuste dokázat, že čas $\Theta(log\:k)$ je nejlepší možný, pokud umíme čísla pouze porovnávat.

17.4. (do 1.5.)

Okénková minima: Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište minimum z posledních $k$ čísel. Na rozdíl od cvičení na okénkový medián (zadáno jako úkol 3.4.) existuje i řešení pracující v amortizovaně konstantním čase na operaci.
Použijte penízkovou metodu k analýze "nafukovacího pole".
Minimový strom pro posloupnost $x_1, \dots , x_n$ navzájem různých prvků je definován takto: v kořeni leží prvek $x_j$ s nejmenší hodnotou, levý podstrom je minimovým stromem pro $x_1, \dots , x_{j-1}$, pravý podstrom pro $x_{j+1}, \dots , x_n$. Navrhněte algoritmus, který sestrojí minimový strom v čase $O(n)$.

24.4. (do 8.5.)

Šroubky a matičky: Na stole leží $n$ různých šroubků a $n$ matiček. Každá matičky 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.
Inverze matice: 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)$. Jako podprogram se může hodit Strassenovo násobení matic. Můžete předpokládat, že $n$ je mocnina dvojky.
Řešte "nekuchařkovou" rekurenci $T(n) = n^{1/2} T(n^{1/2}) + \Theta(n), T(1) = 1$.

15.5. (do 29.5.)

Upravte funkci LinearSelect tak, aby si vystačila s konstantně velkou pomocnou pamětí. Prvky ve vstupním poli můžete libovolně přeskupovat.
Jak bude vypadat strom rekurzivních volání funkce LinearSelect? Kolik bude mít listů? Jak dlouhá bude nejkratší a nejdelší větev?
Kopcem nazveme podposloupnost, která nejprve roste a pak klesá. Vymyslete algoritmus, který v zadané posloupnosti nalezne nejdelší kopec. Pokuste se o řešení v lepším čase než $O(n^3)$. Může se vám hodit algoritmus pro hledání nejdelší rostoucí podposloupnosti ze skript.

22.5. (do neomezeno)

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 $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)$.
Jsou dány rovnoramenné váhy a 12 kuliček, z nichž právě jedna je jiná než ostatní, nevíme však zda je lehčí nebo těžší. Na misku lze dát i více kuliček naráz. Navrhněte, jak na 3 vážení najít tuto jinou kuličku a zjistit, jestli je lehčí nebo těžší. Dokažte, že na 2 vážení to nejde.