Cvičení z Algoritmů a Datových Struktur I

V LS 2014/2015 vedu jedno cvičení ke své přednášce z ADS1. Koná se každé pondělí od 15:40 v S10.

Co jsme dělali

datum téma
16. 2. Rekurzivní hádanky a složitost aritmetiky.
23. 2. Hrátky s prvočísly a RAMem. Jakou složitost má Eratosthenovo síto? A jakou zkoušení dělitelů do odmocniny? Odhad součtu harmonické řady a řady převrácených hodnot prvočísel.
2. 3. Prohledávání grafů: komponenty souvislosti, test stromovosti, test bipartitnosti, porouchané autíčko, dva roboti v bludišti, nejdelší společná podposloupnost.
9. 3. DFS na stromech: hloubka stromu, nejdelší cesta, rozmisťování strážníků, hradní posádky.
16. 3. Hledání artikulací. Kreslení jedním tahem propojováním cyklů a také pomocí DFS.
23. 3. Dijkstrův algoritmus: proč selže na záporných hranách, proč nepomůže přičíst ke všem hranám konstantu, přihrádková struktura pro malá celá čísla. Nejpravděpodobnější cesta.
30. 3. Jak zbohatnout ve směnárně. Potenciálový trik na odstranění záporných hran. Minimalní kostry: Implementace Jarníkova algoritmu.
13. 4. Vyhledávací stromy: hledání následníků, průchod stromem přes následníky, hledání k-tého nejmenšího prvku. Intervalové stromy nad polem.
20. 4. Počítání inverzí pomocí vyhledávacích stromů i bez nich. Zdobení AVL-stromů. Minimální a maximální hloubka (a,b)-stromu.
27. 4. Mazání z (a,b)-stromu. Amortizovaná analýza: inkrementace binárního čísla, penízková metoda, vkládání do (a,b)-stromu. Na okraj: srovnání rychlosti datových struktur na skutečném počítači.
4. 5. Pokračujeme v amortizování: vyvažování vyhledávacích stromů rekonstrukcí, další pokusy s (a,b)-stromy. Na okraj: kouzlo striktně funkcionálních jazyků a z něj plynoucí trampoty s datovými strukturami.
11. 5. Rozděl a panuj: Přepojování drátů. Rekurence nejen kuchařkové:
  • T(n) = 2T(n/2) + Θ(n2)
  • T(n) = 2T(n/3) + Θ(n)
  • T(n) = T(n/2) + Θ(1)
  • T(n) = T(n/2) + T(n/3) + Θ(n)
  • T(n) = 2T(n) + Θ(n log n)
  • T(n) = n1/2 T(n1/2) + Θ(n)
18. 5. Úlohy skoro zkouškové:
  • Je dána matice A přirozených čísel, která v každém řádku i sloupci roste. Najděte (i,j) takové, že Ai,j=i+j. (Jednodušší verze: matice má jen jeden řádek.)
  • Mějme strom s ohodnocenými hranami a číslo X. Existuje ve stromu cesta, se součtem ohodnocení hran přesně X? (Jednodušší verze: strom se nevětví.)
  • Navrhněte datovou strukturu, která bude reprezentovat posloupnost a bude umět přidat prvek na konec a vrátit minimum z posledních K prvků. (Kde K zvolíme pevně při inicializaci struktury.)
  • Dotřídění knihovny: někdo ze setříděné posloupnosti vyndal K prvků a vrátil je jinam. Jak posloupnost dotřídit? (K předem neznáme.)
  • Robot vězí kdesi v čtverečkovém bludišti. Posíláme mu posloupnost příkazů (vlevo, vpravo, dopředu, dozadu), stejnou stále dokola. Příkaz, který nelze provést (je tam zeď), robot ignoruje. Pro které počáteční polohy robota platí, že jednou vyleze ven?
  • Navrhněte datovou strukturu, která umí Insert, Delete a nalezení mediánu. Dokažte, že jste dosáhli optimální časové složitosti.

Domácí úkoly

Na cvičeních budu zadávat různě obtížné domácí úkoly, měli byste za ně získat celkem 100 bodů. Po dvou týdnech od zadání úkolu na cvičení povím nápovědu, od té doby můžete za úkol získat jen poloviční počet bodů.

DatumKódBodůZadání
16. 2. krac9Přirozenému číslu budeme říkat kráčmerné, pokud ho jde zapsat ve tvaru 3i5j7k pro nějaká přirozená i, j, k. Vymyslete algoritmus, který co nejefektivněji najde prvních N kráčmerných čísel.
sqrt7Jak spočítat celočíselnou druhou odmocninu? Tím pro dané x myslíme přirozené číslo y takové, že y2≤ x < (y+1)2.
sifra8Vyluštěte šifru a pošlete mi heslo (spolu se zdůvodněním).
23. 2. sito10Upravte Eratosthenovo síto, aby si vystačilo s pamětí O(n1/2), a přitom nebylo asymptoticky pomalejší.
divs12Upravte Eratosthenovo síto, aby pro každé číslo od 1 do n spočítalo, kolik má dělitelů. Časová složitost by neměla být horší než u původního síta, tedy O(n log log n).
ram9Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti.
2. 3. bube10Jaká je průměrná časová složitost bublinkového třídění? Přesněji: pokud dostaneme na vstupu náhodnou permutaci čísel 1 až n, jaká bude střední hodnota doby výpočtu? Předpokládáme, že algoritmus se zastaví, jakmile během jednoho průchodu nic neprohodí.
sotek9Tiskařský šotek umí za jednotku času změnit jedno písmenko na jiné, případně jedno písmenko vložit nebo smazat. Jak pro dvě zadaná slova zjistit, jak šotek nejrychleji upraví jedno na to druhé.
kkun7Na jedné šachovnici N×N žil byl kulhavý kůň. To je je šachová figurka, která v sudém tahu táhne jako jezdec, v lichém jako pěšec (o 1 dopředu). Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?
9. 3. dele9Mějme souvislý neorientovaný graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?
sink10Mějme graf, který vznikl orientací úplného grafu (tj. mezi každými dvěma vrcholy vede hrana buď jedním, anebo druhým směrem), reprezentovaný maticí sousednosti. Ukažte, jak zjistit, zda v grafu existuje výpusť, tj. vrchol, do kterého vedou hrany ze všech ostatních vrcholů. Zkuste dosáhnout časové složitosti O(počet vrcholů). Můžete předpokládat, že matici už máte načtenu v paměti.
nnz10O množině vrcholů grafu řekneme, že je nezávislá, pokud mezi žádnými dvěma vrcholy nevede hrana. Jak pro daný strom spočítat, kolik v něm nezávislých množin.
16. 3. jtop9Vymyslete, jak poznat grafy, které mají lze topologicky uspořádat právě jedním způsobem.
pnc10Je dán neohodnocený orientovaný graf a počáteční vrchol. Pro všechny ostatní vrcholy spočítejte, kolik do nich z počátečního vrcholu vede nejkratších cest.
6col10Máme rovinný graf a chceme jeho vrcholy obarvit 6 barvami. Algoritmus by měl mít lineární časovou složitost. (Až +10 dalších bodů: barvíme 5 barvami. Algoritmus by už nemusí být lineární, ale čím rychlejší, tím lépe.)
23. 3. rexp10Ukažte, jak pro každé n sestrojit graf na řádově n vrcholech, na kterém relaxační algoritmus s nešikovným pořadím relaxací provede řádově cn kroků (pro nějaké c>1). [+4 body, pokud to dokážete s relaxováním vrcholu s nejnižším ohodnocením jako v Dijkstrovi]
4cykl8Mějme ohodnocený orientovaný graf. Chceme v něm najít nejkratší cyklus ze čtyř hran v čase lepším než Θ(n^4).
ksled9Opět ohodnocený orientovaný graf. Jsou dány vrcholy u, v a číslo k. Spočítejte, jak dlouhý je nejkratší sled z u do v tvořený k hranami.
30. 3. zcykl10Upravte Bellmannův-Fordův algoritmus tak, aby nejen našel záporný cyklus dosažitelný z počátečního vrcholu, ale také vypsal, které vrcholy na něm leží.
lmst8Mějme neorientovaný graf s hranami ohodnocenými celými čísly od 1 do L. Vymyslete co nejefektivnější algoritmus pro nalezení minimální kostry. jeho složitost analyzujte vzhledem k velikosti grafu a číslu L. 8 bodů za algoritmus efektivní pro malé L (řekněme desítky), více, pokud bude efektivní i pro řádově větší L.
mst212Chceme nalézt druhou nejlehčí kostru.
13. 4. rmin8Implementujte operace s intervalovým stromem z cvičení: čtení prvku, zápis prvku, výpočet minima přes interval indexů.
rebal10Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený. Nemáte dost paměti na to, abyste si mohli pořídit ještě jednu kopii prvků – kromě stromu si smíte pamatovat O(log n) hodnot. (Další 2 body, pokud si vystačíte s konstantní pamětí.)
irank7Ukažte, jak upravit vyhledávací 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(hloubka).
20. 4. prank10Uvažme posloupnost všech permutací na množině 1,…,n uspořádanou lexikograficky. Jak nalézt k-tou permutaci v této posloupnosti?
addmin10Navrhněte datovou strukturu, která udržuje posloupnost x1,…,xn celých čísel. Na počátku posloupnost obsahuje samé nuly. K dispozici jsou operace Add(i,j,δ), která přičte ke všem hodnotám xi,xi+1,…,xj číslo δ, a Min(i,j), která vrátí minimum z hodnot xi,xi+1,…,xj.
paren12Je 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" a "zjisti, jestli je posloupnost dobře uzávorkovaná".
27. 4. abjoin10Nechť X, Y jsou dva (a,b)-stromy takové, že všechny kliče v X jsou menší než všechny klíče v Y. Vymyslete algoritmus, který oba stromy v logaritmickém čase sloučí do jednoho.
cntr10Uvažme n-bitový čítač, který podporuje operace INC a DEC (zvýšení a snížení o 1). Modifikujeme ho tak, že každý bit může nabývat hodnot 0, +1 a -1. Ukažte, že v této reprezentaci je amortizovaná složitost obou operací O(1).
union12Dokažte, že pro množiny reprezentované binárními vyhledávacími stromy není možné spočítat sjednocení v lepším než lineárním čase, a to ani v případě, kdy na vstupu dostanete dokonale vyvážené stromy a výstup nemusí být vyvážený.
4. 5. queue9Ukažte, jak pomocí dvou zásobníků simulovat frontu. Snažte se o amortizovaně konstantní časovou složitost operací (za předpokladu, že zásobník pracuje v konstantním čase).
Tuto úlohu a všechny následující můžete odevzdávat za plný počet bodů až do konce září.
uniq10Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, ve kterém se žádné číslo neopakuje.
words9Je dán text rozdělený na slova. Jak najít nejčastější slovo?
11. 5. nonad10Nalezněte neadaptivní algoritmus na úlohu o drátech ze cvičení. Tím se myslí takový, v němž položené dotazy nezávisí na výsledcích předchozích dotazů.
lowbd10Ukažte, že v úloze o drátech je potřeba Ω(n log n) dotazů. Jednodušší verze: dokažte to alespoň pro neadaptivní algoritmy.
hanoi10Uvažujme úlohu o Hanojských věžích ze skriptíček. Chceme přenést věž o n discích z trnu A na trn B pomocí trnu C, ale přidáme dodatečné pravidlo, které zakazuje přenášet disky přímo mezi A a B (v kterémkoli pořadí). Ukažte, že i s tímto pravidlem je úloha řešitelná a navíc každé korektní rozložení disků mezi trny navštívíme právě jednou.

Pokud je úkolem sestrojit algoritmus, nezapomeňte stanovit jeho časovou a paměťovou složitost.

Úkoly prosím posílejte na mj+ads@ucw.cz.

Stránku spravuje Martin Mareš