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

V LS 2016/2017 vedu jedno cvičení k přednášce Ondřeje Čepka z Algoritmů a datových struktur I. Cvičení je primárně určené pro posluchače bioinformatiky, ale po domluvě se tam mohou přihlašovat i studenti jiných oborů.

Cvičení se koná ve čtvrtek od 15:40 v S10.

Co jsme dělali

datum	téma
23. 2.	Rekurzivní hádanky a Euklidův algoritmus.
2. 3.	Pokusy o definici algoritmu a časové složitosti. Programování na RAMu. Jak zneužívat velká čísla.
9. 3.	O datových strukturách a jejich rozhraní. Různé varianty hešování.
16. 3.	Rozděl a panuj: Mergesort a násobení čísel.
23. 3.	Rozděl a panuj: Počítání inverzí, odvození Kuchařkové věty. 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)
30. 3.	Hrátky s Bubblesortem. Přihrádkové třídění v poli. Třídění s log n různými hodnotami. Stabilní slévání. Třídění řetězců.
6. 4.	O složitosti třídění – co věta říká a co neříká. Komponenty souvislosti, testování bipartitnosti, porouchané autíčko.
13. 4.	Dva roboti v bludišti. DFS a klasifikace vrcholů. Mosty v grafech. Jak najít kružnici v orientovaném grafu?
20. 4.	Topologické uspořádáni a indukce podle něj.
27. 4.	O grafové metrice. Dijkstrův algoritmus: proč selže na záporných hranách, proč nepomůže přičíst ke všem hranám konstantu, co si počít s ohodnocenými vrcholy. Nejpravděpodobnější cesta.
4. 5.	Vyhledávací stromy: hledání následníků, průchod stromem přes následníky, budování dokonale vyváženého stromu.
11. 5.	Vyvažování AVL stromů.
18. 5.	Minimální kostry: řezové lemma, Jarníkův, Borůvkův a Kruskalův algoritmus a jejich implementace.

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í
23. 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)². Dejte si pozor, abyste správně zaokrouhlovali.
	bug	0	Ke konci semestru vydáváme knížku o ADS. Budu rád, když se na ni podíváte a upozorníte na všechny chyby, na které narazíte. Za každou novou faktickou chybu dostanete 1 bod.
2. 3.	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.
	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í.
	mmul	10	Podnikneme pokus s RAMem s konstantní cenou instrukce a neomezeným rozsahem čísel. Vymyslete algoritmus, který dostane dvě matice N×N, nezáporných čísel a v čase O(N²) je vynásobí.
9. 3.	oadel	10	Uvažujme následující variantu hešování s otevřenou adresací: v každé buňce tabulky si pamatujeme prvek a počet následujících prvků se stejnou hodnotou hešovací funkce. Navrhněte algoritmy pro operace Find, Insert a Delete.
9. 3.	psum	10	Je dána posloupnost celých čísel a číslo X. Existují nějaké dva (ne nutně různé) prvky posloupnosti, jejichž součet je přesně X? Pokuste se najít algoritmus pracující co nejrychleji (a) v průměru, (b) v nejhorším případě.
16. 3.	muls	8	Odvoďte prostorovou složitost rekurzivního algoritmu na násobení čísel z cvičení.
	kabel	10/15	Mějme dlouhý kabel, z jehož obou konců vystupuje po n drátech. Každý drát na levém konci je propojen s právě jedním na konci druhém a my chceme zjistit, který s kterým. K tomu můžeme používat následující operace: (1) přivést napětí na daný drát na levém konci, (2) odpojit napětí z daného drátu na levém konci, (3) změřit napětí na daném drátu na pravém konci. Navrhněte algoritmus, který pomocí těchto operací zjistí, co je s čím propojeno. Snažte se počet operací minimalizovat. 5 bodů navíc: Nalezněte neadaptivní řešení předchozího cvičení, tedy takové, v němž položené dotazy nezávisí na výsledcích předchozích dotazů.
	klow	8	Dokažte, že v úloze o kabelu je potřeba Ω(n log n) dotazů. Pokud nevíte, jak na to, dokažte to alespoň pro neadaptivní algoritmy.
23. 3.	rec1	7	Vyřešte rekurenci T(n) = 3T(n/2) + 1, T(1) = 1.
	rec2	10	Vyřešte rekurenci T(n) = T(n/3) + T(n/7) + n, T(1) = 1.
	base	12	Máme n-ciferné číslo v soustavě o základu A a chceme ho převést do soustavy o základu B. Prozradíme, že existuje efektivnější řešení než v Θ(n²). (Pozor, číslo se nemusí vejít do jedné celočíselné proměnné.)
30. 3.	lib	10	Posloupnost N prvků byla krásně setříděná. I šla okolo zlá Bugzilla, vytáhla K prvků a vsunula je jinam. Jak posloupnost co nejrychleji opravíte? (K neznáte, ale můžete předpokládat, že je malé, a složitosti vyjadřovat vzhledem k N a K.)
30. 3.	12k	10/15	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. 5 bodů navíc: Kdybychom měli kuliček 13, ale slevili z požadavku zjistit, zda je odlišná kulička lehčí nebo těžší, stále stačí 3 vážení. Pro 14 ale ne. Dokažte.
6. 4.	kkun	7	Na jedné šachovnici N×N žil byl kulhavý kůň. To je šachová figurka, která v sudém tahu táhne jako jezdec, v lichém jako král. Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?
	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.
13. 4.	zpet	6	Na orientovaný graf jsme spustili DFS. Může se v grafu nacházet kružnice složená ze samých zpětných hran? A pokud by graf byl neorientovaný?
	stack	7	Nabízí se svůdná myšlenka, že DFS získáme z BFS nahrazením fronty zásobníkem. Na čem tento postup selže?
	paths	10	Je dán neorientovaný graf a dva jeho vrcholy. Spočítejte, kolik mezi nimi vede nejkratších cest.
20. 4.	utop	9	Jak poznat grafy, které lze topologicky uspořádat právě jedním způsobem?
20. 4.	dum	10	Stavba domu sestává ze spousty činností, z nichž některé je potřeba provést dříve než jiné. Situaci popíšeme grafem: vrcholy jsou činnosti (ohodnocené tím, jak dlouho trvají), orientované hrany vyjadřují závislosti. Spočítejte, za jakou nejkratší dobu lze postavit celý dům, pokud máme neomezeně mnoho pracovníků vykonávajících všechny činnosti. Jak najít kritické činnosti, tedy ty, jejichž prodloužení by způsobilo zpoždění dokončení celé stavby?
27. 4.	rexp	10/14	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 navíc: pokud to dokážete s relaxováním vrcholu s nejnižším ohodnocením jako v Dijkstrovi.
27. 4.	ksled	9	Mějme 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ý právě k hranami.
4. 5.	irank	8	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).
4. 5.	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?
11. 5.	usum	10/12	Je dána posloupnost a číslo X. Najděte v posloupnosti souvislý úsek, jehož součet je roven X. 2 body navíc: jehož součet se co nejvíce blíží číslu X.
	avl1	12	Vymyslete, jak ukládat znaménka do vrcholů AVL stromu tak, abyste si vystačili s jedním bitem na vrchol. Znaménko vrcholu musí být z uložených bitů spočítat v konstantním čase.
	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ý.
18. 5.	lmst	8/12	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.
18. 5.	mst2	12	Chceme nalézt druhou nejlehčí kostru.

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 jako obyčejný text nebo PDF.