Cvičení z Algoritmů a Datových Struktur II
... se v ZS 2004/2005 koná ve středu od 9:00 v E4 a od 10:40 v E1.
Zápočet dostanete za naprogramování libovolného netriviálního algoritmu z přednášky, nebo i jiného, každopádně domluva předem nutná. Účast na cvičení je polehčující okolností :)
Informace o přednášce (syllabus, učební texty atd.) získáte na stránce přednášejícího.
Můžete si stáhnout textík o algoritmech okolo teorie čísel (řešení kongruencí, randomizované testování prvočíselnosti a RSA). Opravená verze z 19. 1. 2005.
Náměty na zápočtové programy
- Variace a`la Aho-McCorasicková:
- je dána množina slov; nalezněte všechny dvojice slov (x,y) takové, že x je podslovem y.
- "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.
- Příhrádkové třídění řetězců (v lineárním čase)
- Maximální tok Dinicovým algoritmem (již zabráno)
- Maximální tok Dinicovým algoritmem pro sítě s jednotkovými kapacitami (využijte toho, že vždy vypadne celá cesta a vůbec neukládejte kapacity ani rezervy)
- Maximální tok Goldbergovým algoritmem (již zabráno)
- 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árování v bipartitiním grafu redukcí na toky v sítích (opět Dinic pro jednotkové kapacity, ale můžete jej zkusit přeformulovat přímo v řeči párování a volných střídavých cest, vyjde jednodušší program)
- Hledání maximálního párovaní v obecném grafu Edmondsovým algoritmem (viz přednáška z Kombinatoriky a grafů I).
- Hledání maximálního toku minimální ceny
- Násobení polynomů za pomoci FFT
- (*) Násobení dlouhých čísel za pomoci FFT
- (*) Efektivní implementace FFT pomocí instrukcí MMX/SSE/VIS/AltiVec.
- Dekodér DTMF (frekvenční telefonní volby) (pomocí FFT)
- Násobení matic Strassenovým algoritmem (již zabráno)
- Konstrukce Voroného diagramu (Fortunův alg. nebo metoda rozděl a panuj)
- 3D konvexní obal
- Konstrukce splňujícího ohodnocení formule pro E3E3-SAT (klauzule délky 3, každá proměnná v právě třech klauzulích)
- Sčítání čísel ve Fibonacciho soustavě
- Rabin-Millerův test prvočíselnosti (s dlouhými čísly)
- Vygenerování náhodného prvočísla s rovnoměrným rozdělením
- (*) RSA
- Výpočet edit-distance dynamickým programováním (již zabráno)