1. (Ruční třídění karet)
    Dostanete balíček zamíchaných karet. Jakým způsobem ho setřídíte? Dokážete něco říci o tomto algoritmu? Jakou bude mít časovou složitost? Jaké budou jeho nároky na prostor (paměť)?

  2. (Hledání pevného bodu zobrazení)
    Dostaneme setříděné pole různých čísel $\ARRAY{A}{1,\dots, n}$. Chceme zjistit, jestli existuje index $i$, pro který $\ARRAY{A}{i}=i$. Pomocí metody rozděl a panuj navrhněte algoritmus běžící v čase $\OO(\log n)$.

  3. (Většinový prvek)
    Dostaneme pole $n$ prvků $\ARRAY{A}{1,\dots, n}$. Prvky nemusíme nutně umět porovnávat,1 ale pro každé dva indexy $i$, $j$ umíme zjistit, jestli $\ARRAY{A}{i}=\ARRAY{A}{j}$. Prvek má v poli většinu, pokud se vyskytuje na více než polovině políček. Navrhněte algoritmus, který zjistí, jestli pole obsahuje prvek mající většinu a případně ho vypíše.

    1. Ukažte, jak vyřešit tento problém v čase $\OO(n\log n)$.

      Nápověda: Rozdělte pole na dvě pole poloviční velikosti a zkuste v nich najít prvek mající většinu.

    2. Najděte algoritmus běžící v lineálním čase.

      Nápověda: Prvky libovolně spárujte. Dostanete $n/2$ párů. Pro každý pár zjistěte, jestli jsou prvky stejné. Pokud ano, tak nechte jeden z nich a druhý prvek smažte. Pokud jsou prvky různé, tak smažte oba. Takto získáme nejvýše $n/2$ prvků. Ukažte, že nově získané prvky mají většinový prvek právě tehdy, když ho má i původních $n$ prvků.

  4. (Házení vajíčka z mrakodrapu)
    Na návštěvě Singapuru jste dostali jako dárek na uvítanou “nerozbitelné vajíčko”. Tvrdí Vám, že je vyrobeno nejmodernější technologií a i když má jen tuhou skořápku, tak prý nejde rozbít. Rozhodnete se to vyzkoušet a proto budete vajíčko házet z mrakodrapu na chodník.2

    Mrakodrap má $n$ pater. Jaké je nejnižší patro, ze kterého už se vajíčko rozbije? (Klidně se může stát, že se vajíčko nerozbije ani z $n$-ého patra.) Kolik nejméně pokusů budete muset provést, aby jste to zjistili? Pokusem myslíme jedno hození vajíčka na chodník.

    1. Máte jen jedno vajíčko.
    2. A co když budete mít dvě, naprosto stejná vajíčka?
    3. Jak to zobecnit pro $k$ vajíček?

    Nejprve zkuste najít co nejlepší horní odhad na počet pokusů. Teprve pak se zamyslete nad tím, jak dokázat, že to lépe nejde.

    Nápověda: Formulka pro počet pokusů není jednoduchá. Stačí, když ukážete, jak spočítat počet pokusů pro $n$-patrový mrakodrap například na počítači.

  5. (Procvičení řešení rekurencí)
    Vyřešte následující rekurence. Řešení určete s přesností $\Theta$-notace.

    1. $T(n)=2T(n/3)+1$
    2. $T(n)=5T(n/4)+n$
    3. $T(n)=7T(n/7)+n$
    4. $T(n)=9T(n/3)+n^2$
    5. $T(n)=8T(n/2)+n^3$
    6. $T(n)=49T(n/25)+n^{3/2}\log n$
    7. $T(n)=2T(n/2)+n/\log n$
    8. $T(n)=16T(n/4)+n!$
    9. $T(n)=T(n-1)+2$
    10. $T(n)=T(n-1)+n^c$, kde $c\geq 1$ je konstanta
    11. $T(n)=T(n-1)+c^n$, kde $c > 1$ je konstanta
    12. $T(n)=2T(n-1)+1$
    13. $T(n)=T(\sqrt{n})+1$
    14. $T(n)=\sqrt{n}T(\sqrt{n})+1$

    Nápověda: (k předposlední rekurenci) Zkuste použít substituci $S(m)=T(2^m)$. Substituce je korektní, protože $2^m$ je rostoucí funkce.