# Pisemka 7.7. 2005

<{ForumPost(poster="Kaja Marik", timestamp=2005-07-08 12:56:27)}>
Opet 3 priklady, citelnost dobra.  
  
1) Odhadnete slozitost a dukaz provedte substitucni metodou  
  
T(n)=2* T(2/3*n) +T(n/3) + 8  
  
2) Vymyslete algoritmus, ktery v case O(n) najde K prvku nejblize medianu. Na vstupu dostanete tedy mnozinu cisel a cislo K, kde K<N. Jo a v tej mnozine nenajdete 2 stejny prvky.  
  
3) Tak ten uz si nepomatuju, ale zacinalo to Dokazte nebo vyvratte a jednalo se o tvrzeni s lehkyma hranama. Dyztak at me nekdo s lepsi pameti doplni.  
  
  
Hodne stesti.
<{/ForumPost}>

<{ForumPost(poster="Mirek", timestamp=2005-07-08 23:08:36)}>
já si to pamatuju takto:  
3) Dokažte nebo vyvraťte že to, že všechny řezy v grafu mají právě jednu lehkou hranu, je postačující,ale nikoliv nutná podmínka k tomu,aby graf měl právě jednu minimální kostru
<{/ForumPost}>