Cvičení z algoritmů a datových struktur, TIN060

Cvičení se konají dvě paralelně, jedno v úterý v 9:00 v S6, druhé v úterý v 12:20 v S7.

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

Zápočet získáte za vypracování zápočtové práce. Ta by měla obsahovat implementaci některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud, a dokumentaci. Dokumentace je popis toho, jak algoritmus nebo implementace funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:

Poslat do konce dubna mail, že budete chtít zápočet. (Objevíte se v seznamu.)
Domluvit se se mnou do konce semestru, tj. do 31. 5. 2009 mailem na tématu zápočtové práce. Inspirace například v seznamu Martina Mareše. Pokud jsme nějaké téma dopodrobna rozebrali na cvičení, tak se mi nejspíš nebude líbit.
Vytvořit zápočtové práce včetně dokumentace.
Poslat mi hotový zápočťák. Většinou po krátké iteraci dostanete zápočet, ale mohu požadovat i osobní předvedení.

Kromě předchozího seznamu je velmi vhodná aktivní účast na cvičení (když si vás budu pamatovat, tak nejspíš nemusíte dělat neudělatenou práci a tak :–).

Témata by se neměla moc opakovat, takže jedno téma povoluji nanejvýš dvěma lidem.

Seznam přidělených zápočtových prací.

Obsah cvičení (21. 02. 2011)

Datum Obsah
24. února 2009
Řešené příklady:
Určete, co dělají následující funkce a jak dlouho jim to trvá:
f(x,y) = if x==0 => return y
         else => return f((x AND y) * 2, x XOR y)
g(x,y) = if y==0 => return 0
         else if y sudé => return 2 * g(x, y/2)
         else => return 2 * g(x, y/2) + x
h(x,y) = if x<y => return (0,x)
         else (a,b) <- 2 * h(x/2, y)
              if x liché => b <- b + 1
              if b>=y => a <- a+1, b <- b-y
              return (a,b)

Máme v vajíček a panelák o N patrech. Cílem je najít nejnižší patro, ze kterého když hodíme vajíčko, tak se rozbije. [Vyřešili jsme úlohu pro 1 vajíčko optimálně na N pokusů, pro log N vajíček optimálně na log N pokusů, pro v vajíček na v*(N^1/v - 1) pokusů.]
3. března 2009
Řešené příklady:
Určete složitost Erarosthenova síta.
Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaký je součet čísel a_i až a_j?".
Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaké je maximum čísel a_i až a_j?".
10. března 2009
Řešené příklady:
Dostanete matici s nulami a jedničkami. Najděte co největší podmatici složenou ze samých nul.
Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Najděte nejkratší cestu k pokladu.
Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka a pasti. Pastí jdete třikrát tak dlouhou dobu jako normálním políčkem. Najděte nejkratší cestu k pokladu.
Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Máte krumpáč, kterým jde prokopnout libovolná stěna. Najděte nejkratší cestu k pokladu, na které prokopnete minimum stěn.
Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, dveře tří barev (R, B, Y), klíče tří barev (r, g, b). Dveře nemůžete projít, když nemáte klíč odpovídající barvy. Najděte nejkratší cestu k pokladu.
Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, právě jedna smrtka a libovolný počet mečů. Smrtka se hýbe poté, co se pohnete vy, a 1) jde nahoru/nikam/dolu, aby se vám přiblížila; poté 2) jde doleva/nikam/doprava, aby se vám přiblížila. Když jít nemůže, stojí. Najděte nejkratší cestu k pokladu, na které se nepotkáte se smrtkou, aniž byste měli meč.
17. března 2009
Řešené příklady:
Dostanete N. Najděte takové číslo dělitelné N, jehož desítkový zápis je složen pouze z nul a jedniček a tento zápis je nejkratší možný.
Pro dané dvě posloupnosti a₁, ..., a_N a b₁, ..., b_M najděte nejkratší posloupnost operací 'odeber prvek' a 'přidej prvek', která z první posloupnosti vyrobí druhou. Najděte řešení nejen v čase Ο(NM), ale hlavně v čase Ο((N+M)D), kde D je počet operací odeber a přidej.
Máme graf, jehož vrcholy jsou mafiáni v italském městečku, a orientované hrany značí, že mafián ovládá jiného mafiána. Zjistěte, zda je v městě mafiánský kmotr. To je takový mafián, který ovládá všechny mafiány v městečku.
24. března 2009
Řešené příklady:
Dostanete neorientovaný graf. Rozhodněte, zda ho lze nakreslit jedním tahem a pokud ano, najděte takový tah.
Dostanete neorientovaný graf. Najděte všechny artikulace, což je vrchol, který když z grafu odstraníte, stane se nesouvislým.
Zorientujte hrany daného neorientovaného grafu tak, aby se v každém vrcholu lišil vstupní a výstupní stupeň nanejvýš o jedna.
Zorientujte hrany daného neorientovaného rovinného grafu tak, aby měl každý vrchol výstupní stupeň nanejvýš tři.
Obarvěte daný rovninný graf pěti barvami.
31. března 2009
Řešené příklady:
Zuřivý robot Čenda má v paměti P instrukcí (vpřed, vlevo vbok, vpravo vbok), které pořád dokola opakuje. Pro dané bludiště NxN je vaším cílem pro každé políčko spočítat, za jak dlouho se Čenda dostane z bludiště ven, když začne na tomto políčku provádět od začátku svůj program.
Uprchlý robot Čenda shání členy do své lupičské bandy. Každé vězení obsahuje nějaký počet trestanců a graf cest mezi věznicemi je strom. Čenda by si chtěl vybrat nějaké věznice, které vyloupí, aby součet trestanců ve vyloupených věznicích byl co největší a zároveň žádné dvě vyloupené věznice nesousedily.
Určete složitost Dijkstrova algoritmu.
Najděte graf se zápornými hranami ale bez záporných cyklů, na kterém nefunguje Dijkstrův algoritmus správně.
Rozmyslete si, že když záporné hrany odstraníte přičtením konstanty, nejkratší cesty nezůstanou zachovány.
Dostali jste ohodnocení H(v) pro každý vrchol grafu, že platí H(u)≤H(u) + vzdálenost(u, v). Ukažte, že graf s ohodnoceními původní_vzdálenost(u, v) + H(v) - H(u) nemá žádné záporné hrany a přitom nejkratší cesty zůstaly zachovány.
7. dubna 2009
Řešené příklady:
V daném ohodnoceném grafu maximálního stupně D nalezněte čtyřcyklus s nejvetším ohodnocením.
Mějme N měn, můžeme je převádět každou na každou, kurz výměny z i-té na j-tou měnu je r_ij. Zjistěte, zda lze měněním měn něco vydělat.
Navrhněte implementaci Jarníkova algoritmu se složitostí Ο(m log n) a Ο(n²) a Ο(n log n + m).
Zjistěte, jaké má Borůvkův algoritmus problémy v případě, že různé hrany mohou mít stejné ohodnocení, a navrhněte, jak ho opravit.
Nalezněte libovolnou druhou nejlepší minimální kostru, tedy takovou kostru, jejíž ohodnocení je druhé nejlepší.
Mějme graf ohodnocený malými celými čísly 1..K. Navrhněte implementaci Dijsktrova a Jarníkova algoritmu se složitostí Ο(nK+m).
14. dubna 2009
Řešené příklady:
Dostanete graf s nějakými označenými vrcholy. Najděte takovou minimální kostru, že všechny označené vrcholy jsou listy.
Dostanete multigraf. Vymyslete, jak v ho v lineárním čase převést na graf, aby z násobných hran zůstala vždy nejkratší.
Spočtěte počet inverzí dané permutace [Ο(N log N)].
Z daných bodů v rovině najděte dva nejbližší [Ο(N log N)].
21. dubna 2009
Řešené příklady:
Máte pole nerostoucích hodnot, které má začátek a je potenciálně nekonečně dlouhé. Najděte v něm danou hodnotu x.
V mrakodrapu je N drátů dole a M drátů nahoře, některé jsou spojené. Kromě nich máme ještě zemák. Jak na co nejméně přejezdů zjistit, jak jsou dráty spojené, když je můžete spojovat jenom se zemákem? Jak to dopadne, když je můžete spojovat i mezi sebou?
V jeskyni je drak a přistihl vás, jak mu kradete poklad. Nyní si s ním musíte zahrát o život následující hru. Drak si myslí číslo od nuly do milionu. Vy smíte na papír napsat nejakou množinu čísel a drak vám řekne, jestli v té množině je to číslo, které si myslí. Drak ovšem může nejvýš jednou zalhat. Vymyslete řešení na co nejméně dotazů.
Máte generátor náhodných bitů. Jak vymyslet funkci random(N), která bude vracet čísla 0, 1, ..., N-1 s rovnoměrným rozdělením?
28. dubna 2009
Řešené příklady:
Dostali jste skoro setříděnou posloupnost, ve které je k špatně zatříděných prvků. Dotřiďte ji v čase Ο(N + K log K).
Dostali jste skoro setříděnou posloupnost, ve které je každý prvek nejvýš o k pozic mimo. Dotřiďte ji v čase Ο(N log K).
Vygenrujte náhodnou permutaci.
V balíčku 52 karet je 26 červených. Balíček je náhodně zamíchán. Kdykoliv můžete říct stop, líznout si kartu z vrchu balíčku a když bude červená, vyhráli jste. Když neřeknete stop, kartu sejme nepřítel a ukáže vám ji. Pokud neřeknete stop až do poslední karty, musíte otočit poslední. Nalezněte (pravděpodobnostní) strategii, která maximalizuje pravděpodobnost výhry.
5. května 2009
Řešené příklady:
Naimplementujte přihrádkové třídění pole A do pole B bez použití dalších pointerů.
Setřiďte daných N slov o celkové délce P písmen v čase Ο(P+A), kde A je počet písmen abecedy.
Rozdělte daných N slov o celkové délce P písmen do skupin, aby v jedné skupině byla slova, která jsou svými přesmyčkami.
Dva zakořeněné stromy s ohodnocenými vrcholy jsou isomorfní, pokud jsou stejné až na pořadí synů. Popište algoritmus, který zjistí, zda jsou dva dané stromy isomorfní.
12. května 2009
Řešené příklady:
Vymyslete postup, který k danému vrcholu v binárním stromě najde jeho následníka v inorder uspořádání, ukažte, že má amortizovaně konstantní složitost.
Dostanete N intervalů. Najděte z nich ten, který proniká největší množství jiných intervalů.
Ukažte, že N přičtení jedničky k C-cifernému číslu trvá O(N+C). Vymyslete způsob, jak implementovat přičítání a odečítání jedničky tak, aby N operací trvalo Ο(N+C).
Je dané K. Načítejte dál N čísel. Vždy po načtení jednoho čísla vypište, jaký je nejmenší rozdíl nějakých z K předchozích čísel.
Implementujte MTF v co nejlepším čase.
19. května 2009
Řešené příklady:
V posloupnosti nezáporných čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K.
V posloupnosti celých čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K.
V daném stromě s hranami ohodnocenými celými čísly a_i najděte souvislou cestu se součtem rovným danému K.
Rozmyslete si implementaci hešovacích tabulek, které rostou / zmenšují se podle aktuální obsazenosti.

Datum	Obsah
24. února 2009	Řešené příklady: Určete, co dělají následující funkce a jak dlouho jim to trvá: `f(x,y) = if x==0 => return y` `else => return f((x AND y) * 2, x XOR y)` `g(x,y) = if y==0 => return 0` `else if y sudé => return 2 * g(x, y/2)` `else => return 2 * g(x, y/2) + x` `h(x,y) = if x<y => return (0,x)` `else (a,b) <- 2 * h(x/2, y)` `if x liché => b <- b + 1` `if b>=y => a <- a+1, b <- b-y` `return (a,b)` Máme v vajíček a panelák o N patrech. Cílem je najít nejnižší patro, ze kterého když hodíme vajíčko, tak se rozbije. [Vyřešili jsme úlohu pro 1 vajíčko optimálně na N pokusů, pro log N vajíček optimálně na log N pokusů, pro v vajíček na v(N^1/v - 1)* pokusů.]
3. března 2009	Řešené příklady: Určete složitost Erarosthenova síta. Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaký je součet čísel a_i až a_j?". Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaké je maximum čísel a_i až a_j?".
10. března 2009	Řešené příklady: Dostanete matici s nulami a jedničkami. Najděte co největší podmatici složenou ze samých nul. Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Najděte nejkratší cestu k pokladu. Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka a pasti. Pastí jdete třikrát tak dlouhou dobu jako normálním políčkem. Najděte nejkratší cestu k pokladu. Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Máte krumpáč, kterým jde prokopnout libovolná stěna. Najděte nejkratší cestu k pokladu, na které prokopnete minimum stěn. Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, dveře tří barev (R, B, Y), klíče tří barev (r, g, b). Dveře nemůžete projít, když nemáte klíč odpovídající barvy. Najděte nejkratší cestu k pokladu. Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, právě jedna smrtka a libovolný počet mečů. Smrtka se hýbe poté, co se pohnete vy, a 1) jde nahoru/nikam/dolu, aby se vám přiblížila; poté 2) jde doleva/nikam/doprava, aby se vám přiblížila. Když jít nemůže, stojí. Najděte nejkratší cestu k pokladu, na které se nepotkáte se smrtkou, aniž byste měli meč.
17. března 2009	Řešené příklady: Dostanete N. Najděte takové číslo dělitelné N, jehož desítkový zápis je složen pouze z nul a jedniček a tento zápis je nejkratší možný. Pro dané dvě posloupnosti a₁, ..., a_N a b₁, ..., b_M najděte nejkratší posloupnost operací 'odeber prvek' a 'přidej prvek', která z první posloupnosti vyrobí druhou. Najděte řešení nejen v čase Ο(NM), ale hlavně v čase Ο((N+M)D), kde D je počet operací odeber a přidej. Máme graf, jehož vrcholy jsou mafiáni v italském městečku, a orientované hrany značí, že mafián ovládá jiného mafiána. Zjistěte, zda je v městě mafiánský kmotr. To je takový mafián, který ovládá všechny mafiány v městečku.
24. března 2009	Řešené příklady: Dostanete neorientovaný graf. Rozhodněte, zda ho lze nakreslit jedním tahem a pokud ano, najděte takový tah. Dostanete neorientovaný graf. Najděte všechny artikulace, což je vrchol, který když z grafu odstraníte, stane se nesouvislým. Zorientujte hrany daného neorientovaného grafu tak, aby se v každém vrcholu lišil vstupní a výstupní stupeň nanejvýš o jedna. Zorientujte hrany daného neorientovaného rovinného grafu tak, aby měl každý vrchol výstupní stupeň nanejvýš tři. Obarvěte daný rovninný graf pěti barvami.
31. března 2009	Řešené příklady: Zuřivý robot Čenda má v paměti P instrukcí (vpřed, vlevo vbok, vpravo vbok), které pořád dokola opakuje. Pro dané bludiště NxN je vaším cílem pro každé políčko spočítat, za jak dlouho se Čenda dostane z bludiště ven, když začne na tomto políčku provádět od začátku svůj program. Uprchlý robot Čenda shání členy do své lupičské bandy. Každé vězení obsahuje nějaký počet trestanců a graf cest mezi věznicemi je strom. Čenda by si chtěl vybrat nějaké věznice, které vyloupí, aby součet trestanců ve vyloupených věznicích byl co největší a zároveň žádné dvě vyloupené věznice nesousedily. Určete složitost Dijkstrova algoritmu. Najděte graf se zápornými hranami ale bez záporných cyklů, na kterém nefunguje Dijkstrův algoritmus správně. Rozmyslete si, že když záporné hrany odstraníte přičtením konstanty, nejkratší cesty nezůstanou zachovány. Dostali jste ohodnocení H(v) pro každý vrchol grafu, že platí H(u)≤H(u) + vzdálenost(u, v). Ukažte, že graf s ohodnoceními původní_vzdálenost(u, v) + H(v) - H(u) nemá žádné záporné hrany a přitom nejkratší cesty zůstaly zachovány.
7. dubna 2009	Řešené příklady: V daném ohodnoceném grafu maximálního stupně D nalezněte čtyřcyklus s nejvetším ohodnocením. Mějme N měn, můžeme je převádět každou na každou, kurz výměny z i-té na j-tou měnu je r_ij. Zjistěte, zda lze měněním měn něco vydělat. Navrhněte implementaci Jarníkova algoritmu se složitostí Ο(m log n) a Ο(n²) a Ο(n log n + m). Zjistěte, jaké má Borůvkův algoritmus problémy v případě, že různé hrany mohou mít stejné ohodnocení, a navrhněte, jak ho opravit. Nalezněte libovolnou druhou nejlepší minimální kostru, tedy takovou kostru, jejíž ohodnocení je druhé nejlepší. Mějme graf ohodnocený malými celými čísly 1..K. Navrhněte implementaci Dijsktrova a Jarníkova algoritmu se složitostí Ο(nK+m).
14. dubna 2009	Řešené příklady: Dostanete graf s nějakými označenými vrcholy. Najděte takovou minimální kostru, že všechny označené vrcholy jsou listy. Dostanete multigraf. Vymyslete, jak v ho v lineárním čase převést na graf, aby z násobných hran zůstala vždy nejkratší. Spočtěte počet inverzí dané permutace [Ο(N log N)]. Z daných bodů v rovině najděte dva nejbližší [Ο(N log N)].
21. dubna 2009	Řešené příklady: Máte pole nerostoucích hodnot, které má začátek a je potenciálně nekonečně dlouhé. Najděte v něm danou hodnotu x. V mrakodrapu je N drátů dole a M drátů nahoře, některé jsou spojené. Kromě nich máme ještě zemák. Jak na co nejméně přejezdů zjistit, jak jsou dráty spojené, když je můžete spojovat jenom se zemákem? Jak to dopadne, když je můžete spojovat i mezi sebou? V jeskyni je drak a přistihl vás, jak mu kradete poklad. Nyní si s ním musíte zahrát o život následující hru. Drak si myslí číslo od nuly do milionu. Vy smíte na papír napsat nejakou množinu čísel a drak vám řekne, jestli v té množině je to číslo, které si myslí. Drak ovšem může nejvýš jednou zalhat. Vymyslete řešení na co nejméně dotazů. Máte generátor náhodných bitů. Jak vymyslet funkci random(N), která bude vracet čísla 0, 1, ..., N-1 s rovnoměrným rozdělením?
28. dubna 2009	Řešené příklady: Dostali jste skoro setříděnou posloupnost, ve které je k špatně zatříděných prvků. Dotřiďte ji v čase Ο(N + K log K). Dostali jste skoro setříděnou posloupnost, ve které je každý prvek nejvýš o k pozic mimo. Dotřiďte ji v čase Ο(N log K). Vygenrujte náhodnou permutaci. V balíčku 52 karet je 26 červených. Balíček je náhodně zamíchán. Kdykoliv můžete říct stop, líznout si kartu z vrchu balíčku a když bude červená, vyhráli jste. Když neřeknete stop, kartu sejme nepřítel a ukáže vám ji. Pokud neřeknete stop až do poslední karty, musíte otočit poslední. Nalezněte (pravděpodobnostní) strategii, která maximalizuje pravděpodobnost výhry.
5. května 2009	Řešené příklady: Naimplementujte přihrádkové třídění pole A do pole B bez použití dalších pointerů. Setřiďte daných N slov o celkové délce P písmen v čase Ο(P+A), kde A je počet písmen abecedy. Rozdělte daných N slov o celkové délce P písmen do skupin, aby v jedné skupině byla slova, která jsou svými přesmyčkami. Dva zakořeněné stromy s ohodnocenými vrcholy jsou isomorfní, pokud jsou stejné až na pořadí synů. Popište algoritmus, který zjistí, zda jsou dva dané stromy isomorfní.
12. května 2009	Řešené příklady: Vymyslete postup, který k danému vrcholu v binárním stromě najde jeho následníka v inorder uspořádání, ukažte, že má amortizovaně konstantní složitost. Dostanete N intervalů. Najděte z nich ten, který proniká největší množství jiných intervalů. Ukažte, že N přičtení jedničky k C-cifernému číslu trvá O(N+C). Vymyslete způsob, jak implementovat přičítání a odečítání jedničky tak, aby N operací trvalo Ο(N+C). Je dané K. Načítejte dál N čísel. Vždy po načtení jednoho čísla vypište, jaký je nejmenší rozdíl nějakých z K předchozích čísel. Implementujte MTF v co nejlepším čase.
19. května 2009	Řešené příklady: V posloupnosti nezáporných čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K. V posloupnosti celých čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K. V daném stromě s hranami ohodnocenými celými čísly a_i najděte souvislou cestu se součtem rovným danému K. Rozmyslete si implementaci hešovacích tabulek, které rostou / zmenšují se podle aktuální obsazenosti.

Zápočtové práce (25. 05. 2018)

Jméno Specifikace Zápočet

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.

Zpět