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) + Θ(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)
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ů.

DatumKódBodůZadání
23. 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. Dejte si pozor, abyste správně zaokrouhlovali.
bug0Ke 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. ram9Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti.
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í.
mmul10Podnikneme 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(N2) je vynásobí.
9. 3. oadel10Uvaž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.
psum10Je 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. muls8Odvoďte prostorovou složitost rekurzivního algoritmu na násobení čísel z cvičení.
kabel10/15Mě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ů.
klow8Dokaž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. rec17Vyřešte rekurenci T(n) = 3T(n/2) + 1, T(1) = 1.
rec210Vyřešte rekurenci T(n) = T(n/3) + T(n/7) + n, T(1) = 1.
base12Má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 Θ(n2). (Pozor, číslo se nemusí vejít do jedné celočíselné proměnné.)
30. 3. lib10Posloupnost 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.)
12k10/15Jsou 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. kkun7Na 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?
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.
13. 4. zpet6Na 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ý?
stack7Nabí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?
paths10Je dán neorientovaný graf a dva jeho vrcholy. Spočítejte, kolik mezi nimi vede nejkratších cest.
20. 4. utop9Jak poznat grafy, které lze topologicky uspořádat právě jedním způsobem?
dum10Stavba 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. rexp10/14Ukaž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 navíc: pokud to dokážete s relaxováním vrcholu s nejnižším ohodnocením jako v Dijkstrovi.
ksled9Mě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. irank8Ukaž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).
prank10Uvaž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. usum10/12Je 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.
avl112Vymyslete, 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.
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ý.
18. 5. lmst8/12Mě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.

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.

Stránku spravuje Martin Mareš