Cvičení z Algoritmů a datových struktur I

Pondělí 17:20 v S10. Obyčejné cvičení, jako všechna ostatní :) Co říct víc? Třeba:

Co jsme dělali

datum	co se cvičilo
23. 2.	Rekurzivní hádanky.
2. 3.	Házení vajíček. Půlící algoritmus na největší společné dělitele. Kráva za plotem. Čísla ve tvaru 2ⁱ3^j5^k. Největší prázdná podmatice.
9. 3.	Programování na RAMu. Proč jsme si RAM nezavedli jinak? (nekonečné programy, reálná čísla, neomezená čísla?) Hrátky s grafy a prohledáváním do šířky: komponenty souvislosti, případ rozbitého autíčka, kulhavý kůň, dva roboti v bludišti.
16. 3.	Grafové algoritmy: jak poznat, že je v grafu cyklus? Agenti a jejich šéf. Kreslení grafů jedním, případně více tahy. Hledání nejmenšího kladného čísla zapsaného pomocí nul a jedniček, které je dělitelné daným číslem (jak upravit algoritmus z přednášky? existuje takové číslo vždy?).
23. 3.	Opět grafové algoritmy: počítání cest, vyvážená a skoro vyvážená orientace grafu, artikulace, asfaltování (rozklad grafu na cesty délky 2), barvení rovinných grafů šesti barvami. Jak se barví pěti?
30. 3.	Nejkratší cesty: Dijkstrův algoritmus kontra záporné hrany, jak vyzrát na vrcholová ohodnocení vrcholů, jak se zbavit záporných hran pomocí potenciálů. Nejspolehlivější cesta. Do konce dubna si rozmyslete svou zápočtovou práci a domluvte se se mnou na tématu.
6. 4.	Jak zbohatnout na devizových kursech? Hladový algoritmus. Minimální kostry kontra více stejně těžkých hran. Nejkratší cesty a minimální kostry v grafech ohodnocených malými celými čísly. Jak najít minimální kostru, v níž jsou zadané vrcholy listy (nebo právě zadané vrcholy)?
20. 4.	Násobení čísel na mnoho způsobů, algoritmy se složitostí Θ(n^log₃5) a Θ(n^1+ε). Může být umocňování rychlejší než násobení? Propojování drátů.
27. 4.	Od náhodných bitů k náhodným číslům. Míchání karet aneb náhodné permutace. Sumy naše vezdejší. Nejbližší dvojice bodů v rovině.
4. 5.	K-tý nejmenší prvek na mnoho způsobů. Jak dopadnou trojice a jak sedmice? Přihrádkové třídění v poli, třídění řetězců pro malé i velké abecedy.
11. 5.	Přehlídka stromových struktur a jejich srovnání. Operace s vyhledávacími stromy: následníci, intervalové dotazy apod. Ochutnávka amortizované složitosti.
18. 5.	Otázky a odpovědi. Příklady téměř zkouškové. Cesty dané délky ve stromech.

Zápočet

Zápočet je za vypracování zápočtové práce. Ta by měla pojednávat o řešení nějakého (nepříliš) jednoduchého algoritmického problému a měli byste v ní popsat problém, svůj algoritmus, rozebrat jeho časovou a paměťovou složitost a pokud není zjevné, že je algoritmus správný, dokázat ještě jeho správnost. Doporučuji vám (ale není to povinné), abyste si také algoritmus zkusili naprogramovat, mnoho potřebných detailů si uvědomíte až při tom. Za používání cizích myšlenek (vět či algoritmů z knížek, materiálů z přednášky atd.) se není třeba stydět, pokud je budete náležitě citovat.

Než začnete práci psát, domluvte se se mnou, prosím, na tématu, nejlépe mailem.

Svou práci mi buďto přineste na papíře, nebo mi ji pošlete e-mailem. V takovém případě ovšem, prosím, použijte nějaký otevřený formát (tím myslím formát, jehož struktura je všeobecně známa) – to je třeba čistý text, PostScript, PDF nebo TeX. Tuto podmínku naopak nesplňuje Microsoft Word ani RTF.

Inspirace pro zápočtovou práci

Implementace Dijkstrova algoritmu s k-regulární haldou
Strassenovo násobení čtvercových matic [O(n^log₂7)] (zkuste zjistit, od které velikosti matic se vyplácí přepnout na klasický algoritmus)
Přihrádkové třídění řetězců [O(součet délek)]
Insert a Delete v AVL-stromech [O(log n)]
Insert a Delete v červeno-černých stromech [O(log n)]
Insert a Delete v (a,b)-stromech [O(b log_a n)]
Rozdělení (2,3)-stromu na dva, jeden obsahující prvky menší než dané x, druhý ty větší. [O(log n)]
Hledání silně souvislých komponent orientovaného grafu [O(n+m)]
Hledání nejbližší dvojice bodů v rovině [O(n log n)] (rozděl a panuj)
Slévání setříděných posloupností v konstantním pomocném prostoru [O(n)] (pomůže pan Google)
Implementujte Treap: to je randomizovaná datová struktura kombinující strom a haldu. Má tvar stromu, přičemž v každém prvku je mimo klíče ještě náhodná, řekněme 32-bitová, "sušenka". Strom je podle prvků uspořádaný jako vyhledávací strom a podle sušenek jako halda. K Insertu a Deletu se hodí rotace.
Na vstupu je číslo K a posloupnost (postupně, prvek po prvku, takže dopředu nevíte, jak dlouhá). Vyberte náhodně K prvků posloupnosti tak, aby všechny K-tice měly stejnou pravděpodobnost. Paměťová složitost by neměla záviset na délce vstupní posloupnosti.
Ve vrcholech stromu jsou rozmístěni loupežníci. Nalezněte rozmístění co nejmenšího počtu četníků tak, aby mezi každými dvěma loupežníky byl aspoň jeden četník (možno i na tomtéž vrcholu, co některý z loupežníků). [O(n)]
Jak doplnit do neorientovaného grafu co nejméně hran, aby se stal hranově 2-souvislým? [O(n+m)]
Dělení dlouhých čísel [O(n^log₂3)] (například redukcí na násobení pomocí Newtonovy metody)
Přesmyčkový slovník: program si načte seznam slov (slovník) a pak umí k zadanému slovu najít všechny přesmyčky, které se vyskytují ve slovníku.
Hromada souborů na disku, efektivně najít všechny, které mají stejný obsah.
Je dána množina desítkových číslic M a číslo K. Najděte nejmenší kladné přirozené číslo, jehož desítkový zápis se skládá pouze z číslic z množiny M, a přitom je dělitelné číslem K. (sestrojte si vhodný graf)
Jsou dány dva řetězce, spočítejte jejich editační vzdálenost, čili minimální počet smazání, vložení a změn znaků, jimiž lze z jednoho řetězce vytvořit druhý. [O(poly(n))] (buď sestrojte vhodný graf nebo zkuste dynamické programování)
V rovině leží množina obdélníků (hrany rovnoběžné s osami). Jaký je obsah (či obvod) jejich sjednocení?
Nakreslete neorientovaný graf nejmenším možným počtem tahů. [O(n+m)]
Obarvěte rovinný graf šesti (pěti?) barvami. [O(n)]
Fibonacciho číselná soustava používá číslice 0 a 1, ale narozdíl od dvojkové má k-tý řád váhu rovnou k-tému Fibonaccimu číslu. Naprogramujte sčítání dvou čísel v této soustavě. [O(n)]