Cvičení z Algoritmů a Datových Struktur I

V LS 2010/2011 vedu jedno ze cvičení ke své přednášce z ADS1.

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

Účast na cvičení je polehčující okolností (kdo bude na cvičení aktivní, může řešit jednodušší úlohu, případně mu ji mohu odpustit).

Co jsme dělali

datum téma
24. 2. Rekurzivní hádanky. Aritmetika s dlouhými čísly. Na rozmyšlení: Jak dopadne sčítání zleva doprava (nebo v libovolném jiném pořadí)? Proč fungují dvojkové doplňky a jak vypadá jejich analogie v jiných soustavách? Je lepší školní násobení a dělení, nebo naše rekurzivní?
3. 3. Házení vajíčky z balkonu. Programování na RAMu: hledání maxima, třídění.
10. 3. Druhá odmocnina na papíře. Asymptotické porovnávání funkcí.
17. 3. Úlohy o stromech: průměr, centrum, největší housenka, rozmisťování posádek, separátorová dekompozice.
24. 3. Krysaři: V jakém pořadí odtrhávat vrcholy, aby byl graf stále souvislý? Hledání mostů a artikulací. Úkoly na příště: překlepová vzdálenost, nejmenší kladné číslo z nul a jedniček dělitelné daným K, dva roboti v bludišti.
31. 3. Cvičil Tomáš Valla: Vrcholová pokrytí a nezávislé množiny ve stromech, bludiště s dveřmi a klíči, hledání souvislých oblastí v bitmapě (i s kompresí).
7. 4. Počet cest v acyklickém grafu, počet nejkratších cest v grafu obecném. Vyvážená a skoro vyvážená orientace grafu.
14. 4. Dijkstrův algoritmus: proč selže na záporných hranách, proč nepomůže přičíst ke všem hranám konstantu. Jak se chová obecný algoritmus na nejkratší cesty, pokud si otevřené vrcholy ukládáme do fronty či zásobníku. Nejširší a nejpravděpodobnější cesta.
21. 4. Konverze měn. Jak se změní minimální kostra po změně jedné hrany grafu. Jak najít druhou nejmenší kostru? Lemma o cyklech a inverzní Kruskalův algoritmus (odebírání hran od nejtěžší).
28. 4. Zase ty kostry… Minimální kostra v grafech s vahami {1,…K}: kontrakce hran či přihrádková struktura pro Jarníkův algoritmus. Jako desert servírujeme kontrahující Borůvkův algoritmus.
5. 5. Vyvažování stromů pomocí přestavování podstromů. Hledání k-tého nejmenšího prvku ve stromu. Počet inverzí v permutaci. Intervalové stromy.
12. 5. Roztržitý profesor: seznamy se zkratkami, vyhledávací stromy, Fenwickovy stromy.
19. 5. Úlohy skoro zkouškové:
  • Je dána matice A přirozených čísel, která v každém řádku i sloupci roste. Najděte (i,j) takové, že Ai,j=i+j. (Jednodušší verze: matice má jen jeden řádek.)
  • Mějme posloupnost přirozených čísel. Zjistěte, zda jsou všechna čísla navzájem různá.
  • Mějme strom s ohodnocenými hranami a číslo X. Existuje ve stromu cesta, se součtem ohodnocení hran přesně X? (Jednodušší verze: strom se nevětví.)
  • Navrhněte algoritmus, který dokonale vyváží daný vyhledávací strom bez použití pomocného pole.
  • Navrhněte datovou strukturu, která bude reprezentovat posloupnost a bude umět přidat prvek na konec a vrátit minimum z posledních K prvků. (Kde K zvolíme pevně při inicializaci struktury.)
  • Jiná datová struktura: vyhledávací strom, který si pamatuje svou historii a umí odpovídat na dotazy typu "byl v množině prvek X v čase T?".
  • Metro pro krtky: mějme množinu tětiv kružnice. Kolik mají průsečíků? Slibujeme, že v každém vnitřním bodě kruhu se protínají nejvýše 2 tětivy.
  • Bulvár: 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.
  • Dokažte, že reprezentujeme-li množiny binárními vyhledávacími stromy, nelze 2 množiny sjednotit v čase lepším než lineárním. (Hint: sudá a lichá čísla)
26. 5. Rozdělování a panování. Propojování drátů. Inverze v permutacích ještě jednou. Rekurence nejen kuchařkové:
  • T(n) = 2T(n/2) + Θ(n2)
  • T(n) = 2T(n/3) + Θ(n) … počítáme černou barvu ve fraktálu
  • T(n) = T(n/2) + Θ(1) … binární vyhledávání
  • T(n) = 2T(n) + Θ(n log n) … když průběžně třídíme
  • T(n) = n1/2 T(n1/2) + Θ(n)

Zápočtová práce

Zápočtová práce obnáší vyřešení nějaké algoritmické úlohy. Chci od vás popis algoritmu, rozbor správnosti a časové i paměťové složitosti, velice doporučuji napsat i program a nepoužívat v něm knihovní funkce, u kterých netušíte, jak jsou implementované. Dobrou inspirací k tomu, jak o algoritmech psát, může být třeba archiv KSP nebo MO-P.

Pokud vás žádné téma nenapadá, můžete využít služeb našeho nápadníku. Není sice tak sladký jako polibek informatické múzy, ale v nouzi také poslouží.

Domácí úkoly

Během semestru byste měli naprogramovat dvě úlohy (jednoduché variace na látku z přednášky, které aspoň stručně probereme na cvičení) a odevzdat je v CodExu pro Programování 1/2. Z každé musíte mít plný počet bodů.

Nejkratší cesty mezi matfyzem a menzou

Roztržitý profesor

Stránku spravuje Martin Mareš