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.

22. 5. odpoledne

A1. Topologické uspořádání: definice, vlastnosti, algoritmus.
A2. AVL stromy: definice, hloubka, Insert.
B1. Je dána posloupnost celých čísel a₁,…a_n a číslo x. Hledáme i, j takové, že a_i + a_j = x.
B2. Je dán neorientovaný graf. Jak ho nakreslit co nejmenším počtem tahů?
C. Upravte definici (a,b)-stromů a operace s nimi tak, aby každý vrchol byl zaplněn alespoň ze 2/3.

A1. Minimální kostra: definice, libovolný efektivní algoritmus.
A2. Dolní odhad složitosti třídění.
B1. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšeme minimum z posledních K čísel.
B2. Mějme orientovaný graf s celočíselně ohodnocenými hranami. Sled nazveme k-hladký, pokud se ohodnocení každých dvou na sebe navazujících hran liší nejvýše o k. Navrhněte algoritmus, který nalezne 3-hladký sled o co nejméně hranách mezi zadanými dvěma vrcholy.
C. Vyřešte úlohu B1 v čase O(1) na operaci.

A1. Dijkstrův algoritmus.
A2. Kuchařková věta o rekurencích.
B1. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšeme medián z posledních K čísel.
B2. Mějme plán městečka ve tvaru stromu. Hrany jsou ulice, vrcholy křižovatky. Na křižovatku lze umístit strážníka, ten pak hlídá všechny ulice sousedící s křižovatkou. Strážníkovi ovšem musíme zaplatit, mezi křižovatkami se liší, kolik. Vymyslete, jak co nejlevněji rozmístit strážníky tak, aby všechny ulice byly hlídané.
C. Dokažte, že vaše řešení úlohy B1 je v porovnávacím modelu optimální.

A1. QuickSort: formulace, složitost v nejlepším, nejhorším a průměrném případě
A2. Komponenty silné souvislosti: definice, algoritmus na jejich hledání
B1. Je dána permutace π na množině {1,…n}. Najděte nejmenší k>0 takové, že π^k je identita.
B2. Mějme posloupnost prvků, jejímž setříděním se každý prvek pohne o nejvýše d≪n pozic. Jaký třídicí algoritmus se pro takové posloupnosti hodí?

A1. (a,b)-stromy: definice, hloubka, Insert nebo Delete
A2. Hledání mostů
B1. Mějme posloupnost n prvků, která obsahuje pouze k≪n různých hodnot. Jak ji co nejrychleji setřídit?
B2. Je dán neorientovaný graf. Jak jeho hrany pokrýt disjunktními cestami délky 2?
C. Odmocninou z permutace π na množině {1,…,n} nazveme permutaci σ takovou, že σ∘σ=π. Jak zadanou permutaci efektivně odmocnit (případně poznat, že to nejde)?

A1. Minimální kostra: definice, libovolný efektivní algoritmus.
A2. Universální hešování.
B1. Je dán strom s hranami ohodnocenými přirozenými čísly. Spočítejte jeho průměr, tedy délku nejdelší cesty.
B2. Mějme matici A přirozených čísel, která v každém řádku i sloupci ostře roste. Chceme zjistit, zda existují indexy i,j takové, že A[i,j] = i+j.
C. Vymyslete program pro RAM, který v konstantním čase zjistí, zde dané celé kladné číslo je mocnina dvojky.

A1. Topologické uspořádání: definice, vlastnosti, algoritmus.
A2. Hledání k-tého nejmenšího prvku.
B1. Mějme souvislý neorientovaný graf. Chceme najít pořadí mazání vrcholů takové, aby graf stále zůstával souvislý.
B2. 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.

A1. Random access machine: definice stroje a složitosti.
A2. AVL stromy: definice, hloubka, Insert nebo Delete.
B1. Nalezněte ve stromu největší párování.
B2. Je dána posloupnost celých čísel. Najděte nejdelší úsek, ve kterém se neopakují hodnoty.
C. Mějme množinu celých čísel. Díra budeme říkat dvojici prvků množiny, mezi nimiž neleží žádný další prvek. Jak najit největší díru v lineárním čas?

A2. Kuchařková věta o rekurencích.
A1. Dijkstrův algoritmus.
B1. Barevení rovinného grafu 6 barvami.
B2. Je dána posloupnost celých čísel. Úsek je vyvážený, pokud se v něm vyskytuje stejný počet kladných hodnot, jako záporných. Najděte co nejdelší vyvážený úsek.
C. Jako B1, ale 5 barvami.

A1. Algoritmus pro násobení čísel.
A2. Dolní odhad složitosti třídění.
B1. Je dán multigraf, odstraňte z něj násobné hrany.
B2. 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ě.

A1. QuickSort: formulace, složitost v nejlepším, nejhorším a průměrném případě
A2. Komponenty silné souvislosti: definice, algoritmus na jejich hledání
B1. Inverze v číselné posloupnosti x₁, …, x_n je taková dvojice indexů (i,j), pro kterou platí i<j a současně x_i > x_j. Vymyslete algoritmus, který co nejefektivněji spočte, kolik je v posloupnosti inverzí. Můžete předpokládat, že posloupnost je permutací na množině {1,…n}.
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.

A1. AVL stromy: definice, hloubka, Insert nebo Delete.
A2. Dolní odhad složitosti třídění.
B1. Je dán neorientovaný graf, otestujte, zda je bipartitní.
B2. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypište minimum z posledních K čísel.

A1. (a,b)-stromy: definice, hloubka, Insert nebo Delete
A2. Hledání mostů
B1. Je dána posloupnost délky N, v níž se nachází pouze K různých hodnot, přičemž K je mnohem menší než N. Vymyslete co nejefektivnější algoritmus, který takovou posloupnost setřídí.
B2. Je dán neorientovaný graf. Jeho hrany chceme rozložit na disjunktní cesty délky 2.