Pisemka 7.7. 2005

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.

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