Sent:	5. januára 2000 17:54
Subject:	DSA 5.1.2000

2h pisomka
Odporucam preratat si priklady z minulych rokov ...

1. Nech f(n) a g(n) su asymptoticky nezaporne fcie. Pomocou zakladnej
definicie
    Theta - notacie dokazte, ze
    max (f(n),g(n))= Theta (f(n)+g(n))

2. Najdite riesenie rekurentnej rovnice
    T(n) = 2T( sqrt(n)) + 1
    pouzitim zmeny premennej; netrap sa teraz tym, ci su argumenty cele
cisla

3. Ukazte, ze najvecsi prvok v podstrome haldy lezi v koreni tohto
podstromu.

4. Popis algoritmus, ktory ma na vstupe n celych cisel z intervalu <1..k>,
tieto cisla
    najprv predspracuje aby potom mohol odpovedat na lubovolnu otazku typu:
   "Kolko z n celych cisel padne do intervalu <a..b> ?" v case O(1). Tento
    algoritmus by mal fazu predspracovania spocitat v case O(n+k)

5. Ktore z nasledujucich triediacich algoritmov su stabilne: insertsort,
mergesort,
    heapsort, quicksort a countingsort ? Nacrtnite jednoduchy sposob, ako
urobit
    lubovolne triedenie stabilnym.

6. Nakresli postupnost medzivysledkov na ilustraciu operacie Quick-sort
    aplikovanej na pole.
    A=<5,3,17,10,84,19,6,22,9>.

7. Vyuzi vlastnost BP-stromu na rigorozny (presny) dokaz toho, ze kod
algoritmu
    Tree-Successor je spravny.

8. Nech R(i,j) je pocet odvolani sa na prvok m[i,j] algoritmom
    MATRIX-CHAIN-ORDER pri vypocte dalsich prvkov tabulky. Ukaz, ze
    celkovy pocet odvolani sa pre celu tabulku je
    n         n
   Suma  Suma  R(i,j) = (n^3-n) / 3
    i=1      j=1
                                    n
    Skus vyuzit identitu  Suma i^2 = n (n+1) (2n+1) / 6
                                    i=1

9. Zostrojte RB-strom, ktory bude vysledkom po postupnom vkladani klucov
   17,41,38,31,12,19,8,35,10 do povodneho prazdneho RB-stromu

10. Premia - Priklady Rekurencii
   Odvod asymptoticke horne a dolne ohranicenie pre T(n) v kazdej z
nasledujucich
   rekurentnych rovnic. Predpokladajme, ze T(n) je konstanta pre n<=2. Najdi
co
   najtesnejsie ohranicenia, a zdovodni tvoje 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

Tot vsjo, byeeeeeee
                                        Pichtik


Sent:	14. januára 2000 13:16
Subject:	algoritmy 14. 1. 19100

1. dokaz, ze pre lub. konstanty a, b, kde b>0, plati (n+a)^b=theta(n^b)

2. cas vypoctu je theta(g(n)) <-> najhorsi pripad je O(g(n)) a najlepsi
   OMEGA(g(n))

3. ukaz, ze heapsort je OMEGA(g(n))

4. cas vypoctu quicksort sa da vylepsit, ak netriedime podpolia mensie ako k
   a nakoniec pouzijeme insert sort. O(nk+log2(n/k)). dokaz a vyber vhodne k.
   (ja som si povedal T(n)=c1*nk+c2*n*log2(n/k) a minimum som nasiel derivaciou)

5. n-prvkova halde ma vysku (int) log2(n)

6. hashing zretazenim, h(k)=k mod m, m=2^p-1. k je retazec znakov pri zaklade
   2^p. dokaz, ze permutacie znakov k maju rovnaku h(k).
   (dokazete, ze h(k) je kongruentna so suctom znakov modulo 2^p-1. presne ako
   dokaz kriteria delitelnosti 9)

7. triedenie: vkladame postupne do stromu a nakoniec vypiseme cez inorder.
   najdi najlepsi a najhorsi pripad.

8. najdi optimalne ozatvorkovanie matic s rozmermi <5, 10, 3, 12, 5, 50, 6>
   (tieto priklady fakt preskakujte, trva to asi hodinu)

9. ukaz, ze greedy postup vyberania co najkratsich aktivit nie je optimalny.
   (napr. aktivity (0,5) (4,7) (6, 12))

10. utried kopu funkcii podla radu rastu. najzaujimavejsie boli podla mna
    (lg n)! a n^(1/lg n). ostatne boli v pohode.

m.