# Mareš 25.5.18

<{ForumPost(poster="Trollwerine", timestamp=2018-05-26 17:06:21)}>
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  
  
1) a 2) jsou z přednášky, jenom pokud používáte kuchařku, tak ji vysvětlit  
3) udělat z grafu kostru a mazat list po listu   
4) 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")
<{/ForumPost}>