Toto je stará verze stránky AlgoritmyADatovéStruktury/ZkouškaLS2007 z 2007-05-30 16:59:46..

Algoritmy a datové struktury — zkouška LS 2007

Skuska 30.5.2007
1.
MFFSORT(A,i,j)
{
if (A[i] > A[j]) swap (A[i], A[j]);
if (i + 1 < j)
{
k = spodna_cela_cast(j – i + 1);
MFFSORT(A, i, j – k);
MFFSORT(A, i + k, j);
MFFSORT(A, i, j – k);
}
}
Dokazte alebo vyvratte: alg. utriedi dane pole A

2.
Urcte zlozitost alg. z (1.)

3.
na vstupe [x_i, y_i],(i = 1..n) su bunky gridu p x p
2 bunky su susedne, ak |x_1 – x_2| <= 1 && |y_1 – y_2| <=1
Napiste alg, ktory uci v O(n) ci vstup obsahuje susedne bunky.
Mozte si alokovat pole velkosti O(n)

Tady u toho tretiho prikladu bylo v pohode pouzit hashovani podle obou souradnic (bez blizsiho urceni hashovaci funkce)
Pak uz staci pro kazdej prvek kouknout do hashovaci tabulky na jeho osm potencialnich sousedu jestli tam jsou.
KF

jinak po tehle pisemne casti nasledovala este ustni cast kde kazdemu zadal jiny problem

(ja jsem mel dokazat slozitost quicksortu v prumernem pripade a kdyz zjistil ze vubec netusim tak rek ze pisemec mam peknej tak at mu este reknu jak funguje floyd-warsall)
(dalsi lidi co tam byli se mnou meli povidat o hashovani, rict jak funguje a okecat dukaz strasena a neco s radixsortem, to sem moc nepobral o cem vsem mluvil)