Mareš 25.5.18

Zkouška u Mareše.

1. násobení n-ciferných čísel rychleji než n^2

2. minimální kostra + důkaz správnosti

3. vymyslet algoritmus na mazání vrcholů v grafu, který zachovává souvislost (když algoritmu dáme souvislý graf a budeme mazat podle toho, co nám řekne, tak v každém kroku bude graf souvislý)

4. okénkový medián k prvků v nekonečné posloupnosti

5. a 2) jsou z přednášky, jenom pokud používáte kuchařku, tak ji vysvětlit

6. udělat z grafu kostru a mazat list po listu

7. držet si AVL strom s hodnotami, u každého vrcholu si pamatovat velikosti stromů na synech, pak jde přidávání, odebírání a hledání k/2-tého v O(log(k))

Zkouška byla fajn, když viděl správný nápad, tak se v tom nešťoural, jenom chtěl mít dobře důkaz správnosti a pořádně vysvětlené kroky (žádné "černá magie mi najde X")