1. V pseudo kode sme mali zadane:
Kód: Vybrat vše
MFF_SORT(A,i,j)
BEGIN
if A[i] >= A[j] then PREHOD(A[i],A[j])
if i+1 >= j then EXIT
k:= |_(j-i+1)/3_| ..................(pozn. |_dolna cela cast_|)
MFF_SORT(A,i,j-k)
MFF_SORT(A,i+k,j)
MFF_SORT(A,i,j-k)
END
2. Urcte asymptoticku zlozitost algoritmu v zavislosti od funkcie F, ktoru nejakym sposobom vyciciate z ULOHY C. 1 ...
(T.z. odvodit rekurentny vztah; horny a dolny odhad; dokazat)
3. (Toto si fakt pamatam len matne, takze ak tam niekto bol a zadanie si pamata presnejsie, nech ma opravi)
Mate nejaku stvorcovu tabulku PxP (mozno to bolo nieco ine ale v principe to bolo jedno). Na vstupe dostanete nahodne vygenerovane dvojice (x,y), pricom 0<x,y<=p. Dve dvojice su susediace, ak sa |x1-x2|<=1 a |y1-y2|<=1. Vymyslite algoritmus, ktory vrati TRUE ak sa v zozname nachadza aspon jedna susediaca dvojica, inak vrati FALSE. Ocakavana casova zlozitost algoritmu je LINEARNA. Mozete predpokladat ze kazda dvojica sa vyskytne najviac raz.
1. a 2. som zmakol... Tu trojku nemal nikto dobre, kedze to malo byt riesene hashovanim. Takze max. za tuto ulohu bol 1/2b, co sa mi podarilo aj pri nie tak korektnom rieseni...