# Zkouska 3.2.

<{ForumPost(poster="vexis", timestamp=2010-02-03 18:08:18)}>
Zadani z dnesni pisemky:  
  
1. Aho-Corasick  
2. 2-aproximační algoritmus batohu, kdyz plati trojuhelnikova nerovnost  
3. najit vsechny pruseciky parabol ax<sup>2</sup> + bx + c = 0 kde a >0 (postup vpodstate stejny jako u usecek akorat pro poloviny parabol)  
4. pokryt vykousanou sachovnici dominovymi kostkami (prevedeme na problem perfektniho parovani -> pridame zdroj a stok a kapacity 1 -> najdeme maximalni tok)
<{/ForumPost}>