Zkouškové otázky z Algoritmů a datových struktur I
23. 5. (předtermín)
- Formulujte Mergesort a analyzujte jeho složitost.
- Definujte komponenty silné souvislosti orientovaného grafu. Popište a analyzujte algoritmus na jejich nalezení.
- Čtverečkovou sítí s překážkami stěhujeme gauč tvaru "L" ze tří políček. Najděte cestu na co nejméně kroků (posun o 1 políčko, případně otočení na volném čtverci 2×2 pole).
- 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.
27. 5. dopoledne
- Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
- Formulujte a dokažte Kuchařkovou větu o rekurencích.
- Je dáno čtverečkové bludiště. Najděte cestu ze startu do cíle, která projde co nejméně zdmi.
- Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, který obsahuje stejný počet kladných čísel jako záporných.
27. 5. odpoledne
- Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
- Definujte AVL strom a popište operaci Insert.
- Je dán neorientovaný graf. Zjistěte, zda je bipartitní.
- 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í. Můžete předpokládat, že posloupnost je permutací na množině {1,…n}.
29. 5. dopoledne
- Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
- Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
- Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
- Je dána posloupnost přirozených čísel. Spočítejte, kolik má vybraných podposloupností, jejichž součet je dělitelný 7.
29. 5. odpoledne
- Definujte (a,b)-strom a dokažte lemma o jeho hloubce.
- Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
- Je dána posloupnost celých čísel a číslo S. Najděte trojici (ne nutně různých) prvků posloupnosti, jejichž součet je roven S.
- Je dána nějaká permutace π, která propojuje n levých konců kabelů s n pravými. Chceme tuto permutaci najít pomocí co nejmenšího počtu operací "nastav i-tý levý konec na hodnotu 0 nebo 1" a "zjisti hodnotu na j-tém pravém konci".
3. 6. dopoledne
- Popište a analyzujte Floydův-Warshallův algoritmus na výpočet matice vzdáleností.
- Definujte (a,b)-strom a popište operaci Insert.
- Na vstupu je posloupnost znaků. Spočítejte, kolikrát se v něm vyskytuje
vybraná podposloupnost
KOCKA
. - Je dán strom, jehož vrcholy jsou ohodnocené celočíselnými cenami. Najděte co nejlevnější podmnožinu vrcholů, která protíná každou hranu.
3. 6. odpoledne
- Popište a analyzujte algoritmus pro hledání mostů v neorientovaných grafech.
- Formulujte a dokažte Kuchařkovou větu o rekurencích.
- Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšte medián z posledních K čísel.
- Je dán neorientovaný graf. Jak množinu jeho hran rozložit na hranově disjunktní cesty délky 2? (Tedy tak, aby každá hrana ležela v právě jedné cestě.) Pokud si nevíte rady s obecným grafem, zkuste to nejdřív pro strom.
5. 6. odpoledne
- Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
- Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
- Je dána posloupnost čísel x1, …, xn a číslo s. Spočítejte, kolik existuje dvojic indexů (i,j) takových, že xi + xj = s.
- Je dán orientovaný graf s určeným počátečním a cílovým vrcholem, v některých vrcholech se prodává zmrzlina. Najděte sled z počátečního do koncového vrcholu, který navštíví co nejvíce různých vrcholů se zmrzlinou.
11. 6. dopoledne
- Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
- Definujte AVL strom a popište operaci Insert.
- Lagrangeova věta říka, že každé přirozené číslo x jde rozložit na součet čtyř čtverců (druhých mocnin celých čísel). Navrhněte algoritmus, který pro všechna x=1,…,n tyto rozklady najde.
- Je dán neorientovaný graf s hranami ohodnocenými čísly z množiny {1,…,5}. Najděte jeho minimální kostru.
11. 6. odpoledne
- Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
- Definujte c-univerzální systém hešovacích funkcí. Ukažte, jak ho použít. Předveďte konstrukci nějakého takového systému.
- 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í.
- Mějme orientovaný graf, jehož hrany jsou ohodnocené pravděpodobnostmi. Najděte nejpravděpodobnější cestu mezi dvěma vrcholy, tj. takovou, na níž je součin pravděpodobností hran největší možný.
19. 6. odpoledne
- Popište a analyzujte datovou strukturu Union-Find.
- Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
- Hledáme nejkratší cestu čtverečkovým bludištěm, která se vyhne strážím. Každá stráž chodí po cyklu délky nejvýše 10.
- Vymyslete co nejefektivnější algoritmus pro K-cestné slévání: slití K setříděných posloupností o celkové délce N. Jak se změní časová složitost Mergesortu, když budeme dělit na K částí a slévat K-cestně?