Zkouška - 13.12.2019 Hubička

1. Popsat Goldbergův algoritmus, správnost + časová složitost [10 bodů]

2. Navrhněte hradlovou síť, která porovná dvě n-bitová čísla. (log n) [5 bodů]

3. Navrhněte algoritmus, který pokruje šachovnici s dírami dominem (2x1), aby žádné domino nečouhalo ze šachovnice nebo z děr. (průvodce 329/4) [5 bodů]

(BONUS) 4. Navrhněte dynamickou datovou strukturu, která po změne jednotlivých znaků v textu řekne, jestli obsahuje jehlu.

1. Popísať Dinica - algoritmus, čas, pamäť, stačila mu intuícia

2. Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 2 P ? Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 4 NP ?

3. Nájsť v texte najdlhšie fibonacciho slovo

Bonusovku som ani nečítal, možno by mohol niekto doplniť.

Bonusovka byla pro obě skupiny zhruba stejná.