Toto je stará verze stránky AlgoritmyADatovéStruktury/ZkouškaLS2007 z 2007-05-31 10:51:11..

Algoritmy a datové struktury — zkouška LS 2007

Skuska 30.5.2007

písemná

Na písemnou je jedna hodina. Když odevzdáte dřív, můžete hned pokračovat ústní.

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); //Na tom threadu, co je na nej odkaz dole bylo spodna_cela_cast( (j – i + 1) / 3 ), tak predpokladam, ze to bylo i tady – Martin?
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

Přesně tak, je to stejné zadání, jako už kdysi bylo: http://forum.matfyz.info/viewtopic.php?p=1773 Kdybych si to byl zkusil vyřešit, mohl jsem to odevzdat ještě dřív:). — Adam

ústní

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)

Já měl popsat algoritmus hledání k-tého prvku, dokázat, že je Θ(n) a ještě chtěl substitucí určit přesně multiplikativní konstantu. — Adam