[home]

ADS I (2016/2017)

Cvičení k přednášce Algoritmy a datové struktury I

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (tj. za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna 5 body (tj. více aktivity na jednom cvičení je stále 5 bodů).

Body

Smazáno kvůli GDPR.

Úkoly

28.2. (do 21.3.)

• Nalezněte alespoň 5 asymptotických vztahů mezi těmito funkcemi: n, log n, log log n, sqrt(n), n^(log n), 2^n, n^(3/2), n!, n^n.
• Dokažte, že O(f(n) + g(n)) = O(max(f(n),g(n))).
• Dokažte, že n log n není v O(n).

7.3. (do 21.3.)

• Napište algoritmus, který pro zadané x a n spočítá x^n v čase O(log n). Algoritmus musí fungovat pro libovolné celé kladné n.
• Mějme konečnou množinu přirozených čísel a číslo x. Chceme zjistit, zda množina obsahuje dvojici prvků se součtem x. Vyřešte úkol v lepší složitosti než n^2.

14.3. - výuka odpadá

21.3. (do 4.4.)

• Máme dvě množiny přirozených čísel S = {s_1, ..., s_m} a T = {t_1, ..., t_n}. Navrhněte algoritmus, který zjistí, zda je S podmnožinou T. Řešte v lineárním čase.
• Uvažujte dvojité hešování (f(x) = (h(x) + i*g(x)) mod m) bez funkce Delete. Každá přihrádka j má navíc počítadlo c_j, které určuje počet prvků v tabulce, pro které platí h(x) = j. Jak toto počítadlo využít pro zrychlení neúspěšných vyhledávání v tabulce? Napište příklad, kdy je toto zrychlení veliké.

28.3. (do 11.4.)

• Ukažte správnost Strassenova násobení matic
• Napište odhad velikosti matice, pro které se vyplatí použít Strassenovo násobení matic místo počítání podle definice. Odhad můžete spočítat nebo algoritmy naprogramovat a prakticky vyzkoušet. Pro jednoduchost uvažujte pouze čtvercové matice.
• Master theorem: Rekurentní rovnice T(n) = a * T(n/b) + O(n^c), T(1) = 1 má pro konstanty a >= 1, b > 1 a c >= 0 řešení:
  • T(n)=O(n^c log n) pokud a/b^c = 1
  • T(n)=O(n^c) pokud a/b^c < 1
  • T(n)=O(n^(log_b a)) pokud a/b^c > 1
  Nalezněte algoritmus, který odpovídá druhému typu chování.

4.4. (do 18.4.)

• Je dáno n-prvkové pole, ve kterém jsou za sebou dvě vzestupně setříděné posloupnosti (ne nutně stejně dlouhé). Navrhněte algoritmus, který najde medián sjednocení obou posloupností v sublineárním čase. (Lze řešit v čase O(log n).)
• Na stole leží n různých šroubků a n matiček. Každá matička pasuje na právě jeden šroub a my chceme zjistit, která na který. Umíme ale pouze porovnávat šroub s matičkou – tím získáme jeden ze tří možných výsledků: matička je příliš velká, příliš malá, nebo správně velká. Nalezněte co nejefektivnější algoritmus (tj. lépe než v n^2).
• Uvažujte následující Bubble Sort. Na jakých datech provede Bubblesort pouze jeden průchod? Na jakých právě dva průchody? Kolik přesně průchodů vykoná nad sestupně uspořádaným vstupem?

11.4. (do 25.4.)

• Jsou dány rovnoramenné váhy a n kuliček, z nichž právě jedna je těžší než ostatní. Na misku lze dát i více kuliček naráz. Navrhněte algoritmus používající co nejmenší počet vážení. Dokažte, že tento počet je optimální.
• Na jisté šachovnici žil kulhavý kůň. To je zvláštní šachová figurka, která v sudých tazích táhne jako jezdec, v lichých jako pěšec. Vymyslete algoritmus, který z jednoho zadaného políčka dokulhá na druhé na nejmenší možný počet tahů.
• Mějme mapu Manhattanu: čtverečkovaný papír, křížení čar odpovídají křižovatkám, úsečky mezi nimi jednotlivým streets a avenues, z nichž některé jsou neprůjezdné kvůli dopravní zácpě. Zrovna se nám v jedné ulici porouchalo auto a nyní dovede pouze jezdit rovně a odbočovat doprava. Nalezněte nejkratší cestu do servisu (na zadanou křižovatku).

18.4. (do 2.5.)

• Vyberte si libovolný úkol z kapitoly 1.11 ze skript (strana 28-30).

25.4. (do 9.5.)

• Vyberte si libovolný (jiný než předchozí) úkol z kapitoly 1.11 ze skript (strana 28-30).
• O orientovaném grafu řekneme, že je polosouvislý, pokud mezi každými dvěma vrcholy vede orientovaná cesta alespoň jedním směrem. Navrhněte lineární algoritmus, který polosouvislost grafu rozhoduje.

2.5. (do 16.5.)

• Nechť délky hran leží v množině {0, . . . , L}. Navrhněte datovou strukturu založenou na přihrádkách, s níž Dijkstrův algoritmus poběží v čase O(nL + m). Pokuste se vystačit s pamětí O(n + m + L).
• Upravte Bellmanův-Fordův algoritmus, aby uměl detekovat záporný cyklus dosažitelný z vrcholu v_0. Uměli byste tento cyklus vypsat?
• Dokažte, že v grafu bez záporných cyklů se obecný relaxační algoritmus zastaví, ať už vrchol k uzavření vybíráme libovolně.

9.5. (do 23.5.)

• Směnárna obchoduje s n měnami (měna číslo 1 je koruna) a vyhlašuje matici kurzů K. Kurz K_ij říká, kolik za jednu jednotku i-té měny dostaneme jednotek j-té měny. Vymyslete algoritmus, který zjistí, zda existuje posloupnost směn, která začne s jednou korunou a skončí s více korunami.
• Vymyslete algoritmus, který nalezne všechny hrany, jež leží na alespoň jedné nejkratší cestě.
• Kritická hrana budiž taková, která leží na všech nejkratších cestách. Tedy ta, jejíž prodloužení by ovlivnilo vzdálenost. Navrhněte algoritmus, který najde všechny kritické hrany.
• Silnice v mapě máme ohodnocené dvěma čísly: délkou a mýtem (poplatkem za projetí). Jak najít nejlevnější z nejkratších cest?

16.5. (do 30.5.)

• Navrhněte algoritmus, který v lineárním čase zadaný BVS dokonale vyváží. Na cvičení jsme nalezli algoritmus, který to zvládne v čase O(n) a pamětí O(n). Nalezněte algoritmus, který bude v čase stále lineární, ale (kromě zadaného stromu) bude potřebovat pouze O(log(n)) paměti navíc.
• Obvyklá reprezentace BVS v paměti potřebuje v každém vrcholu 3 ukazatele: na levého syna, na pravého syna a na otce. Ukažte, jak si vystačit se dvěma ukazateli. Původní 3 ukazatele by z těch vašich mělo jít spočítat v konstantním čase.

23.5. (do neomezeně)

• Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních k čísel. Dosáhněte časové složitosti O(log k) na operaci. Dokažte, že čas Θ(log k) je nejlepší možný, pokud umíme čísla pouze porovnávat.
• Navrhněte operaci Join(X, Y ), která dostane dva (a, b)-stromy X a Y a sloučí je do jednoho. Může se přitom spolehnout na to, že všechny klíče z X jsou menší než všechny z Y. Zkuste dosáhnout složitosti O(log |X| + log |Y |).