Pisemna cast:
Je dan vztah T(n) = 2T(n/2+1)+n<sup>2</sup>. Pro vhodne zvolene n<sub>0</sub> plati, ze pro vsechna n mensi nez n<sub>0</sub> T(n) = 1. Odhadnete funkci f, pro kterou plati T(n) = theta(f(n)) a svuj odhad dokazte substitucni metodou.
Popiste a napiste v "Pascalu" algoritmus, ktery na vstupu dostane dve setrizene posloupnosti X a Y (kazda z nich ma delku N) a ma v case O(log N) najit jeden z medianu vsech 2N cisel z X i Y.
Vymyslete algoritmus na nasobeni matic velikosti n x kn a kn x n, ktery pouziva jako podprogram Strassenuv algoritmus. Pro obe mozna poradi soucinu zjistete casovou slozitost a porovnejte ji se slozitosti klasickeho nasobiciho algoritmu.
U ustni casti jsem mel definici AVL stromu, dukaz jeho logaritmicke vysky a diskuzi o Kruskalovu algoritmu na hledani minimalni kostry grafu a jeho casove slozitosti.