Povodna sprava:

Datum a cas:   21-JAN-1997 13:38
Vec:           algoritmy 21.1.

1. klasika: max(f(n),g(n))=theta(f(n)+g(n))
                                 
2. Ukazte (pomocou substitucnej metody), ze riesenie T(n)=2T(n/2)+n je
omega(n.lg n). Mozno z toho urolbit zaver, ze riesenie je theta(n lgn)?

3. Kde v halde je najmensi prvok?

4. h(k)=k mod 9, kolizie zretazenim. Ukazte vkladanie klucov 5, 28,
19, 15, 20, 33, 12, 17, 10

5. Napiste NErekurzivnu proceduru pracujucu v case O(n), ktora pre
dany n uzlovy binarny strom vypise hodnotu kazdeho kluca (pouzit
zasobnik).

6. Bol nakresleny RB-strom. Ukazat postupne vymazavanie vsetkych
vrcholov v danom poradi.

7. Optimalne uzatvorkovanie sucinu matic...

8. Popiste datovu strukturu, ktora bude vbysledkom po absorbovani
cervenych deti do ich ciernych rodicov v RB-strome, pricom cierny
rodicia akceptuju za svoje: deti svojich cervenych deti (podla mojho
skromneho nazoru to bude B-strom).

9. Dokazte, ze pri optimalnom kode, ak su znaky usporiadane tak, ze
ich frekvencie su nerastuce, potom dlzky ich kodov su v nerastucom
poradi.

10. PREMIA priklady rekurencii:
a) T(n)=16T(n/4)+n^2
b) T(n)=7T(n/3)+n^2
c) T(n)=T(n-1)+n
d) T(n)=2T(sqrt(n))+1.

P.S.: radsej si nacvicte pracu s tymi ... RB-stromami, aby vas to
nezdrzovalo.