Zk 26.5.

Juj, tak rad pisem reporty z uspesnych skusiek.... :P

Pisomka:

1. Pre rekurentnu rovnicu T(n) = 2*T(n/2 + 1) + n^2 odhadnite f(n), pre ktoru T(n) je "velke theta" od f(n) a dokazte substitucnou metodou (horny aj dolny odhad of course...)

2. Navrhnite algoritmus, ktory z dvoch zotriedenych poli dlzky n najde spolocny median (t.j. median vsetkych 2n prvkov) v case O(log n), samozrejme zdovodnite, a pripadne napiste zodpovedajuci program v niecom Pascal/C-like (nemal som, ale nevadilo).

3. Za predpokladu vyuzitia Strassenovho alg. nasobenia matic vysvetlite, v akom case je mozne vynasobit dve matice velkosti (n x kn) a (kn x n), oboma sposobmi (t.j. vysledok (n x n) aj (kn x kn)) a porovnajte so zlozitostou pri klasickom nasobeni.

2 hod casu, spolu 3 body. Pri odovzdavani kazdy dostal termin, kedy sa tam ma zjavit, po kratkej konzultacii pisomky bola pridelena jedna teoreticka tema, typicky napr. Bellman-Ford, Dijkstra, AVL stromceky, hladanie k-teho prvku atd., citujem "Jak to funguje, proc to funguje a v jakem case..." :) Cepek sa dost vypytoval, ked si chcel overit ci clovek rozumie tomu co pise, ale zas nic hrozostrasne...

Inak s 1,5 bodom z pisomky sa pri ustnej este dalo bojovat o trojku (ak clovek chcel...)

Isidor wrote:Juj, tak rad pisem reporty z uspesnych skusiek.... :P

2. Navrhnite algoritmus, ktory z dvoch zotriedenych poli dlzky n najde spolocny median (t.j. median vsetkych 2n prvkov) v case O(log n), samozrejme zdovodnite, a pripadne napiste zodpovedajuci program v niecom Pascal/C-like (nemal som, ale nevadilo).

Davam tento algoritmus k pripominkam:

Znaceni A- prvni pole, B- druhe pole, Ma- median pole A, Mb-median pole B.
Ma=A[n/2];
Mb=B[n/2];

1. vyhledam v poli A imaginarni pozici Mb (pole jej nemusi obsahovat) O(log n)
   vyhledam v poli B imaginarni pozici Ma O(log n)

2. pulenim intervalu v obou polich mezi Mb a Ma naleznu median
   o vezmu prvek z A mezi Mb a Ma, oznacim jej x
   o vezmu prvek z B mezi Mb a Ma, oznacim jej y
   o porovnam x a y, napr x<y
   o v poli A budu hledat v horni polovine intervalu Mb, Ma
   o v poli B budu hledat v dolni polovine intervalu Mb, Ma

3. algoritmus konci pokud je velikost intervalu 1

Jedna se o ulohu 9.3-8 (str. 193) z Introduction to Algorithms

Reseni je krasne popsano zde (posledni dve stranky):

http://www.cse.nd.edu/courses/cse60111/www/sol3.pdf

ci v PostScriptu: http://www.cse.nd.edu/courses/cse60111/www/sol3.ps

3. Za predpokladu vyuzitia Strassenovho alg. nasobenia matic vysvetlite, v akom case je mozne vynasobit dve matice velkosti (n x kn) a (kn x n), oboma sposobmi (t.j. vysledok (n x n) aj (kn x kn)) a porovnajte so zlozitostou pri klasickom nasobeni.

cviceni 28.2-5:

http://www.cs.pdx.edu/~maier/cs584/Assi ... -06sol.pdf

kn x kn lze pomoci k^2 strassenu -> O(k^2n^log_2(7))
reverzni: n x n lze pomoci k strassenu -> O(klog_2(7))