Povodna sprava:

Datum a cas:    4-JAN-1997 10:06
Vec:           Algoritmy - skuska 3.1.

Ahojte,

na prosbu viacerych z Vas pisem znenie zadani skusky z algoritmov (v zatvorke
za priklodom je vzdy pocet bodov zan).
Nebolo to az take tazke tazke, ale casovo pomerne narocne, tak sa na to
pripravte. Napriklad pri siestich maticiach je MATRIX-CHAIN v case O(n^3)...
Takze tak:

1. Nech f(n), g(n) su asymptoticky nezaporne fcie. Pomocou zakladnej definicie
theta-notacie dokazte, ze
				max{f(n),g(n)} = theta(f(n)+g(N))         (8)

2. Pouzite metodu master theorem (hlavna veta) na zistenie tesnych
asymptotickych ohraniceni pre rekurenciu
						T(N) = 4 T(n/2) + n^2    (10)

3. Ukazte, ze cas vypoctu algoritmu HEAPIFY je v nojhorsom pripade
omega(lg n). (Pomoc: Pre haldu s n uzlami zadaj take hodnoty uzlov, ktore
sposobia, ze HEAPIFY bude volane rekurzivne v kazdom uzle na ceste od korena
k listu.)                                                                (10)

4. Cas vypoctu algoritmu quicksort je mozne v praxi vylepsit, ak vezmeme
do uvahy, ze insertsort triedi velmi rychlo postupnosti, ktore su uz "skoro"
utriedene. Ak volame quicksort na podpoli s mensim poctom prvkov nez k prvkov,
tak ich nechame nezmenene a vratime sa bez triedenia. Ked skonci praca alg.
quicksort, tak spustime alg. insertsort na ukoncenie triedenia. Zdovodnite, ze
ocakavany cas vypoctu tohto triediaceho algoritmu je O(nk + n log(n/k)).
Ako vybrat vhodne k teoreticky a prakticky?                              (10)

5. Nech a=<a0,a1,...,ar> oznacuje postupnost r+1 prvkov vybratych nahodne
z mnoziny {0,1,...,m-1}. Definujme prislusnu hasovaciu funkciu ha z H

	ha(x) = suma od i=0 po r ( ai*xi) mod m			(*)

kde x=<x0,x1,...,xr> je rozpis x do r+1 bitovych retazcov rovnakej dlzky.
Ukazte, ze ak bude kazda zlozka ai z a v rovnici (*) rozna od nuly, potom
mnozina H z definicie
			H = zjednotenie cez a ({ha})
nie je univerzalna.                                                      (12)

6. Prehladavanie BP-stromu metodou INORDER mozno vykonat tak, ze najdeme
minimalny prvok pomocou algoritmu TREE-MINIMUM a potom pouzitim n-1 volani
algoritmu TREE-SUCCESSOR. Dokazte, ze tento algoritmus bezi v case theta(n).
                                                                          (9)

7. Najdite optimalne uzatvorkovanie sucinu maticoveho retazca, ktoreho
postupnost rozmerov je <15,12,40,25,7,30,10>.                            (10)

8. Dokazte, ze zlomkovy problem batohu ma vlastnost greedy vyberu.        (8)

9. Zostrojte RB-strom, ktory bude vysledkom po postupnom vkladani klucov
87,93,58,129,27,81,138,72 do povodne prazdneho RB-stromu.                (10)

10. PREMIA - PRIKLADY REKURENCII

Odvodte asymptoticky horne a dolne ohranicenia pre T(n) v kazdej
z nasledujucich rekurentnych rovnic. Predpokladajme, ze T(n) je konstanta
pre n<=2. Najdite co najtesnejsie ohranicenia a zdovodnite vase riesenie:

a)   T(n) = 7 T(n/2) + n^2
b)   T(n) = 2 T(n/4) + sqrt(n)
c)   T(n) = T(n-1) + lg n
d)   T(n) = sqrt(n) * T(sqrt(n)) + n                                     (13)



Tot' vsjo. Majte sa. Ivona