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) + Θ(n²) 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) = n^1/2 T(n^1/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 A_i,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ů.

Datum	Kód	Bodů	Zadání
16. 2.	krac	9	Přirozenému číslu budeme říkat kráčmerné, pokud ho jde zapsat ve tvaru 3ⁱ5^j7^k pro nějaká přirozená i, j, k. Vymyslete algoritmus, který co nejefektivněji najde prvních N kráčmerných čísel.
	sqrt	7	Jak spočítat celočíselnou druhou odmocninu? Tím pro dané x myslíme přirozené číslo y takové, že y²≤ x < (y+1)².
	sifra	8	Vyluštěte šifru a pošlete mi heslo (spolu se zdůvodněním).
23. 2.	sito	10	Upravte Eratosthenovo síto, aby si vystačilo s pamětí O(n^1/2), a přitom nebylo asymptoticky pomalejší.
	divs	12	Upravte 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).
	ram	9	Naprogramujte 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.	bube	10	Jaká 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í.
	sotek	9	Tiskař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é.
	kkun	7	Na 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.	dele	9	Mě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ý?
	sink	10	Mě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.
	nnz	10	O 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.	jtop	9	Vymyslete, jak poznat grafy, které mají lze topologicky uspořádat právě jedním způsobem.
	pnc	10	Je 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.
	6col	10	Má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.	rexp	10	Ukaž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ě cⁿ 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]
	4cykl	8	Mějme ohodnocený orientovaný graf. Chceme v něm najít nejkratší cyklus ze čtyř hran v čase lepším než Θ(n^4).
	ksled	9	Opě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.	zcykl	10	Upravte 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ží.
	lmst	8	Mě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.
	mst2	12	Chceme nalézt druhou nejlehčí kostru.
13. 4.	rmin	8	Implementujte operace s intervalovým stromem z cvičení: čtení prvku, zápis prvku, výpočet minima přes interval indexů.
	rebal	10	Vymyslete 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í.)
	irank	7	Ukaž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.	prank	10	Uvažme posloupnost všech permutací na množině 1,…,n uspořádanou lexikograficky. Jak nalézt k-tou permutaci v této posloupnosti?
	addmin	10	Navrhněte datovou strukturu, která udržuje posloupnost x₁,…,x_n 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 x_i,x_i+1,…,x_j číslo δ, a Min(i,j), která vrátí minimum z hodnot x_i,x_i+1,…,x_j.
	paren	12	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" a "zjisti, jestli je posloupnost dobře uzávorkovaná".
27. 4.	abjoin	10	Nechť 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.
	cntr	10	Uvaž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).
	union	12	Dokaž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.	queue	9	Ukaž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áří.
	uniq	10	Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, ve kterém se žádné číslo neopakuje.
	words	9	Je dán text rozdělený na slova. Jak najít nejčastější slovo?
11. 5.	nonad	10	Nalezně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ů.
	lowbd	10	Ukažte, že v úloze o drátech je potřeba Ω(n log n) dotazů. Jednodušší verze: dokažte to alespoň pro neadaptivní algoritmy.
	hanoi	10	Uvaž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.