Cvičení z Algoritmů a datových struktur v LS11/12

Cvičení probíhá každý čtvrtek od 14:00 v učebně S10.

Podmínky získání zápočtu

• Dvě úlohy vypracované v CodExu.
  1. Založte si účet na Codexu. Udělejte to pokud možno co nejdříve.
  2. Pošlete mi mailem váš login z codexu, já vás přidám do příslušné skupiny.
  3. Kdo jste ještě Codex nepotkali, funguje to tak, že pošlete řešení v C, C++, Pascalu nebo C#, automat to vyhodnotí na 10ti sadách vstupních dat a oznámí vám, na kterých váš program odpověděl špatně, nebo mu došla paměť či přidělený čas.
• První úloha: "Počet inverzí".
  • Chtěl bych, aby váš program byl schopný v limitu zpracovat VŠECH 10 SAD.
  • Váš algoritmus by měl fungovat v čase a paměti O(N log N), protože přidělený čas je řádově několik sekund a paměť cca 64MB.
  • Deadline na vyřešení této první úlohy je 30.4. 23:59
  • Vzorová data k testování.
• Druhá úloha: "Vrabci na střeše".
  • Chtěl bych, aby váš program byl schopný v limitu zpracovat VŠECH 10 SAD.
  • Váš algoritmus by měl fungovat v čase a paměti O(N+M), protože přidělený čas je řádově sekunda a paměť cca 64MB.
  • Deadline na vyřešení této druhé úlohy je 31.5. 23:59
  • Vzorová data k testování.
• "Zápočťák". Jedná se o 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 také úlohu teoretického rázu. Preferuji vaše vlastní nápady, některé však 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:
  • 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ězné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.
  • Hotové řešení mi odešlete mailem nebo dejte na papíře na cvičení.
• Rád bych, aby každý měl jiné zadání.
• Deadline na vybrání tématu je 8. května.

Zde je 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.

• Implementace Dijkstrova algoritmu s k-regulární haldou
• Strassenovo násobení čtvercových matic [O(nlog27)] (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 loga 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)]
• 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)]
• 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).
• Je dán graf G. Úkolem je zorientovat každou hranu G tak, aby výsledný graf byl silně souvislý. Výstupem algoritmu je tedy u každé hrany správná orientace, případně odpověď, že to nejde. [O(N+M)]
• 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)]
• Bitmapový černobílý obrázek je zkomprimován pomocí RLE, tj. jsou dány jeho rozměry X,Y a dále N dvojic (barva,počet pixelů této barvy v řadě za sebou). Navrhněte co nejefektivnější algoritmus, který spočítá velikost maximální souvislé oblasti bílé barvy ("souvisí" se svisle a vodorovně). Pozor, nemáme dostatek paměti na to, abychom celý obrázek dekomprimovali. [O(N)]
• 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)]

Na cvičení ke mně jsou přihlášeni tito studenti:

Pokud máte problém s tím, že jste zde uvedeni, dejte mi vědět a já vás odstraním.

Co se dělalo

23. února

Seznámení s podmínkami zápočtu. Úloha o vajíčku házeném z paneláku - 1 vajíčko, 2 vajíčka, a více, co za nejlepší řešení se dá dostat, jde to lépe než logaritmicky(?). Jak v setříděném poli najít rychle dvojici s určitým součtem. Hledání lokálního minima (do příště). Odhad složitosti Eratosthenova síta (příště). Maximální černý obdélník v bitmapě (příště).

1. března

Lokální minimum. Složitost Eratosthenova síta. Maximální černý obdélník. Souvislý podblok posloupnosti čísel s maximálním součtem (důkaz sami doma). Body na kružnici, existuje dvojice jejíž spojnice prochází středem? (doma)

8. března

Proč nejde insertovat do BVS rychleji nez O(log n). Nejbližší vyšší prvek v BVS a jak tím projít celý strom v O(n). Jak hledat v BVS k-tý nejmenší prvek. Intervalový strom (doděláme příště). Hledání nejdelší cesty v stromu (příště).

15. března

Dodělány intervalové stromy. Výraz v C, který otestuje mocninu dvojky. Nejdelší cesta ve stromu, včetně vážené varianty. Do příště: problém batohu, alternativní algoritmus na nejdelší cestu ve stromu, hledání max. nezávislé množiny ve stromu.

22. března

Cesta s maximálním součtem v trojúhelníku čísel. Nafukovací pole. Problém batohu. Maximální vybraná rostoucí podposloupnost a její varianty.

29. března

Úloha s chybějící dvojicí čísel. Join a split B-stromů, opakování algoritmů pro B-stromy. Několik těžkých úloh pro koumáky: kontrukce optimálních vyhledávacích stromů, rozdělení čísel do přihrádek aby nejtěžší přihrádka byla co nejlehčí, problém batohu pro dva a více batohů. Splay stromy.

5. dubna

Bubblesort a důkaz správnosti. Quicksort a jeho pravděpodobnostní analýza. Hledání k-tého nejmenšího prvku. Hledání sqrt(n) nejmenších prvků pole v čase O(n). Dotřídění pole kde prvek je do K pozic od svého místa. Pro koumáky: in-place merge s pomocnou pamětí O(sqrt(n)), nebo dokonce O(1). Prohledávní grafů a stavových prostorů do hloubky a šířky. Indiana Jones a mumie, cooperative hra dvou hráčů v bludišti.

12. dubna

Třídění N čísel z rozsahu 1..N^3. Topologické třídění a makefiles. Jednoznačnost topologického uspořádání. Kostra grafu. Povídání o DFS stromu. Neudělali jsme: Eulerovský tah. Počet cest v DAG. Maximální cesta ve váženém DAG. 6-barvení rovinného grafu. Dláždění grafu pomocí K_{1,2}. Testování 2-souvislosti.

19. dubna

N měst s max. 2 cestami doprava. 6-barvení rovinného grafu. Hledání eulerovského tahu. Maximální bílá podoblast v RLE zakompresené bitmapě (neuděláno). Odvození Dijkstrova algoritmu.

26. dubna

Další vlastnosti Dijkstry: proč nefunguje na záporných hranách, proč proč funguje když všechny záporné hrany sousedí se startem, více kritérií, ohodnocené vrcholy. Bellman-Fordův algoritmus, jak pomocí něho hledat záporné cykly. Floyd-Warshallův algoritmus. Výpočet Fibonacciho čísel pomocí matice. Do příště: jak u F-W i vypsat nejkratší cestu, cyklus ve směnární tabulce, jak najít vrchol ze kterého se lze dostat do celého grafu, Dijkstra pro "nejspolehlivější" cestu.

3. května

Výpis cestu u F-W. Cyklus ve směnární tabulce. Nejbezpečnější cesta pomocí Dijkstry. Nejkratší desítkové číslo se zakázanými ciframi dělitelné K. DFS strom a hledání mostů (hranová 2-souvislost). Do příště: jak najít vrchol ze kterého se lze dostat do celého (orientovaného) grafu.

10. května

Jak najít vrchol ze kterého se lze dostat do celého (orientovaného) grafu. Algoritmus rozkladu na silně souvislé komponenty. A je rostoucí pole čísel, jak najít i takové že A[i]=i? Může být výpočet x^2 efektivnější než x.y? Do příště: testování polosouvislosti.

17. května

Úloha s vkládáním krabic do sebe. Polosouvislost. Rozděl a panuj. Rychlé násobení dlouhých čísel. Dynamické programování a minimální triangulace N-úhelníka.

24. května

Minimální kostry. Hladový (Kruskalův) algoritmus, důkaz správnosti, logaritmické slévání komponent. Stručně Jarníkův a Borůvkův algoritmus. Jak hledat MK v grafu váženém vahami 1..K. Jaký vliv na MK má změna váhy jedné hrany? Jak hledat MK když určité vrcholy mají být listy. Na problém batohu nefunguje hladový algoritmus.