Zkouškové otázky z Algoritmů a datových struktur I
22. 5. odpoledne
- A1. Kruskalův algoritmus, jeho složitost a důkaz správnosti.
- A2. Násobení dlouhých čísel v lepším než kvadratickém čase.
- B1. Navrhněte efektivní datovou strukturu, která bude umět operace Insert, Delete a nalezení k-tého nejmenšího prvku. Dokažte, že asymptoticky lepší složitosti operací není možné dosáhnout.
- B2. Mějme bludiště ve tvaru čtvercové sítě, jejíž políčka obsahují místnosti, zdi, klíče K1 až Kk a odpovídající zamčené dveře D1 až Dk. Dveřmi Di je možno projít, pokud jste předtím alespoň jednou navštívili políčko s klíčem Ki. Vymyslete algoritmus, který najde (ne nutně nejkratší) cestu ven z bludiště.
- C. O orientovaném grafu řekneme, že je polosouvislý, pokud pro každou dvojici vrcholů (u,v) existuje cesta z u do v nebo z v do u (případně obě). Jak efektivně rozpoznat, zda je graf polosouvislý?
27. 5. verze α
- A1. Je dáno N celých čísel v rozsahu 0...N4-1. Ukažte, jak je setřídit v čase O(N).
- A2. Červeno-černé stromy: definice, důkaz logaritmické hloubky, popis operace Insert nebo Delete.
- B1. Je dán plán bludiště (čtvercová síť, políčka buď prázdná nebo zdi) a počáteční polohy dvou robotů v něm. Roboty chceme vyvést z bludiště (přes libovolnou hranu), ale příkazy (krok na sever, jih, východ, západ) dáváme oběma současně, přičemž robot, který by narazil do zdi, příkaz ignoruje. Vymyslete algoritmus, který najde nejkratší možnou posloupnost příkazů, která oba roboty vyvede.
- B2. V knihovně máme řadu N knih seřazenou podle unikátních názvů. Neposední čtenáři K knih vyndali a vrátili na jiná místa. Navrhněte co nejefektivnější algoritmus, který knihovnu dotřídí.
- C. Ukažte, že pokud máme algoritmus na inverzi trojúhelníkové matice N×N v čase T(N), můžeme ho využít ke konstrukci algoritmu pro násobení matic N×N v čase O(T(N)).
27. 5. verze β
- A1. Vyslovte a dokažte Kuchařkovou větu (Master theorem).
- A2. Popište algoritmus na hledání mostů v neorientovaných grafech.
- B1. Je dán neorientovaný graf s hranami ohodnocenými reálnými čísly. Navrhněte co nejefektivnější algoritmus, který v grafu nalezne nejdelší 4-cyklus (kružnici o čtyřech hranách s největším možným součtem ohodnocení). Využijte toho, že všechny vrcholy mají stupeň nejvýše 100.
- B2. 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 a dokázat, že je asymptoticky nejmenší možný.
- C. Stejné jako ve verzi α
3. 6.
- A1. Popište QuickSort a rozeberte jeho časovou složitost v nejlepším, nejhorším a průměrném případě.
- A2. Popište Bellmanův-Fordův algoritmus na nejkratší cesty. Kdy ho je vhodné použít?
- B1. Inverze v číselné posloupnosti x1, ..., xn je taková dvojice indexů (i,j), pro kterou platí i<j a současně xi > xj. Vymyslete algoritmus, který co nejefektivněji spočte, kolik je v posloupnosti inverzí.
- B2. Je dán neorientovaný neohodnocený graf a dva jeho vrcholy x, y. Navrhněte algoritmus, který spočítá, kolik existuje nejkratších cest z x do y.
- C. Jak najít druhou nejlehčí kostru?
10. 6.
- B1. Byla jednou jedna směnárna, která obchodovala s N měnami podle matice kursů K (Ki,j říká, kolik jednotek měny j získáme za jednotku měny i). Na počátku máme jednu korunu (jednotku měny č. 1), je možné postupným směňováním získat více korun?
- B2. Je dán text, který se skládá ze slov oddělených mezerami. Vypište všechna slova v pořadí podle jejich četností.
17. 6.
- A1. Vyslovte a dokažte větu o dolním odhadu časové složitosti třídění. Proč ji neporušuje přihrádkové třídění?
- A2. Popište Dijkstrův algoritmus pro nejkratší cesty. Na jaké grafy funguje?
- B1. Vymyslete algoritmus pro obarvení vrcholů rovinného grafu 6 barvami. Jde to v lineárním čase? A jak s 5 barvami?
- B2. Navrhněte datovou strukturu pro reprezentaci množiny prvků z lineárně uspořádáného universa, která bude umět v čase O(log N) operace Insert, Delete a spočítání prvků ležících v daném intervalu.
- C. Jak sestrojit ε-síť n-prvkové množiny X pro 0<ε<1 v čase O(n log(1/ε))? To je rostoucí posloupnost prvků vybraných z X taková, že mezi dvěma sousedními leží εn prvků z X (+/- konstanta). Například pro ε=1/2 posloupnost obsahuje minimum, medián a maximum.
24. 6.
- A1. Definujte komponenty silné souvislosti a popište algoritmus, který je nalezne.
- A2. Popište Euklidův algoritmus.
- B1. Mějme strom, jehož vrcholy jsou ohodnoceny celými čísly. Množinu vrcholů stromu nazveme nezávislou, pokud žádné dva její vrcholy nejsou spojeny hranou. Navrhněte algoritmus, který nalezne nezávislou množinu, jejíž součet ohodnocení je největší možný.
- B2. Je dána posloupnost x1,…,xn celých čísel a číslo S. Jak co nejefektivněji najít souvislý úsek xi,…,xj, jehož součet je roven S?
- C. Vymyslete datovou strukturu pro semipersistentní reprezentaci množiny. To je taková, která umí bězné operace Insert a Delete, ale hledat umí nejen v současném stavu množiny, nýbrž i v libovolném stavu v minulosti.
1. 7.
- A1. Popište QuickSort a rozeberte jeho časovou složitost v nejlepším, nejhorším a průměrném případě.
- A2. AVL stromy: definice, důkaz logaritmické hloubky a operace Insert nebo Delete.
- B1. Je dán ohodnocený neorientovaný graf a některé z jeho vrcholů jsou označeny. Jak najít minimální z těch koster, jejichž všechny označené vrcholy jsou listy?
- B2. Formátování odstavců. Mějme text složený ze slov, psaný písmem s pevnou šířkou znaku, a stránku známé šířky. Chceme rozdělit text na řádky a každý řádek roztáhnout na celou šířky stránky tím, že přidáme mezery mezi slova. Ošklivost řádku definujeme jako druhou mocninu počtu přidaných mezer, ošklivost odstavce je součet ošklivostí řádků. Vymyslete algoritmus, který najde nejhezčí (čili nejméně ošklivé) rozdělení na řádky.
- C. Variace na Hanojské věže: chceme přesunout věž z 1. trnu na 2. trn, ale je zakázáno přesouvat disky přímo mezi těmito dvěma trny (ať už kterýmkoliv směrem). Jde to? Kolik tahů je potřeba? Dokažte, že optimální postup navštíví všechna korektní rozmístění disků mezi trny.
2. 8.
- A1. Kruskalův algoritmus, jeho složitost a důkaz správnosti.
- A2. Popište přihrádkové třídění a ukažte, jak pomocí něj třídit N čísel v rozsahu 0...N3-1 v lineárním čase.
- B1. Mějme strom, jehož vrcholy jsou ohodnoceny celými čísly. Množinu vrcholů stromu nazveme nezávislou, pokud žádné dva její vrcholy nejsou spojeny hranou. Navrhněte algoritmus, který nalezne nezávislou množinu, jejíž součet ohodnocení je největší možný.
- B2. Hanojské věže. Přišli jsme k už rozehrané hře a chceme co nejméně korektními tahy hrací desku uklidit, tedy přenést všechny disky na jeden (libovolný) trn. Vymyslete algoritmus, který takovou minimální posloupnost tahů vypíše.
1. 9.
- A1. Nadefinujte topologické uspořádání, popište algoritmus pro jeho konstrukci. K čemu je dobré?
- A2. Popište QuickSort a rozeberte jeho časovou složitost v nejlepším, nejhorším a průměrném případě.
- B1. V místnosti je M tlačítek a N žárovek. Každé tlačítko má přiřazenu množinu žárovek, jejichž stav po stisknutí invertuje. Známe přiřazení žárovek tlačítkům a počáteční stav žárovek. Jak najít posloupnost stisků tlačítek, po jejímž provedení jsou všechny žárovky zhasnuté?
- B2. Vymyslete algoritmus, který pro zadaných N bodů v rovině nalezne kružnici, na které leží největší počet z těchto bodů.
- C. Nalezněte k-tý nejmenší z N prvků, máte-li k dispozici paměť asymptoticky menší než k. Pokuste se o lepší časovou složitost než Θ(kN). Můžete použít randomizaci.