Cvičení z Pokročilé algoritmizace v LS18/19

Cvičení probíhá každé liché úterý od 14:30 v učebně 347 (nová budova).

Konzultace

Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229 (prvočíslo!).

Podmínky zápočtu

Zápočet lze získat za semestrální práci, která spočívá ve vypracování netriviálního úkolu. To může znamenat buďto implementaci nějakého algoritmu či datové struktury z přednášky či cvičení, nebo úlohu teoretického rázu.

Preferuji vaše vlastní nápady, některé mohou samozřejmě vyplynout z přednášky či cvičení. O každé úloze bych se s vámi však chtěl pobavit, zda ji schválím. Vypracování zápočťáku by mělo obsahovat následující věci:

• Perfektní slovní popis použitého algoritmu, srozumitelný i bez nahlížení do zdrojáku.
• Důkaz správnosti algoritmu.
• Analýzu časové a paměťové složitosti.
• Program v běžném programovacím jazyce.
• Pokud je zadání spíše implementační, měla by být posílena programová část na úkor slovní části.
• Řešení vysázejte nejlépe v TeXu, nebo ho alespoň zkonvertujte do PDF. Číst matematiku/informatiku ve Wordu odmítám.

Dále:

• Rád bych, aby každý měl jiné zadání.
• Deadline na vybrání tématu je 15. dubna, 23:59, ozvěte se však raději dříve, kdyby už třeba téma bylo zabrané.
• Hotové řešení mi odešlete mailem.
• Pokud nebudu mít námitek, domluvíme se na osobním předvedení.
• Deadline na vypracovanou práci je do konce semestru, tedy před začátkem zkouškového. Nicméně počítejte s tím, že možná nebudu napoprvé spokojen a budete muset něco předělávat, navíc nebudu mít na samotném konci semestru tolik času.

Inspirace pro semestrální práci

Zde je zdaleka nekompletní seznam inspirací pro zápočtovou práci, průběžně budou přibývat. Vlastní nápady jsou preferovány. V případě nejasnosti zadání či jiných dotazů se mi ozvěte.

• 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)]
• Implementujte a popište 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.
• 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)]
• 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.
• Nakreslete neorientovaný graf nejmenším možným počtem tahů. [O(n+m)]
• Obarvěte rovinný graf pěti barvami. [O(n)]
• Vymyslete algoritmus, který dostane neorientovaný graf, a zorientuje ho tak, aby se vstupní a výstupní stupeň lišil maximálně o 1. [O(n+m)]
• Dáno číslo K a N-prvková posloupnost taková, že existuje její K-prvková podmnožina (ale už nevíme jaká), kterou když odebereme, zbude vzestupně utříděná posloupnost. Co nejrychleji posloupnost dotřiďte. Lze řešit v O(N+K.log K).
• Dán graf G. Navrhněte algoritmus, který všechny hrany zorientuje tak, že u každého vrcholu se vstupní a výstupní stupeň liší maximálně o jedničku. [O(N+M)]
• Dán neorientovaný graf G. Chceme ho pokrýt grafy K_{1,2}, tedy cestičkami délky 2 tak, aby každá hrana byla pokryta pouze jednou cestičkou a žádná hrana nebyla vynechaná. Navrhněte algoritmus, který zjistí, zda G lze takto pokrýt a pokud ano, takové pokrytí vypíše. [O(n+m)]
• Housenka je strom, který má páteř ve tvaru cesty, na kterou jsou připojeny nožičky (listy). Jak v zadaném stromě najít housenku s maximálním počtem vrcholů? [O(n)]
• V rovině dány červené a modré body. Efektivně zjistěte, zda je lze oddělit nějakou přímkou.
• Oploťte $N$ bodů v rovině dvěma ploty tak, aby každý bod byl oplocen a celkově jste spotřebovali nejmenší množství pletiva.
• Navrhněte efektivní algoritmus, který najde nejdelší vodorovnou úsečku ležící uvnitř zadaného (ne nutně konvexního) mnohoúhelníku.
• V rovině leží množina obdélníků (hrany rovnoběžné s osami). Jaký je obsah (či obvod) jejich sjednocení? [O(n log n)]
• Je dána množina bodů v rovině. Rozložte ji na dvě disjunktní středově symetrické množiny, případně oznamte, že to nejde.
• Optimalizovaně implementujte datovou strukturu Hollow Heaps (google poradí článek z r.2015)
• Optimalizovaně implementujte van Emde-Boasovy stromy (opět pomůže google)
• Optimalizovaně implementujte d-dimenzionální intervalové stromy (opět pomůže google)
• Optimalizovaně implementujte d-dimenzionální KD-stromy (opět pomůže google)
• Optimalizovaně implementujte strukturu Rtree pro lokaci bodů v rovině (opět pomůže google)

Vybraná témata prací