Zápočtové úlohy z ADS1

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í? [O(n log n)]
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)]
Jak najít všechna dokonalá čísla od 1 do n? [O(n log n)]