od Isidor » 26. 5. 2005 17:54
Juj, tak rad pisem reporty z uspesnych skusiek....
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...)
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...)