Algoritmy a datové struktury I

Cvičení k přednášce Algoritmy a datové struktury I [NTIN060] v letním semestru 2019/2020. Probíhá v pondělí od 12:20 v S10.

Požadavky na zápočet

Tabulka výsledků

Průběh virtuálního cvičení

V obvyklou dobu, tj. pondělí 12:20, se sejdeme virtuálně skrz platformu Zoom. Vždy vám s předstihem zašlu odkaz, do místnosti se bude dát připojit již před oficálním začátkem cvičení.

Cvičení bude probíhat obdobně jako prezenčně - tj. na začátku si trochu zopakujeme potřebnou látku z přednášky, a poté budeme řešit úlohy. Zadání úloh zveřejním se začátkem cvičení na webu. Pokud se nemůžete zúčastnit virtuálního cvičení, velmi doporučuji zamyslet se nad úlohami samostatně. Během pondělního odpoledne se pak na webu také objeví náznaky řešení, které vám pomohou pakliže si s nějakou úlohou nebudete vědět rady.

Pokud si s čímkoliv nebudete vědět rady, budete tápat nebo jen chtít popostrčit správným směrěm, neváhejete se ozvat. Rád odpovím na dotazy mailem nebo cokoliv (do)vysvětlím ať už individuálně nebo skupinově na Zoomu.

Protože je tenhle způsob fungování nový pro nás pro všechny, budu rád když se ozvete s jakoukoliv zpětnou vazbou, přípomínkou či nápadem na zlepšení.

Co jsme dělali

17. 2. 2020
Úvodní informace a pár zahřívacích úloh. Házení vajíček, součty dvojic a součty úseků posloupností. [Příklady 1-4]
23. 2. 2020
Cvičil Miloš Chromý. Zavedení asymptotické notace a její použití. [Příklady]
2. 3. 2020
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-6]
9. 3. 2020
Další příklady na prohledávání grafů a stavových prostor. Topologické třídění a rozklad na komponenty silné souvislosti. [Příklady 1-5]
16. 3. 2020
Organizace vzdálené výuky. Dijkstrův algoritmus a proč ho nechceme používat na grafech obsahujících záporné hrany. Příklady na hledání nejkratší cesty. [Příklady] [Náznaky řešení]
23. 3. 2020
Bellman-Fordův a Floyd-Warshallův algoritmus na hledání nejkratších cest. [Příklady 1-3] [Náznaky řešení]
30. 3. 2020
Minimální kostry. [Příklady 1-5] [Náznaky řešení]
6. 4. 2020
Binární vyhledávácí stromy a operace s nimi. [Příklady] [Náznaky řešení]
20. 4. 2020
Pokračování binárních vyhledávácích stromů a $(a,b)$-stromy. [Příklady] [Náznaky řešení]
27. 4. 2020
Amortizace. [Příklady] [Náznaky řešení]
4. 5. 2020
Hashování. [Příklady] [Náznaky řešení]
11. 5. 2020
Rozděl a panuj. Příklady na použití kuchařkové věty. [Příklady] [Náznaky řešení]
18. 5. 2020
Quickselect, Quicksort, Linearselect. [Příklady] [Náznaky řešení]
25. 5. 2020
Dynamické programování. [Příklady] [Náznaky řešení]

Domácí úkoly

Úkoly odevzdávejte pomocí emailu. Ideálně sázejte v $\LaTeX \text{u}$, nebo můžete poslat odkaz na hackmd.io, což je nejjednodušší způsob jak si sázení matematiky osahat (malá ukázka). Rukou psané řešení posílejte kvalitně naskenované, existují rozumné skenovací aplikace pro Android i iOS.

1. Různá písmena (do 2.3.) 4b.
Na vstupu je text složený z písmen anglické abecedy a mezer. Vymyslete algoritmus, který najde nejdelší úsek textu, v němž se žádné písmeno (nepočítáme mezery) neopakuje.
2. $\Theta + \Theta$ (do 9.3.) 5b.
Mějme 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))$.
3. Rychlé matice (do 16.3.) 7b.
Uvažujeme výpočetní model RAM s konstantní cenou instrukce a neomezeným rozsahem čísel. Vymyslete algoritmus, který dostane dvě matice $N \times N$ nezáporných čísel a v čase $\mathcal{O}(N^2)$ je vynásobí.
4. Uvěznění roboti (do 16.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$.
5. Kritické vrcholy (do 23.3.) 4b.
Stavíme dům a sestavíme si závislostní graf všech činností. O vrcholu tohoto grafu řekneme, že je kritický, pokud by zpomalení příslušné činnosti způsobilo pozdější dokončení celého domu. Při řízení stavby si proto na takové vrcholy musíme dávat pozor. Vymyslete, jak je všechny najít.
6. Polosouvislost (do 23.3.) 6b.
O orientovaném grafu řekneme, že je polosouvislý, pokud mezi každými dvěma vrcholy vede orientovaná cesta alespoň jedním směrem. Navrhněte lineární algoritmus, který polosouvislost grafu rozhoduje.
7. Krátké hrany (do 30.3) 5b.
Máme ohodnocený orientovaný graf G s nezápornými hranami a dva jeho vrcholy $s$ a $t$. Vymyslete algoritmus, který nalezne všechny hrany, jež leží na alespoň jedné nejkratší cestě z $s$ do $t$.
8. Poctivá směnárna (do 6.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.
9. Matice dosažitelnosti (do 6.4.) 7b.
Matice dosažitelnosti grafu je taková matice $R$, že $R_ij = 1$ právě tehdy když z vrcholu $i$ vede cesta do vrcholu $j$. Vymyslete jak pro graf spočítat matici dosažitelnosti v čase $o(n^3)$.
10. Listnatá kostra (do 20.4.) 5b.
Pro neorientovaný ohodnocený graf $G=(V,E,w)$ a množinu vrcholů $S\subseteq V$ navrhněte algoritmus, který najde minimální kostru grafu $G$, u které jsou všechny vrcholy z množiny $S$ listy nalezené kostry. Ostatní vrcholy mohou být také listy, tedy například pro $S = \emptyset$ hledáme obvyklou minimální kostru.
11. Okénkový medián (do 27.4.) 5b.
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.
12. Join na místě (do 4.5.) 8b.
Navrhněte algoritmus, který sloučí dva stromy $T_1$ a $T_2$ do jediného dokonale vyváženého stromu $T$ v čase $O(\vert T_1\vert +\vert T_2\vert)$ s využitím pouze $O(1)$ paměti navíc.
13. Minimový strom (do 11.5.) 5b.
Minimový binární strom $M(a)$ pro zadanou posloupnost $a = (a_1,\ldots ,a_n)$ bez opakujících se prvků je definován takto: Buď $a_i$ minimální prvek $a_1, \ldots ,a_n$ pak kořen $M(a)$ je $a_i$, jeho levý podstrom je $M(a_1, \ldots ,a_{i−1})$ a pravý podstrom $M(a_{i+1},\ldots,a_n)$. $M(\emptyset)$ je prázdný strom. Pro zadanou posloupnost postavte minimový strom v čase $O(n)$.
14. Závorky (do 11.5.) 7b.
Je dána posloupnost levých a pravých závorek délky $n$. Vymyslete datovou strukturu, která umí operace „otoč závorku na pozici i“ v čase $O(\log n)$ a „zjisti, jestli je posloupnost dobře uzávorkovaná“ v čase $O(1)$.
15. Okénkové minimum (do 11.5.) 6b.
Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište minimum z posledních $k$ čísel. Dosáhněte časové složitosti $O(1)$ amortizovaně na operaci.
16. Hledáme přesmyčky (do 18.5.) 5b.
Jsou dány dvě slova $j$ a $s$ nad abecedou $[\mathtt{a}-\mathtt{z}]$. Najděte všechny pozice v $s$ kde se nachází nějaká přesmyčka $j$. Přesmyčka $j$ je řetězec vzniklý z $j$ libovolným přeházením písmen.
17. Inverze v posloupnosti (do 25.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)$.
18. LinearSelect (do 1.6.) 5b.
Upravte algoritmus LinearSelect tak, aby si vystačil s konstantně velkou pomocnou pamětí. Prvky ve vstupním poli můžete libovolně přeskupovat.
19. Depeše (do 8.6.) 5b.
Dešifrovali jsme tajnou depeši, ale chybí v ní mezery. Známe však slovník všech slov, která se v depeši mohou vyskytnout. Rozdělte depeši na co nejméně slov ze slovníku.

Užitečné odkazy