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

Cvičení se koná v pondělí v 12:20 v S6.

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

Zápočet získáte za odevzdání dvou časově omezených úkolů a vypracování zápočtové práce. Ta by měla obsahovat popis některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud. Takový text by měl obsahovat to, jak algoritmus funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:

V termínu odevzdat první a druhý domácí úkol. Úkoly budou oznámeny na cvičení a na webových stránkách alespon s měsíčním předstihem.
Domluvit se se mnou do konce semestru, tj. do 27. 5. 2011 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. Jedno téma je nanejvýš pro 3 lidi, aby se témata moc neopakovala.
Poslat mi zápočťák. Většinou po krátké iteraci dostanete zápočet, ale mohu požadovat i osobní předvedení.

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

Seznam domácích úkolů

Domácí úkoly se odevzdávají v CodExu, ve skupině ADS1-Straka. Do této skupiny vás mohu přiřadit jenom já, takže až budete mít v CodExu účet, napište mi mail, přiřadím vás do ní. Úkoly řešte jednotlivě, takže neodevzdávejte cizí řešení, protože je budu ručně kontrolovat. Pokud na nějaké zkopírované narazím, nikomu z účastníků nedám zápočet.

První domácí úkol je úloha Vrabci na střeše. Musíte ji odevzdat do 1. května 23:59. Pro uznání úkolu musíte získat 100 ze 100 bodů (tj. na všech deset z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Obsahují jedno ukázkové řešení, ale správných řešení je samozřejmě víc. Časový limit v CodExu je 2s na každý vstup, paměťový je 64MB. Pokud budete mít po týdnu programování stále problém, je čas mi napsat.
Druhý domácí úkol je úloha Roztržitý profesor. Musíte ji odevzdat do 5. června 23:59. Pro uznání úkolu musíte získat 100 ze 100 bodů (tj. na všech deset z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Časové limity v CodExu jsou 1s v C/C++/Pascal, 1.5s v C#. Paměťový limit je 64MB.

Načítání vstupu v C# v CodExu

Pro načítení vstupu v C#, který se skládá z mnoha čísel, je možné použít třídu Reader.cs. Tu najdete v CodExu v sekci 'Uvítací stránka'. V CodExu je váš program s touto třídou kompilován automaticky, stačí přidat

using
  CodEx

, doma ji musíte přikompilovávat ručně. Pomocí ní můžete načíst další číslo ze standardního vstupu jako Reader.Console().Int(). Kromě čísel jde načítat ještě Char, Double, Word a Line.

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

Obsah cvičení (03. 10. 2011)

Datum Obsah
21. února 2011 Řešené příklady:
Definice asymptotické časové složitosti, symbolu Ο a Θ.
Určete, co dělají následující funkce a jak dlouho jim to trvá:
f(x,y) = if x==0 then y
                 else f((x AND y) * 2, x XOR y)
g(x,y) = if y==0 then 0
                 else 2 * g(x, y/2) + x * (y AND 1)
h(x,y) = if x<y then (0,x)
         else (a,b) <- 2 * h(x/2, y) + (0, x AND 1)
              if b≥y then (a+1, b-y) else (a, b)

28. února 2011 Řešené příklady:
Máme v vajíček a panelák o N patrech. Cílem je najít na co nejméně pokusů nejnižší patro, ze kterého když hodíme vajíčko, tak se rozbije [v * N^1/v pokusů].
V matici s nulami a jedničkami najděte největší podmatici složenou za samých nul [Ο(NM)].

7. března 2011 Řešené příklady:
Mějme čísla x₁, x₂, ... x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat operaci dělení (tj. jenom násobení). Snažte se co nejvíce šetřit pamětí (čas Ο(N) a paměť Ο(N), čas Ο(N) a paměť Ο(√N), čas Ο(N log N) a paměť Ο(log N)).
Pokud byste mohli s libovolně dlouhými celými čísly pracovat v konstantním čase, navrhněte algoritmus na vynásobení dvou matic v čase Ο(n²).
Pomocí rekurze vynásobte dvě celá n-bitová čísla v čase Ο(n^{log₂ 3}).

14. března 2011 Řešené příklady:
Č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 a zdroje radioaktivity – každé políčko má konkrétní úroveň radioaktivity. Nalezněte nejkratší cestu k pokladu, na které je maximální úroveň radioaktivity co nejmenší.
Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, dveře tří barev (R, B, Y), klíče tří barev (r, b, y). 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, Minotaurus a libovolný počet mečů. Minotaurus se hýbe poté, co se pohnete vy, a jde nahoru/nikam/dolu, aby se vám přiblížil; poté jde doleva/nikam/doprava, aby se vám přiblížil. Když jít nemůže, stojí. Najděte nejkratší cestu k pokladu, na které se nepotkáte s Minotaurem, aniž byste měli meč.

21. března 2011 Řešené příklady:
V daném ohodnoceném grafu najděte kružnici délky 3 s minimálním součtem ohodnocení hran. [Ο(NM)]
V daném ohodnoceném grafu najděte kružnici délky 4 s minimálním součtem ohodnocení hran. [Ο(NM)]
V daném ohodnoceném grafu najděte kružnici délky 5 s minimálním součtem ohodnocení hran. [Ο(NM)]
V neohodnoceném stromě najděte nejdelší cestu.
V neohodnoceném stromě najděte největší housenku. Housenka je cesta, na kterou se připojují nožičky a její velikost se měří počtem jejích hran.
Království je strom s ohodnocenými vrcholy. Umistěte posádky do některých vrcholů tak, aby součet ohodnocení vrcholů s posádkami byl co největší a zároveň každá souvislá skupina posádek byla velikosti nanejvýš 3.

28. března 2011 Ř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.
Dostanete neorientovaný graf. Najděte všechny mosty, což jsou hrana, kterou když z grafu odstraníte, stane se nesouvislým.
Dostanete neorientovaný graf. Najděte všechny artikulace, což je vrchol, který když z grafu odstraníte, stane se nesouvislým.
Podobným algoritmem, tj. procházením orientovaného grafu do šířky, najděte komponenty silné souvislosti.
Obarvěte daný rovinný graf šesti barvami.

4. dubna 2011 Řešené příklady:
Obarvěte daný rovinný graf šesti barvami.
Obarvěte daný rovinný graf pěti barvami.
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.
Dostanete neorientovaný graf. Rozhodněte, zda ho lze nakreslit jedním tahem a pokud ano, najděte takový tah.

11. dubna 2011 Řešené příklady:
Popište implementaci Dijkstrova algoritmu a určete jeho složitost při použití pole, binární haldy a k-regulární haldy. [Ο(N²), Ο(M log N), Ο(M log_M/N N) pro k=m/n]
Definovali jsme amortizovanou složitost a ukázali binomiální haldy a Fibonacciho haldy.
Navrhněte, jak do Dijkstrova algoritmu zapojit zeměpisné souřadnice, pokud hledáte nejkratší cestu mezi městy.

18. dubna 2011 Řešené příklady:
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 takové, že pro každou hranu vzdálenost(u, v) - H(u) + H(v)≥0. Graf s ohodnoceními vzdálenost(u, v) - H(u) + H(v) tedy nemá žádné záporné hrany. Ukažte, že nejkratší cesty zůstanou v tomto grafu zachovány.
Dokažte funkčnosti Bellman-Fordova algoritmu.
Mějme gragf G s hranami ohodnocenými přirozenými čísly≤K. Implementujte Dijkstrův algoritmus se složitostí Ο(kN + 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.
Dokažte funkčnosti Floyd-Warshallova algoritmu.

25. dubna 2011 Velikonoce
2. května 2011 Řešené příklady:
Popište Jarníkův algoritmus pro hledání minimální kostry, a to jeho implementace se složitostmi Ο(N²), Ο(M log N), Ο(N log N + M).
Popište Kruskalův algoritmus se složitostí Ο(M log N), případně Ο(M * α(M)) pokud jsou hrany již setříděné.
Upravte algoritmus pro hledání minimální kostry, aby fungoval inkrementálně – v grafu postupně přibývají hrany a vy po každém přidání musíte říci, jak v tuto chvíli vypadá minimální kostra [Ο(N) na přidání hrany].
Nalezněte druhou nejlepší minimální kostru [Ο(N² + M)].
V posloupnosti nezáporných čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K.

9. května 2011 Řešené příklady:
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.
Zjistěte, zda se v dané posloupnosti nějaké číslo vyskytuje víckrát. [Ο(N+K) jsou-li hodnoty v rozsahu 1..K, Ο(N log N) pomocí třídění, Ο(N log N) pomocí vyvážených vyhledávacích stromů.]
Dostanete číslo K a potom postupně N hodnot. Po načtení hodnoty vypište velikost minimálního rozdílu mezi K posledně zadanými prvky. [Ο(N log K)]

16. května 2011 cvičení odpadá
23. května 2011 Řešené příklady:
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ů [26].
Z daných bodů v rovině najděte dva nejbližší [Ο(N log N)].
Bleší turnaj probíhá na svislé stěně, na které jsou vodorovné plošinky. Závod probíhá tak, že blecha padá, až dopadne na plošinku. Pak se rozhodne, zda půjde doleva nebo doprava, a jde, dokud nedojde na konec plošinky. Z ní pak seskočí a zase padá, dokud se nedostane na podlahu. Vítězí blecha, která přistane na podlaze jako první. Ovšem je nutné, aby žádná blecha nespadla z větší výšky než v blechometrů, jinak se totiž zarazí nožičkami do plošínky a v závodě končí. Najděte pro danou sadu plošinek nejkratší cestu [Ο(N log N)].

Datum	Obsah
21. února 2011	Řešené příklady: Definice asymptotické časové složitosti, symbolu Ο a Θ. Určete, co dělají následující funkce a jak dlouho jim to trvá: `f(x,y) = if x==0 then y` `else f((x AND y) * 2, x XOR y)` `g(x,y) = if y==0 then 0` `else 2 * g(x, y/2) + x * (y AND 1)` `h(x,y) = if x<y then (0,x)` `else (a,b) <- 2 * h(x/2, y) + (0, x AND 1)` `if b≥y then (a+1, b-y) else (a, b)`
28. února 2011	Řešené příklady: Máme v vajíček a panelák o N patrech. Cílem je najít na co nejméně pokusů nejnižší patro, ze kterého když hodíme vajíčko, tak se rozbije [v N^1/v pokusů]. V matici s nulami a jedničkami najděte největší podmatici složenou za samých nul [Ο(NM)*].
7. března 2011	Řešené příklady: Mějme čísla x₁, x₂, ... x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat operaci dělení (tj. jenom násobení). Snažte se co nejvíce šetřit pamětí (čas Ο(N) a paměť Ο(N), čas Ο(N) a paměť Ο(√N), čas Ο(N log N) a paměť Ο(log N)). Pokud byste mohli s libovolně dlouhými celými čísly pracovat v konstantním čase, navrhněte algoritmus na vynásobení dvou matic v čase Ο(n²). Pomocí rekurze vynásobte dvě celá n-bitová čísla v čase Ο(n^{log₂ 3}).
14. března 2011	Řešené příklady: Č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 a zdroje radioaktivity – každé políčko má konkrétní úroveň radioaktivity. Nalezněte nejkratší cestu k pokladu, na které je maximální úroveň radioaktivity co nejmenší. Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, dveře tří barev (R, B, Y), klíče tří barev (r, b, y). 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, Minotaurus a libovolný počet mečů. Minotaurus se hýbe poté, co se pohnete vy, a jde nahoru/nikam/dolu, aby se vám přiblížil; poté jde doleva/nikam/doprava, aby se vám přiblížil. Když jít nemůže, stojí. Najděte nejkratší cestu k pokladu, na které se nepotkáte s Minotaurem, aniž byste měli meč.
21. března 2011	Řešené příklady: V daném ohodnoceném grafu najděte kružnici délky 3 s minimálním součtem ohodnocení hran. [Ο(NM)] V daném ohodnoceném grafu najděte kružnici délky 4 s minimálním součtem ohodnocení hran. [Ο(NM)] V daném ohodnoceném grafu najděte kružnici délky 5 s minimálním součtem ohodnocení hran. [Ο(NM)] V neohodnoceném stromě najděte nejdelší cestu. V neohodnoceném stromě najděte největší housenku. Housenka je cesta, na kterou se připojují nožičky a její velikost se měří počtem jejích hran. Království je strom s ohodnocenými vrcholy. Umistěte posádky do některých vrcholů tak, aby součet ohodnocení vrcholů s posádkami byl co největší a zároveň každá souvislá skupina posádek byla velikosti nanejvýš 3.
28. března 2011	Ř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. Dostanete neorientovaný graf. Najděte všechny mosty, což jsou hrana, kterou když z grafu odstraníte, stane se nesouvislým. Dostanete neorientovaný graf. Najděte všechny artikulace, což je vrchol, který když z grafu odstraníte, stane se nesouvislým. Podobným algoritmem, tj. procházením orientovaného grafu do šířky, najděte komponenty silné souvislosti. Obarvěte daný rovinný graf šesti barvami.
4. dubna 2011	Řešené příklady: Obarvěte daný rovinný graf šesti barvami. Obarvěte daný rovinný graf pěti barvami. 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. Dostanete neorientovaný graf. Rozhodněte, zda ho lze nakreslit jedním tahem a pokud ano, najděte takový tah.
11. dubna 2011	Řešené příklady: Popište implementaci Dijkstrova algoritmu a určete jeho složitost při použití pole, binární haldy a k-regulární haldy. [Ο(N²), Ο(M log N), Ο(M log_M/N N) pro k=m/n] Definovali jsme amortizovanou složitost a ukázali binomiální haldy a Fibonacciho haldy. Navrhněte, jak do Dijkstrova algoritmu zapojit zeměpisné souřadnice, pokud hledáte nejkratší cestu mezi městy.
18. dubna 2011	Řešené příklady: 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 takové, že pro každou hranu vzdálenost(u, v) - H(u) + H(v)≥0. Graf s ohodnoceními vzdálenost(u, v) - H(u) + H(v) tedy nemá žádné záporné hrany. Ukažte, že nejkratší cesty zůstanou v tomto grafu zachovány. Dokažte funkčnosti Bellman-Fordova algoritmu. Mějme gragf G s hranami ohodnocenými přirozenými čísly≤K. Implementujte Dijkstrův algoritmus se složitostí Ο(kN + 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. Dokažte funkčnosti Floyd-Warshallova algoritmu.
25. dubna 2011	Velikonoce
2. května 2011	Řešené příklady: Popište Jarníkův algoritmus pro hledání minimální kostry, a to jeho implementace se složitostmi Ο(N²), Ο(M log N), Ο(N log N + M). Popište Kruskalův algoritmus se složitostí Ο(M log N), případně Ο(M α(M))* pokud jsou hrany již setříděné. Upravte algoritmus pro hledání minimální kostry, aby fungoval inkrementálně – v grafu postupně přibývají hrany a vy po každém přidání musíte říci, jak v tuto chvíli vypadá minimální kostra [Ο(N) na přidání hrany]. Nalezněte druhou nejlepší minimální kostru [Ο(N² + M)]. V posloupnosti nezáporných čísel a₁, ..., a_N najděte souvislý úsek se součtem rovným danému K.
9. května 2011	Řešené příklady: 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. Zjistěte, zda se v dané posloupnosti nějaké číslo vyskytuje víckrát. [Ο(N+K) jsou-li hodnoty v rozsahu 1..K, Ο(N log N) pomocí třídění, Ο(N log N) pomocí vyvážených vyhledávacích stromů.] Dostanete číslo K a potom postupně N hodnot. Po načtení hodnoty vypište velikost minimálního rozdílu mezi K posledně zadanými prvky. [Ο(N log K)]
16. května 2011	cvičení odpadá
23. května 2011	Řešené příklady: 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ů [26]. Z daných bodů v rovině najděte dva nejbližší [Ο(N log N)]. Bleší turnaj probíhá na svislé stěně, na které jsou vodorovné plošinky. Závod probíhá tak, že blecha padá, až dopadne na plošinku. Pak se rozhodne, zda půjde doleva nebo doprava, a jde, dokud nedojde na konec plošinky. Z ní pak seskočí a zase padá, dokud se nedostane na podlahu. Vítězí blecha, která přistane na podlaze jako první. Ovšem je nutné, aby žádná blecha nespadla z větší výšky než v blechometrů, jinak se totiž zarazí nožičkami do plošínky a v závodě končí. Najděte pro danou sadu plošinek nejkratší cestu [Ο(N log N)].

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

Výsledky úkolů se aktualizují z CodExu jednou nočně.

Jméno Úkol 1 Úkol 2 Specifikace Zápočťák Zápočet

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

Zpět