[home]
ADS I (2019/2020)
Cvičení k přednášce Algoritmy a datové struktury I
Doporučená literatura
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.
- Zopakovali jsme asymptotickou notaci pro třídy $O, \Omega, \Theta, o, \omega$. Dokázali jsme některá jednoduchá tvrzení ($O$ aritmetika) a porovnaly některé funkce.
- Vyzkoušeli jsme si jak zapisovat pseudokody na příkladech hledání úseku s největším součtem (v $O(n)$) a binárním vyhledávání.
- 28.2.
- Začali jsme s grafovými algoritmy - BFS a DFS
- BFS i DFS jsme si zkusili odkrokovat na příkladě orientovaného grafu. Provedli jsme klasifikaci hran a zjistili jsme, které se nemohou vykytovat v neorientovaných grafech.
- Použili jsme BFS na hledání nejkratší cesty v grafu možných stavů.
- 6.3.
- Zopakovali jsme DFS, definovali in, out a low pro vrcholy. Pomocí nich jsme v rychlosti ukázali algoritmus pro hledání mostů a artikulací. Pomocí in a out jsme definovali jak vypadají stromové, dopředné, zpětné a příčné hrany.
- Definovali jsme DAG, našli algoritmus jak pro daný DAG najít topologické uspořádání. Vyřešili jsme pár příkladů na topologickou indukci (nejkratší a nejdelší cesty, počet nejkratších cest).
- 13.3.
- Hodina se ruší. Zadané úkoly jsou na téma nejkratších cest. Zopakujte si toto téma ve skriptech, kapitola 6.
- 20.3.
- První cvičení pomocí Zoom. Zopakovali jsme si 3 kostrové algoritmy. Rozmysleli jsme si časovou složitost pomocí základních datových struktur. Proto jsme zopakovali i základní operace na haldě.
- Další příklady - důkaz, že mosty jsou ve všech kostrách; opravení Borůvkova algoritmu, aby pracoval i s neunikátními vahami.
- 27.3.
- Podívali jsme se na binární vyhledávací stromy. Jakmile jsme přišli na to, jak vypsat BVS in-order a ze seřazeného pole vytvořit dokonale vyvážený BVS, všechny ostatní příklady byly lehké - BVSsplit, BVSmerge, dokonaleé vyvážení v O(n).
- 3.4.
- Odkrokovali jsme insert na AVL stromech. Definovali jsme (a,b)-stromy a odkrokovali na nich insert.
- Ukázali jsme ekvivalenci červeno-černých stromů a (2,4)-stromů. Na detailní popis insertu a deletu nezbyl čas.
- 17.4.
- Podívali jsem se na amortizovanou složitost - účetní a penízková metoda. Zopakovali jsme nafukovací pole a binární počítadlo.
- Ukázali jsme, že odečítání zkazí amortizovanou složitost binárního počítadla. Ukázali jsme jak udělat ze dvou zásobníků frontu s amortizovanou konstantní složitostí.
- Připomněli jsme jaký je rozdíl mezi hešováním s přihrádkami a s otevřenou adresací. Na hešování se podíváme ještě příště.
- 24.4.
- Pokračovali jsme v hešování - odkrokovali jsme hešování s otevřenou adresací.
- Algoritmy typu rozděl a panuj - spletitý kabel, inverze v posloupnosti, nekuchařkové rekurence.
- 8.5.
- Náhradní cvičení za odpadlé ze dne 13.3.
- Nejkratší cesty - obecný relaxační algoritmus, jeho zastavení a využití.
- Floyd-Warshall - odkrokování, detekce záporného cyklu, rekonstrukce nejkratší cesty.
- 15.5.
- Pokračovali jsme s algoritmy rozděl a panuj. Připomněli jsme si hledání k-tého nejmenšího prvku v lineárním čase. Ukázali, proč se berou pětice místo trojic nebo sedmic.
- Zasekli jsme se u řešení příkladu na hledání mediánu dvou setříděných posloupností. K tomu se vrátíme příští hodinu.
- Začali jsme s dynamickým programováním - zatím jsme jen zmínili příklady ze skript (Fibonacciho čísla a nejdelší rostoucí podposloupnost). S tématem budeme pokračovat příště.
- 22.5.
- Opravili jsme řešení mediánu dvou setříděných posloupností. Hezky vysvětlené správné řešení lze najít zde.
- Ukázali jsme dolní odhad třídění a vážili kuličky.
- Pokračovali jsme s dynamickým programováním.
- 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.