# Zk 26.5.

<{ForumPost(poster="Isidor", timestamp=2005-05-26 17:54:30)}>
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...)
<{/ForumPost}>

<{ForumPost(poster="Peter", timestamp=2005-09-11 21:20:41)}>

 > 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
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-05-29 21:21:52)}>
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](http://www.cse.nd.edu/courses/cse60111/www/sol3.pdf)  
  
ci v PostScriptu: [http://www.cse.nd.edu/courses/cse60111/www/sol3.ps](http://www.cse.nd.edu/courses/cse60111/www/sol3.ps)
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-05-29 21:46:29)}>

 > 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](http://www.cs.pdx.edu/~maier/cs584/Assignments/hw04-06sol.pdf)  
  
kn x kn lze pomoci k^2 strassenu -> O(k^2*n^log_2(7))  
reverzni: n x n lze pomoci k strassenu -> O(k*log_2(7))
<{/ForumPost}>