# 15.5.2013 Mareš

<{ForumPost(poster="unicorns", timestamp=2013-05-16 11:21:06)}>
1) (a-b)-tree: definice, insert/delete, časové složitosti operací  
2) popsat a dokázat libovolný algoritmus na hledání min. kostry  
3) slovní žebřík - je dán slovník N slov délky nejvýše L, nalezněte nejdelší posloupnost slov, které se jedno z druhého tvoří odebráním jednoho libolného písmene, např Glass -> Glas -> Gas -> as (pokud by tato slova dávala smysl)  
4) Knihovna - v knihovně je N knih, z nichž K je setřízeno špatně - dotřiďte knihovnu  
*) V daném stromě zrušte co nejméně hran tak, aby vznikla alespoň jedna komponenta souvislosti obsahující právě K vrcholů  
  
Řešení:  
1) 2) triviálně popsat  
3) vytvořit graf, jehož vrcholy jsou slova a hrana z vrcholu A do vrcholu B vede právě tehdy, lze-li slovo B odebráním jednoho písmene přetvořit na slovo A, potom stačí dokázat, že graf je DAG a řešení je najít v něm nejdelší cestu - celkem O(N.L^2)  
4) procházíme posl. knih zleva doprava, a kdykoli je nějaká kniha zařazena špatně, vyndáme ji (+ navíc ještě tu která byla před ní), vyndaných knih je 2K, ty setřídíme a mergneme z původní posl. Celkem O(N + KlogK)  
*) by mě upřímně zajímala :)  
  
zkouška úplně v klidu, dostatek času, mírné hodnocení
<{/ForumPost}>