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

V LS 2012/2013 vedu jedno cvičení ke své přednášce z ADS1. Koná se každé úterý od 10:40 v S10.

Co jsme dělali

datum	téma
19. 2.	Co je to algoritmus a jak je můžeme srovnávat. Rekurzivní hádanky a složitost aritmetiky.
26. 2.	Ještě trocha aritmetiky: největší společný dělitel Euklidovým algoritmem i půlením. Jakou složitost má Eratosthenovo síto? Odhad součtu harmonické řady a řady převrácených hodnot prvočísel.
5. 3.	Programování na RAMu: bublinkové třídění, násobení matic. Jak by mohl fungovat překladač z Céčka do RAMu.
12. 3.	Prohledávání grafů: komponenty souvislosti, porouchané autíčko, dva roboti v bludišti, nejdelší společná podposloupnost.
19. 3.	Počet cest mezi dvěma vrcholy v DAGu. Počet nejkratších cest. Počet sledů dané délky.
26. 3.	Mosty a artikulace. Průměr stromu. Maximální nezávislá množina v ohodnoceném stromu. (Cvičil Martin Kupec.)
2. 4.	Relaxujeme. Přesněji dokazujeme různá tvrzení o relaxačním algoritmu.
9. 4.	Komponenty silné souvislosti a "falešné topologické uspořádání". Minimálně koster: co když jsou některé hrany stejně těžké?
16. 4.	Vyhledávací stromy: hledání následníků, průchod stromem přes následníky, operace Rank a Index.
23. 4.	Amortizovaný odhad vkládání do (a,b) stromů. Medián sjednocení. Nejdelší podposloupnost bez opakování prvků. Protínající se intervaly. (Cvičil Tom Gavenčiak.)
30. 4.	Vyvažování vyhledávacích stromů rekonstrukcí a analýza penízkovou metodou. Amortizovaný odhad na inkrementaci binárního čísla. Intervalové stromy.
7. 5.	Hledání cesty dané délky v ohodnoceném stromu.
14. 5.	Rozděl a panuj: Umocňování není jednodušší než násobení. Propojování drátů. Počítání inverzí v permutacích. Nejbližší dvojice bodů v rovině.
21. 5.	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)

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í
19. 2.	krac	8	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	10	Vyluštěte šifru a pošlete mi heslo (spolu se zdůvodněním).
26. 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).
	kopec	8	Variace na úlohu z první přednášky: chceme v zadané posloupnosti celých čísel najít nejdelší "kopec", tedy podposloupnost, která nejprve roste a pak klesá.
5. 3.	rsito	8	Naprogramujte Eratosthenovo síto na RAMu.
5. 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í.
12. 3.	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?
	dele	10	Mějme souvislý graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?
19. 3.	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ýpust, 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.
	jtop	9	Vymyslete, jak poznat grafy, které mají lze topologicky uspořádat právě jedním způsobem.
	straz	10	Mějme městečko, jehož uliční síť má tvar stromu: hrany jsou ulice, vrcholy křižovatky (či slepé konce). U každého vrcholu víme, kolik peněz stojí postavit tam strážníka. Rozmyslete, jak co nejlevněji rozmístit strážníky tak, aby každá ulice byla aspoň z jedné strany hlídaná.
26. 3.	npok	7	Může v nějakém grafu existovat množina vrcholů, která by byla současně vrcholovým pokrytím i nezávislou množinou? Charakterizujte všechny případy, kdy to nastane.
	hous	11	Housenka je graf, který se skládá z těla (cesta) a štětin (listy připojené k vrcholům cesty). Najděte v daném stromu podgraf s největším počtem vrcholů, který je isomorfní s nějakou housenkou.
	nnz	8	Jak pro daný strom spočítat, kolik v něm existuje nezávislých množin?
2. 4.	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).
	vcap	8	Mějme mapu silniční sítě coby orientovaný graf. Za průjezd vrcholem se platí mýto (celé kladné číslo). Jak najít cestu mezi dvěma městy, za níž zaplatíme nejméně?
	maxp	10	Mějme orientovaný graf. Každá hrana je ohodnocena spolehlivostí, což je reálné číslo mezi 0 a 1. Spolehlivost cesty definujeme jako součin spolehlivostí hran. Chceme najít nejspolehlivější cestu mezi danými dvěma vrcholy.
	add	6	Můžeme se v algoritmech na hledání nejkratších cest zbavit záporných hran tím, že ke všem hranám přičteme totéž dostatečně velké číslo?
9. 4.	lpath	8	Mějme orientovaný graf s hranami ohodnocenými celými čísly od 1 do L. Vymyslete co nejefektivnější algoritmus pro nalezení nejkratší cesty, 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.
	lmst	10	Totéž jako předchozí úloha, ale pro minimální kostru.
	cont	9	Dokažte kontrakční lemma: Nechť G je graf, T jeho minimální kostra, e hrana ležící v T. Nechť dále G/e je graf vzniklý z G kontrakcí hrany e (se zachováním násobných hran a smyček). Potom T/e je minimální kostra grafu G/e. (Jinými slovy, minimální kostru můžeme získat tak, že uhodneme jednu hranu, která v ní leží, zkontrahujeme ji, rekurzivně najdeme min. kostru menšího grafu a tu pak "odkontrahujeme".)
16. 4.	irank	5	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).
	rebal	12	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(1) hodnot.
	succ	9	Mějme vyhledávací strom s n vrcholy. Dokažte, že začneme-li v libovolném vrcholu a pak budeme k-krát hledat následníka, potrvá to O(k + hloubka stromu).
23. 4.	muni	10	Máme dvě setříděné poslupnosti a chceme najít medián jejich sjednocení. Na cvičení jsme ukázali řešení v čas O(log² n), vylepšete ho na O(log n).
23. 4.	abjoin	10	Nechť A, B jsou dva (a,b) stromy takové, že všechny kliče v A jsou menší než všechny klíče v B. Vymyslete algoritmus, který oba stromy v logaritmickém čase sloučí do jednoho.
30. 4.	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).
	itree	12	Naprogramujte intervalový strom s operacemi Set (změna hodnoty) a Min (výpočet minima intervalu).
	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á".
7. 5.	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ý.
7. 5.	path	10	Je dána cesta s celočíselně ohodnocenými hranami a číslo X. Jak zjistit, zda existuje podcesta se součtem přesně X?
14. 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ů. Tuto úlohu a všechny následující můžete odevzdávat za plný počet bodů až do konce června.
	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.
21. 5.	mini	10	Definujme minimový strom takto: v kořeni je minimum posloupnosti, levý podstrom je minimový strom prvků nalevo od minima, pravý analogicky. Vymyslete algoritmus, který v čase O(n) takový strom sestrojí.
	bulv	10	Redaktor jistého newyorského bulvárního listu chce zaznamenat všechny události, které se dnes stanou. Zná posloupnost křižovatek (New York pro tyto účely považujme za pravidelnou čtvercovou mřížku), kde budou události nastávat, a ví, že každou vyfotí, pokud se bude v daný okamžik nacházet na stejné avenue nebo street (tedy mít stejnou x-ovou nebo y-ovou souřadnici). Nalezněte pro redaktora trasu, která začíná i končí v redakci (bod (0,0)), umožňuje vyfotit všechny události a je nejkratší možná.
	pert	10	Navrhněte vyhledávací strom, který si pamatuje svou historii a umí odpovídat na dotazy typu "byl v množině prvek X v čase T?". Pokuste se zachovat časovou složitost operací O(log n) a spotřebovat co nejméně paměti.

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.