Zkouska 4.6.2012, Cepek
Napsal: 5. 6. 2012 19:46
Pisemna cast:
1. Je dan vztah T(n) = 2T(n/2+1)+n2. Pro vhodne zvolene n0 plati, ze pro vsechna n mensi nez n0 T(n) = 1. Odhadnete funkci f, pro kterou plati T(n) = theta(f(n)) a svuj odhad dokazte substitucni metodou.
2. 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.
3. 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.
1. Je dan vztah T(n) = 2T(n/2+1)+n2. Pro vhodne zvolene n0 plati, ze pro vsechna n mensi nez n0 T(n) = 1. Odhadnete funkci f, pro kterou plati T(n) = theta(f(n)) a svuj odhad dokazte substitucni metodou.
2. 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.
3. 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.