Cvičení z Algoritmů a datových struktur I v LS 12/13

Vedl jsem cvičení k přednášce ADS I Martina Mareše v pátek od 9:00 v S7. Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz..

Co jsme dělali

22. 2. Probrali jsme, jakými způsoby porovnávat algoritmy. Dále jsme zopakovali výpočetní model RAM a naprogramovali v něm třídění vkládáním. Nakonec jsme bádali, co dělají následující funkce a jak rychle (funkce g bude dodělána příště):
  • f(x,y) = if x==0: return y
             else: return f((x & y) << 1, x ^ y)
  • g(x,y) = if y==0: return 0
             else if sudé(y): return 2 * g(x, y/2)
             else: return 2 * g(x, y/2) + x
1. 3. Analýza funkce g z minula. Dále jsme definovali asymptotickou notaci (O, Ω, Θ, o, ω) a porovnávali různé funkce. Nakonec jsme se rozebírali hledání největšího společného dělitele – půlícím algoritmem a Euklidovým algoritmem.
8. 3. Nejprve jsme dokazovali složitost O(N log N) pro Eratosthenovo síto (důkaz O(N log log N) od Martina Mareše). Pak jsme zopakovali prohledávání do šířky (BFS) a hledali nejkratší cestu k pokladu v různých verzích bludiště ve čtvercové síti:
  • jen se zdmi,
  • se zdmi a sutinami (těmi jdeme třikrát déle),
  • se zdmi a krumpáčem na prokopávání zdí (chceme co nejméně použití krumpáče a druhotně nejkratší cestu),
  • se zdmi, dveřmi třech barev (R, G, B) a klíči třech barev (dveřmi projdeme jen, když už jsme sebrali klíč stejné barvy).
15. 3. Zopakovali jsme prohledávání do hloubky a rozebrali algoritmus na hledání komponent silné souvislosti. Dále jsme hledali artikulace a testovali polosouvislost.
22. 3. Dokončení hledání artikulací. Hledání nejkratších cest v ohodnocených grafech bez záporných cyklů: obecný relaxační algoritmus, Bellman-Fordův algoritmus a jejich vlastnosti.
29. 3. Znovu jsme hledali nejkratší cesty v ohodnocených grafech bez záporných cyklů, tentokrát Dijkstrovým algoritmem. Jak se Dijkstra chová na grafech se zápornými hranami (ale bez záporných cyklů), Dijkstra na grafech, kde hledáme nejspolehlivější cestu (součinem pravděpodobností hran). Dědeček měnil měny až vyměnil aneb když máme převodní kurzy měn, jak zjistit, jestli můžeme převáděním měn vydělat. Představení Floyd-Warshallova algoritmu na nalezení délky nejkratších cest mezi všemi dvojicemi vrcholů a jak do něj doplnit konstrukci těch nejkratších cest.
5. 4. Minimální kostry s panem Jarníkem, Borůvkou a Kruskalem. Rozebrali a dokázali jsme, jaké algoritmy budou fungovat, když mohou být váhy hran stejné. Kontrahující Borůvkův algoritmus je lineární pro rovinné grafy. Algoritmus pro váhy hran z množiny 1, 2, ... K v O(NK + M) a amortizovaná složitost.
12. 4. Minimální kostry (MK) podruhé. Co se stane s MK, když se změní váha jedné hrany a jak případně přepočítat kostru. Jak najít hrany, které jsou ve všech, v některých či v žádné MK, pokud váhy mohou být stejné (ukázali jsme O(mn) algoritmus, ale složitost lze srazit i na O(m) pomocí kontrakcí). Dále jsme si ukázali obecný hladový algoritmus, jehož speciálním případem je Kruskalův algoritmus, a proč nefunguje na problém batohu. Huffmanovo kódování jako další příklad hladového přístupu. Nakonec jsme hledali topologické uspořádání (v orientovaných acyklických grafech) pomocí odtrhávání vrcholů a pak i pro případ, že vrcholy jsou ve dvou množinách a ve výsledném uspořádání chceme minimalizovat počet změn mezi těmito množinami.
19. 4. Binární vyhledávací stromy (BVS) – hledání následníka, průchod BVS z minima, úprava, abychom mohli hledat k-tého nejmenšího. Počítání inverzí v permutaci. Medián dvou setříděných polí (u nichž známe délku) rychleji než lineárně.
26. 4. Cvičil Martin Mareš: nejdelší posloupnost bez opakování prvků, intervalové stromy pro počítání minima z intervalu.
3. 5. Mazání v červeno-černých stromech, hledání cesty s daným součtem na cestě a ve stromě. Problém tiskařského šotka, aneb která slova v editační vzdálenosti jedna od daných slov se vyskytují ve slovníku.
10. 5. Cvičil Martin Mareš: metoda rozděl a panuj (počítání inverzí v posloupnosti, hledání dvou nejbližších bodů v rovině, ...).
17. 5. Aplikace trií: hledání triád mezi kartami a morseovkabezoddělovačů. Počítání různých podřetězců délky k pomocí trií a trochu efektivněji pomocí hešování.
24. 5. Řešení rekurencí časových složitostí algoritmů typu rozděl a panuj pomocí stromu rekurze, např. T(n) = 2T(n/2) + Θ(n log n) nebo T(n) = T(n/2) + T(n/3) + Θ(n).

Domácí úkoly

Zápočet je za 100 bodů z domácích úkolů. Ty budou průběžně zadávány na cvičeních a po 14 dnech od zadání k nim řeknu na cvičení nápovědu. Po nápovědě jsou příklady jen za polovinu níže uvedených bodů.
Datum Jméno Body Zadání
22. 2. soucet 8 Na vstupu je seřazené pole délky N a číslo K. Vymyslete algoritmus, který v poli najde co nejefektivněji dvojici čísel, jež mají součet přesně K, případně vrátí, že tam taková dvojice není. Pokud je jich tam více, stačí vrátit jednu libovolnou.
podmatice 10 Dostanete celočíselnou matici s M řádky a N sloupci. Jak v ní najít co největší souvislou čtvercovou nulovou podmatici? Tedy největší čtverec, který obsahuje samé nuly.
Jiná formulace: máte černobílý obrázek zadaný jako dvourozměrné pole nul a jedniček a chcete v něm najít největší černý čtverec.
fceH 5 Co dělá následující funkce a jak rychle v závislosti na velikosti čísel x a y? (Předpokládejte, že y je větší než 0.)
h(x,y) = if x<y: return (0, x)
         else: (a,b) <- 2 * h(x/2, y)
               if liché(x): b <- b + 1
               if b ≥ y: a <- a + 1, b <- b - y
               return(a, b)
1. 3. mnohoúhelník 8 Máte zadaný konvexní mnohoúhelník s N vrcholy v poli souřadnic vrcholů – vrcholy jsou v pořadí, jak leží na obvodu (třeba po směru hodinových ručiček). Na začátku pole je nejvyšší vrchol mnohoúhelníku (ten s největší souřadnicí y). Nalezněte nejnižší vrchol (s nejmenší souřadnicí y). Vstup je již načten v poli, takže to jde lépe než lineárně.
kopec 8 Variace na úlohu z první přednášky: najděte v posloupnosti co nejdelší kopec, tedy podposloupnost, která nejdříve ostře roste a pak ostře klesá. Stačí v O(N2), ale popište celý algoritmus.
síto 11 Eratosthenovo síto je algoritmus na hledání prvočísel mezi čísly 2 až N. Používá pole A, v němž si pamatuje, jestli daný prvek ještě může být prvočíslem nebo už ne. Pak postupně prochází pole, a když narazí na prvek, který může být prvočíslem (což pozná z pole A), pro každý jeho násobek do pole zapíše, že už nemůže být prvočíslem. V podstatě tedy "vyškrtává" násobky prvočísel. Pseudokód:
sito(x,y):
  A = pole délky N inicializované 1
  for i = 2 to N:
    if A[i] == 1:
      print i // i je prvočíslo
      for j = 2*i to N step i // for cyklus od 2*i do N, ale skáče se po i
        A[j] = 0
Eratosthenovo síto má složitost O(N log log N), což není jednoduché dokázat, ale není těžké ukázat O(N log N). Bude rozebráno na cvičení 8.3.
Úkol: upravte Eratosthenovo síto, aby si vystačilo s pamětí O(N1/2), a přitom nebylo asymptoticky pomalejší.
8. 3. síto na RAMu 8 Naprogramujte Eratosthenovo síto na RAMu. Popis RAMu v poznámkách z přednášky před dvěma lety. Složitost a správnost není třeba zdůvodňovat. Úloha je bez nápovědy, tedy pořád za 8 bodů.
hloupý robot 8 Máme bludiště ve čtvercové síti o rozměrech NxN se zdmi, kterými nelze procházet. Robot se umí pohybovat jen rovně a zatočí pouze, když "narazí" do okraje bludiště nebo do zdi (dostane se na políčko sousední se zdí a je otočen směrem ke zdi). Při nárazu se může otočit i o 180°. Najděte pro robota cestu ze startu do cíle s co nejméně zatočeními.
stráž 10 Máme opět bludiště ve čtvercové síti se zdmi. Chceme najít nejkratší cestu k pokladu, aniž bychom potkali stráž (vyskytli se na stejném políčku jako ona). Stráž má zadanou trasu délky L jako posloupnost (sousedních) políček a po této trase chodí tam a zpět.
15. 3. průměr stromu 8 Na vstupu je dán neohodnocený neorientovaný strom. Zjistěte jeho průměr, což je délka nejdelší cesty ve stromě.
počet nejkratších 9 Vymyslete algoritmus na zjištění počtu nejkratších cest mezi dvěma vrcholy v neohodnoceném neorientovaném grafu.
odtrhávání 10 Mějme souvislý neorientovaný graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?
22. 3. stok 10 Mějme graf, který vznikl orientací úplného grafu (tj. mezi každými dvěma vrcholy vede hrana buď jedním, nebo druhým směrem), reprezentovaný maticí sousednosti, která už je načtena v paměti. Vymyslete algoritmus na zjištění, zda v grafu existuje univerzální stok, tj. vrchol, do kterého vedou hrany ze všech ostatních vrcholů. Snažte se dosáhnout časové složitosti O(N), kde N je počet vrcholů.
stromové městečko 10 Mějme městečko, jehož síť ulic má tvar stromu: hrany jsou ulice, vrcholy křižovatky (či slepé konce). U každého vrcholu víme, kolik peněz stojí postavit tam strážníka. Rozmyslete, jak co nejlevněji rozmístit strážníky tak, aby každá ulice byla aspoň z jedné strany hlídaná.
29. 3. ohodnocené vrcholy 8 Najděte nejkratší cestu v (neorientovaném) grafu, kde jsou nezáporně ohodnocené vrcholy. (Délka cesty je součet ohodnocení na cestě.)
dijkstra 10 Mějme graf s hranami ohodnocenými přirozenými čísly od 1 do K. Upravte Dijkstrův algoritmus, aby měl časovou složitost O(KN + M). Jeden bonusový bod získáte za paměťovou složitost O(K), když se nezapočítá paměť na uložení grafu. (Nebo vymyslete jiný algoritmus se stejnou nebo lepší složitostí :-)
housenka 11 Housenka je graf, který se skládá z těla (cesta) a štětin (listy připojené k vrcholům cesty, pro každý vrchol cesty max. jeden). Najděte v daném stromu podgraf s největším počtem vrcholů, který je isomorfní s nějakou housenkou.
5. 4. nejkratší cesty a MK 7 Dokažte či vyvraťte, že strom nejkratších cest z nějakého vrcholu obsahuje stejné hrany jako nějaká minimální kostra.
MK s listy 10 Máme dánu U jako podmnožinu vrcholů souvislého grafu. Najděte minimální kostru takovou, že vrcholy z U jsou listy této kostry. Algoritmus by měl rozpoznat situaci, že taková kostra neexistuje.
nejpropustnější cesta 10 Najděte v grafu s ohodnocenými hranami nejpropustnější cestu mezi dvěma danými vrcholy. Nejpropustnější znamená, že minimum z ohodnocení hran na cestě je maximální možné.
12. 4. barvení 6 8 Vymyslete algoritmus na barvení rovinného grafu 6 barvami. (Bude se vám hodit jedno pozorování z diskrétky.)
kontrakce a MK 10 Dokažte kontrakční lemma: Nechť G je graf, T jeho minimální kostra, e hrana ležící v T. Nechť dále G/e je graf vzniklý z G kontrakcí hrany e (se zachováním násobných hran a smyček). Potom T/e je minimální kostra grafu G/e. (Jinými slovy, minimální kostru můžeme získat tak, že uhodneme jednu hranu, která v ní leží, zkontrahujeme ji, rekurzivně najdeme min. kostru menšího grafu a tu pak "odkontrahujeme".)
19. 4. rank na BVS 7 Ukažte, jak upravit vyhledávací strom, aby navíc uměl efektivně provádět operaci Rank(x,y), která odpoví, kolik vrcholů stromu leží v intervalu [x,y]. Složitost všech operací včetně této by měla být O(hloubka).
následníci 9 Mějme vyhledávací strom s n vrcholy. Dokažte, že začneme-li v libovolném vrcholu a pak budeme k-krát hledat následníka, potrvá to O(k + hloubka stromu).
intervaly 11 Dostanete množinu intervalů na přímce. Spočítejte, kolik dvojic intervalů se protíná.
26. 4. minimový strom 10 Definujme minimový strom takto: v kořeni je minimum posloupnosti, levý podstrom je minimový strom prvků nalevo od minima, pravý analogicky. Vymyslete algoritmus, který v čase O(n) takový strom sestrojí.
minima 8 Vymyslete datovou strukturu, která si udržuje posloupnost čísel a umí operace "změn číslo", "spočítej minimum intervalu" a "sniž všechny hodnoty v intervalu o dané delta". Vše v O(log n).
závorky 12 Je dána posloupnost levých a pravých závorek délky N. Vymyslete datovou strukturu, která umí operace "otoč závorku na pozici i" a "zjisti, jestli je posloupnost dobře uzávorkovaná".
3. 5. abjoin 10 Nechť A, B jsou dva (a,b) stromy takové, že všechny kliče v A jsou menší než všechny klíče v B. (Mohou mít však různé velikosti.) Vymyslete algoritmus, který oba stromy v logaritmickém čase sloučí do jednoho.
četnost 7 Je dán text rozdělený na slova. Spočtěte četnost jednotlivých slov.
přesmyčky 10 Je dán slovník a seznam slov. Ke každému slovu ze seznamu najděte všechny přesmyčky (anagramy neboli permutace písmen), které se vyskytují ve slovníku.
10. 5. mergesort 8 Vymyslete a popište, jak naprogramovat MergeSort bez rekurze.
postfix 10 Máme výpis vrcholů binárního stromu v infixové a prefixové notaci (vrcholy jsou jednoznačně označené čísly). Úkolem je vymyslet algoritmus, který vypíše vrcholy stromu v postfixové notaci. (Stačí v čase O(N log N).) Prefixová notace znamená, že nejprve vypíšeme kořen, pak rekurzivně levý podstrom a rekurzivně pravý podstrom. Podobně v infixové notaci vypíšeme nejdříve levý podstrom, pak kořen a pravý podstrom a v postfixové oba podstromy a až nakonec kořen. Příklad: Pro strom s prefixovým výpisem 16 11 19 3 42 a infixovým 11 16 3 19 42 bude postfixový výpis 11 3 42 19 16.
17. 5. rýmy 7 Máme slovník a chceme vymyslet datovou strukturu, která k zadanému slovu S najde nejlepší rým – slovo ze slovníku s nejdelším společným suffixem (příponou) se zadaným slovem S. Pokud je řešení více, lze vypsat libovolné. Bonus 3 body za to, když nalezený nejlepší rým bude lexikograficky nejmenší (mezi všemi nejlepšími rýmy).
zapomětlivec 10 Zapomětlivec má seznam telefonních čísel, která si chce zapamatovat. Zároveň si pamatuje seznam nějakých slov a chce tedy ke každému telefonnímu číslu přiřadit nějaké slovo, aby když to slovo zapíšeme na klávesnici mobilu, použijeme k tomu číslice z daného telefonního čísla (opakovaný stisk jedné klávesy zaznamenáme třeba jen jednou). Tedy např. "ahoj" odpovídá na většině mobilů číslu 2465. Technické detaily jako rozložení písmen na klávesnici není třeba řešit.
24. 5. turista 6 Turista si na svém dlouhém N-denním výletě každý den poznamená, jaké celkové převýšení od rána do večera ušel (začne dejme tomu u moře, tj. ve výšce 0). V jaké výšce spal nejčastěji?
spoják 9 V paměti je jednorozměrný spojový seznam čísel, přičemž máte ukazatel na jeho první prvek. Úkolem je setřídit spoják s konstantní pomocnou pamětí (tj. použít jen konstantně mnoho proměnných pro přeskládání spojáku).
manhattan 10 Manhattan je tvořen pravoúhlou sítí ulic o rozměrech M krát N. Ulice vedoucí přibližně severojižně se jmenují avenues a na ně jsou kolmé streets (ulici Broadway vedoucí šikmo přes celý Manhattan zanedbáme). Na Manhattanu se každou chvíli něco děje a to něco je určeno dvojicemi (čas, křižovatka). Navrhněte trasu pro fotografa místního bulvárního tisku tak, aby začala i skončila v redakci (bod (0,0)) a v čase každé události se fotograf nacházel na stejné avenue nebo street jako ona událost.

Není-li řečeno jinak, je úkolem vymyslet asymptoticky co nejrychlejší algoritmus řešící úlohu. Kromě slovního popisu algoritmu v řešení zdůvodněte jeho správnost a určete časovou a paměťovou složitost. Program či pseudokód není třeba, ale může se hodit pro doplnění popisu (a na procvičení programování :-)

Úkoly je možné posílat emailem na paulie (zavináč) atrey.karlin.mff.cuni.cz. nebo odevzdávat před cvičením napsané na papír (v tom případě prosím napište na papír i svůj email, abych na něj mohl poslat případné připomínky).

Body za úkoly

Tabulku jsem ze stránek smazal, ale mám ji zaarchivovánu.