# Skuska 14.6.05

<{ForumPost(poster="qwyxyo", timestamp=2005-06-14 16:34:49)}>
No tak dnes bola pisomka z ineho sudka ako zvycajne. Pamatam si prvu ulohu (kedze som si ju opisal), ale 2. a 3. bude vymykat originalu:)  
  
1. V pseudo kode sme mali zadane:  
   

       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
    

  Rozhodnite ci dany algoritmus utriedi lubovolne vstupne n-prvkove pole     A a svoje rozhodnutie zdovodnite resp. dokazte...  
  
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...
<{/ForumPost}>

<{ForumPost(poster="tuxo", timestamp=2005-06-14 21:30:12)}>
hm a riesenie aspon nejak 1 a 2 ?
<{/ForumPost}>

<{ForumPost(poster="qwyxyo", timestamp=2005-06-15 01:28:08)}>

 > tuxo wrote:hm a riesenie aspon nejak 1 a 2 ?

1.   
indukcia: ukazes ze 1,2,3prvkove pole to zotriedi. Predpokladas, ze plati pre 1,2,3...(n-1) a ukazes, ze plati aj pre n. Ked sa na to pozries poriadne tak si uvedomis (teda aspon by si si mal:)), ze tie 3 rekurzivne volania su vlastne volania na n prvkove pole take (nezalezi, aky interval sa vola), ze sa zoradi najprv pole o velkosti 2n/3 od zaciatku, potom rovnako velke pole, ale od n/3 po koniec a do tretice opat to od zaciatku... V predpoklade mas, ze tieto polia sa zotriedia. Takze jedine, co musis ukazat je, ze ked vezmes prve dve tretiny a zotriedis, a potom posledne dve tretiny a zotriedis a opat prve dve tretiny, tak ze cele pole bude zotriedene. To urobis velmi lahko sporom. To uz je fakt trivialne. Ale malo by sa to ukazat. Ved dokaz je dokaz:)  
  
2.  
Toto sa da vidiet priamo z algoritmu. Takze riesenie 1 nemalo vplyv na riesenie 2.  
  
Ako som spominal v 1, tak triedis polia o velkosti 2n/3 a toto zavolas 3x, pricom v tej procedure iba porovnavas, priradujes, a scitavas, co sa ti podari v konstantom case....  
  
Takze z toho ti moze vyjst uz len:  T(n) = 3T(2n/3) + theta(1)  
  
Ak to hodis do master theorem, tak ti z toho vyjde, ze to bezi pri casovej zlozitosti theta( n^(log pri zaklade 3/2 z 3) ~ 2.7-8 )  
  
Dufam, ze to ti bude stacit:)....
<{/ForumPost}>