Zápočtové úlohy z ADS2

Řetězce

Je dána množina slov; nalezněte všechny dvojice slov (x,y) takové, že x je podslovem y.
Je dána množina slov a text; spočítejte, kolikrát se které slovo v textu vyskytuje (v čase lineárním se součtem délek všech slov a délky textu).
Cenzorův problém: je dán seznam zakázaných slov a text T (bez mezer). Odstraňte z textu všechny výskyty zakázaných slov; tím ovšem mohou vzniknout nové, tak je odstraňte také, atd. To vše v lineárním čase.
Je dán řetězec, najděte jeho lexikograficky minimální rotaci (v lineárním čase).
Je dán řetězec, najděte v něm nejdelší palindromický podřetězec (v lineárním čase).
Je dán řetězec a číslo K, najděte nejčastější podřetězec délky K (v průměrně lineárním čase).
Najdětě nejdelší řetězec, který se v daném textu vyskytuje alespoň dvakrát.

Maximální párování v bipartitním grafu pomocí Dinicova algoritmu
Nalezení maximální množiny hranově disjunktních cest mezi zadanými dvěma vrcholy v orientovaném grafu. (Toky a rozklad toku na cesty.)
Maximální tok Goldbergovým algoritmem s výběrem nejvyššího vrcholu s přebytkem
Maximální tok algoritmem Tří Indů
Určování stupně hranové (vrcholové) souvislosti zadaného neorientovaného grafu (redukce na toky v sítích, nejlépe Dinicovým algoritmem pro jednotkové kapacity)
Hledání maximálního párovaní v obecném grafu Edmondsovým algoritmem (viz přednáška z Kombinatoriky a grafů I)
Je dán bipartitní graf s ohodnocenými vrcholy. Nalezněte minimální vrcholové pokrytí, tj. množinu vrcholů s minimálním součtem ohodnocení takovou, že každá hrana grafu sousedí s aspoň jedním z vybraných vrcholů. (Hlídáme bipartitní město různě drahými hlídači.)
Hledání maximálního toku minimální ceny

Konstrukce Voroného diagramu (Fortunův alg. nebo metoda Rozděl a panuj)
Je dána množina obdélníků v rovině (strany rovnoběžné s osami), spočítejte obsah a obvod jejich sjednocení (hint: zametání).
Je dána množina úseček v rovině, spočítejte, kolik mají průsečíků (hint: zametání).
Triangulace mnohoúhelníku (rozklad na sjednocení trojúhelníků)
Datová struktura na lokalizaci bodu v rovině (viz přednáška)
3D konvexní obal

Rabinův-Millerův test prvočíselnosti (s dlouhými čísly), případně nějaký jiný pravděpodobnostní test
(*) Šifrovací algoritmus RSA (s alespoň 256-bitovými klíči, aby to mělo smysl)

(*) Zkuste dokázat následující větu: Je-li jazyk L regulární (tj. dá se rozhodnout nějakým konečným automatem, respektive popsat regulárním výrazem), pak existuje booleovský obvod hloubky O(log n), který ho rozpoznává.
Nalezení nejdelší cesty v kaktusovém grafu (to je neorientovaný graf, jehož každá hrana leží na nejvýše jednom cyklu).