Datum a cas:   12-JAN-1998 10:48
Vec:           Algoritmy, 8.1.

Skuska z algoritmov vyzera nasledovne:
  1. pisomka - dve hodiny, 10 prikladov
  2. posle vas domov, uda termin vysledkov
  3. o jeden - dva dni su vysledky - posedenie u neho v kancelarii, vidite
     obodovanu pisomku, nestacite sa cudovat, kolko mate bodov (viac ako si
     myslite), kratky priatelsky rozhovor (od temy) a zapisana znamka.

A tu su zadania nasich uloh:
 1. Dokaz vetu: f(n) = theta(g(n)) <=> f(n) = O(g(n)) && f(n) = omega(g(n))
 2. Pouzi master theorem na T(n) = 4T(n/2) + n^3
 3. Dokaz, ze heapsort je omega(n lg n)
 4. Dokaz, ze counting-sort je stabilne triedenie.
 5. Implementuj dva zasobniky v jednom poli s casmi O(1)
 6. Uvazujme metodu delenia pri hasovani zretazenim, kde h(k) = k mod m,
    kde m=2^p-1 a k je znakovy retazec interpretovany v ciselnom zaklade 2^p.
    Ukaz, ze ak retazec x moze byt odvodeny z retazca y permutaciou jeho
    znakov, potom sa x a y hasuju na tu istu poziciu. Ukaz priklad aplikacie,
    kedy tato vlastnost hasovacej funkcie je nanajvys nevhodna.
 7. Casy vypoctu algoritmu, ktory cisla najskor insertuje do binarneho stromu a
    potom ich vypise v usporiadanom poradi (inorder) v najlepsom a najhorsom
    pripade.
 8. Dokaz, ze v matrix-chain-order algoritme je
     suma(i,j od 1 po n) R(i,j) = (n^3-n)/3
    vyuzitim suma(i od 1 po n) i^2 = n*(n+1)*(2n+1)/6
    R(i,j) je pocet odvolani sa na miesto tabulky (i,j)
 9. Nie kazdy greedy pristup k problemu vyberu aktivit nam dava najvacsiu
    mnozinu vzajomne kompatibilnych aktivit. Ukaz priklad, kedy vyber aktivit
    na zaklade najkratsieho trvania z tych, ktore su kompatibilne
    s predchadzajucimi nefunguje.
10. Najdi co najtesnejsie asymptoticke ohranicenia:
     T(n) = 7*T(n/2) + n^2
     T(n) = 2*T(n/4) + sqrt(n)
     T(n) = T(n-1) + lg n
     T(n) = sqrt(n)*T(sqrt(n)) + n