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

Čtvrtek 10:40 v S10. Obyčejné cvičení, jako všechna ostatní :) Co říct víc? Třeba:

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.

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)]
• 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)]

Na rozmyšlenou

• Jak pro dlouhé číslo zjistit, zda je dělitelné nějakou konstantou z?
• Dokažte, že sčítání čísel zleva doprava (se skokem zpět, dojde-li k přenosu) je také lineární.
• Dokažte, že následující funkce sčítá dvě čísla:

     f(x,y):
        if x=0 => return y
        else => return f((x AND y)*2, x XOR y).
  

• Jak se chová algoritmus pro hledání mediánu, když místo pětic použijeme trojice nebo sedmice?
• Jak metodou Rozděl a panuj hledat nejbližší dvojici v zadané množině bodů v rovině?