Zkouškové otázky z Algoritmů a datových struktur I

Otázky An se týkají přednesené látky, Bn jsou příklady k vymyšlení, C je nepovinná úloha jen tak pro radost.

15. 5. odpoledne

A1. (a,b) stromy: definice, operace dle vlastního výběru
A2. Minimální kostry: algoritmus dle vlastního výběru
B1. Je dán slovník. Sestrojte co nejdelší slovní žebřík. To je posloupnost slov ze slovníku taková, že (i+1)-ní slovo získáme z i-tého smazáním jednoho písmene. Například pro anglický slovník AGID-4 vychází žebřík glassiness, glassines, glassine, glassie, lassie, lassi, lass, ass, as, a.
B2. Uvažujme posloupnost, která je setříděná až na K prvků, které jsou zatříděny chybně (knížky v knihovně hojně navštěvované čtenáři). Navrhněte co nejefektivnější algoritmus (vzhledem k počtu prvků a K), který posloupnost dotřídí.
C. Je dán binární strom a číslo K. Smažte co nejméně hran tak, aby jedna z komponent souvislosti měla právě K vrcholů.

A1. Algoritmus pro násobení čísel.
A2. Definujte výpočetní model RAM a naprogramujte v něm násobení matic.
B1. Je dán strom s celočíselně ohodnocenými vrcholy. Najděte nezávislou množinu vrcholů s největším možným součtem ohodnocení.
B2. Sestrojte datovou strukturu, která reprezentuje posloupnost a umí operaci "zjisti k-tý prvek v pořadí a přesuň ho za začátek".
C. Sestrojte datovou strukturu, která si pamatuje posloupnost N celých čísel a umí operace "změn prvek posloupnosti" a "najdi neprázdný úsek, jehož součet je dělitelný 17 (existuje-li)".

A1. Třídění sléváním.
A2. Algoritmus pro rozklad grafu na komponenty silné souvislosti.
B1. Je dán neorientovaný graf s hranami ohodnocenými čísly z množiny {1,…L} pro pevné, malé L. Najděte jeho minimální kostru.
B2. Uvažme všechny permutace na množině {1,…,N} uspořádané lexikograficky. Jak najít k-tou v pořadí?
C. Vymyslete pro předchozí úlohu jiné uspořádání, ve kterém půjde k-tou permutaci najít v čase O(N).

A1. Topologické uspořádání: definice, věta o existenci, algoritmus.
A2. Deterministický lineární algoritmus na nalezení k-tého nejmenšího prvku.
B1. Mějme neorientovaný graf, chceme najít všechny jeho artikulace (tak říkáme vrcholu, jehož odstraněním se zvýší počet komponent souvislosti).
B2. Je dána posloupnost celých čísel. Chceme v ní najít nejdelší vyvážený úsek, to jest takový, v němž je stejně kladných čísel jako záporných.
C. Dvojrozměrná verze předchozí úlohy (je dána matice, hledáme podmatici).

A1. Dijkstrův algoritmus.
A2. Dolní odhad složitosti třídění.
B1. Je dána posloupnost čísel a číslo K. Zjistěte mediány všech souvislých úseků délky K.
B2. Kdesi v bludišti se nachází robot. Vysíláme posloupnost příkazů (S/J/V/Z) pořád dokola, než robot vyleze z bludiště (pokud robot nemůže příkaz provést, protože by narazil do zdi, ignoruje ho). Zjistěte, zda pro danou mapu bludiště a danou posloupnost příkazů platí, že ať robot na počátku stojí kdekoliv, vždy je vysvobozen.
C. Je dán vyhledavací strom. Jak z něj udělat AVL strom v čase O(n) a prostoru lepším než Θ(n)?

A1. Kruskalův algoritmus.
A2. QuickSort.
B1. Konstrukce eulerovského tahu v grafu.
B2. Sestrojte vyhledávací strom, který bude navíc umět operaci Rank(x,y), která v logaritmickém čase spočte, kolik hodnot ve stromu leží v intervalu [x,y].
C. Stejná jako ráno.

A1. Kuchařková věta.
A2. Hledání mostů.
B1. Je dána posloupnost celých čísel a číslo x. Najděte dva (ne nutně různé) prvky posloupnosti tak, aby jejich součet byl roven x.
B2. Je dán neorientovaný graf ohodnocený kladnými celými čísly a jeho vrcholy x,y. Najděte tu z nejkratších cest z x do y, která navštíví nejvíce vrcholů.
C. Mějme posloupnost a₁,…a_n. Dírou v této posloupnosti nazveme dvojici (a_i, a_j) takovou, že a_i < a_j a žádné jiné a_k neleží mezi a_i a a_j. Rozdílu a_j - a_i budeme říkat velikost díry. Najděte v zadané posloupnosti největší díru. Dodejme, že to lze v lineárním čase.

A1. Topologické uspořádání grafu.
A2. Univerzální hešování.
B1. Vymyslete datovou strukturu, která si bude pamatovat množinu čísel a bude umět co nejrychleji vložit číslo do množiny, odstranit číslo z množiny a zjistit medián z čísel v množině. Dokažte, že vaše řešení je optimální.
B2. Bolek a Lolek zabloudili v tajuplném hradu a chtějí se vrátit domů. Hrad má tvar čtverečkového bludiště, na některých políčkách jsou navíc dveře a ovládací panely. Dveřmi může jedna z postav projít jen tehdy, když druhá stojí u příslušného ovládacího panelu. Vymyslete, jak oba dostat z bludiště ven.