Cvičení z Algoritmů a datových struktur I v LS 14/15 (středa 17:20, S11)

Vedu cvičení k přednášce ADS I Martina Mareše ve středu od 17:20 v S11. Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz.
Potřebujete-li konzultaci, ozvěte se na stejnou emailovou adresu. Od 6.6. však budu pryč až do začátku července, nicméně budu na internetu. Víc jak půlku července (od 11.) budu také pryč, navíc mimo dosah internetu, tak budu rád, pokud dořešíte zápočet do konce června.

Zápočet je třeba dořešit do 23. září.

Co jsme dělali

18. 2. Diskuse o porovnávání algoritmů, hledání souvislé nulové podmatice v zadané matici (zatím jsme se dostali na O(N2M2)) a rekurzivní hádanky (funkce g bude dodělána příště).
25. 2. Analýza funkce g z minula. Dále jsme definovali asymptotickou notaci (O, Ω, Θ, o, ω) a porovnávali různé funkce. Nakonec jsme dokazovali, že Eratosthenovo síto má časovou složitost O(N log N). (Lze dokázat O(N log log N), viz třeba text od Martina Mareše.)
4. 3. Prohledávání do šířky (BFS) na grafech a ve stavovém prostoru. Hledání komponent souvislosti, test, jestli je zadaný graf strom nebo jestli je bipartitní. Hledání nejkratší cesty k pokladu v různých verzích bludiště ve čtvercové síti (v základu jsou zdi, hrdina a poklad): se sutinami, s dveřmi a klíči tří barev a s krumpáčem (bude doděláno příště).
Slíbené Eratosthenovo síto na RAMu
11. 3. Řešení bludiště s krumpáčem. Prohledávání do hloubky (DFS) na grafech, opakování klasifikace hran (stromové, zpětné, dopředné a příčné), hledání mostů a topologického uspořádání. Je prohledávání do šířky se zásobníkem stejné jako prohledávání do hloubky? Hledání artikulací a topologického uspořádání v orientovaných acyklických grafech odtrháváním zdrojů (vrcholů se vstupním stupněm 0).
Hledání mostů a artikulací ve skriptech (str. 14)
18. 3. Rekurzivní výpočet na stromu: největší nezávislá množina a vrcholové pokrytí nejmenší ceny (aka rozmisťování strážníků do vrcholů stromu, aby každá ulice (hrana) byla hlídaná).
25. 3. Jednotažky aneb hledání Eulerovský tahů v grafech se všemi stupni sudými pomocí slepování hladových řešení (zmíněno, že jde použít upravené DFS jdoucí každou hranou právě jednou s výpisem hran v obráceném pořadí navštěvení). Komponenty silné souvislosti orientovaného grafu a Tarjanův algoritmus. Testování polosouvislosti a rozdíly mezi slabou, polo- a silnou souvislostí orientovaného grafu.
1. 4. Relaxační algoritmus, jak hledat výsledné nejkratší cesty (když se zastaví), a rozbor, proč se zastaví, když v grafu není záporný cyklus. Dijkstrův algoritmus a jeho chování na grafech se zápornými hranami a proč nepomůže přičtení konstanty k délce každé hrany. Nejpravděpodobnější cesta zlogaritmováním pravděpodobností a přenásobením -1. Podobně hledání, jestli lze ve směnárně vydělat převáděním měn, pomocí převodu na hledání záporného cyklu v grafu.
8. 4. Hledání nejkratších cest mezi všemi dvojicemi vrcholů a Floyd-Warshallův algoritmus (na orientovaných grafech bez záporných cyklů). Jak vypisovat nejkratší cesty a jak algoritmus upravit, aby našel délku nejkratšího cyklu. Jarníkův algoritmus s vahami hran, které nemusí být různé, a jeho implementace s haldou.
15. 4. Dokončení min. koster: Borůvkův algoritmus a jak selže, když povolíme stejné váhy hran; naopak Kruskalův algoritmus funguje. Binární vyhledávací stromy (BVS): hledání následníka, průchod BVS z minima pomocí operace následníka je lineární a úprava, abychom mohli hledat k-tý nejmenší prvek.
22. 4.
  • Součtový intervalový strom nad polem.
  • Počítání inverzí v posloupnosti (různých čísel, tj. např. v permutaci) pomocí binárních vyhledávacích stromů a pomocí metody rozděl a panuj (úpravou MergeSortu).
  • Medián dvou setříděných posloupností v logaritmickém čase.
29. 4. (a,b)-stromy: minimální a maximální hloubka a jak z nich mazat. Amortizovaná složitost: neformální definice a důkaz, že přičtení 1 k n-bitovému binárnímu číslu je amortizovaně O(1) pomocí penízkové metody. Penízková metoda na vkládání do (a,b)-stromu.
6. 5. Trie (písmenkové stromy) a komprimované trie. Aplikace trií: mnemotechnické pomůcky pro telefonní seznam a triády. Zmínka o hledání počtu různých podřetězců délky k v řetězci délky n (s triemi O(kn), hešováním průměrně O(n), což bude doděláno příště).
13. 5. Rektorský sportovní den (cviko odpadá)
20. 5. Počet různých podřetězců délky k v řetězci délky n za pomoci hešování (bez důkazu, že s velkou pravděpodobností dostaneme správný výsledek). Rozděl a panuj: Pro zadané pole A s ostře rostoucí posloupností celých čísel hledání indexu i takového, že A[i] = i. Počítání rekurencí pomocí stromu rekurze:
  • T(n) = 2T(n/2) + Θ(n2)
  • T(n) = 2T(n/3) + Θ(n)
  • T(n) = 3T(n/2) + Θ(n)
  • T(n) = T(n/2) + Θ(1)
  • T(n) = 2T(n) + Θ(n log n)
  • T(n) = n1/2 T(n1/2) + Θ(n)

Zápočet

Zápočet je za 100 bodů z domácích úkolů, které budu průběžně zadávat na cvičeních. Po 14 dnech od zadání jsou úkoly za polovinu níže uvedených bodů a taky po 14 dnech k nim mohu říct na požádání nápovědu (buď po cvičení, nebo emailem).

Do řešení byste měli především napsat slovní popis algoritmu spolu se stručným zdůvodněním správnosti (není třeba formální důkaz) a časovou a paměťovou složitostí. Program nebo pseudokód není povinný, může sloužit k lepšímu pochopení (nebo k procvičení programování :-)

Úkoly odevzdávejte nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu). Můžete mi odevzdávat i papíry s ručně psaným řešení, ale pište prosím čitelně (a přidejte svůj email, abych na něj mohl poslat případné připomínky). Nafocený text psaný rukou mi neposílejte.

Datum Jméno Body Zadání
18. 2. soucet 8 Na vstupu je setříděné 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 takových dvojic více, stačí vrátit jednu libovolnou.
sqrt 7 Jak spočítat celočíselnou druhou odmocninu? Tím pro dané x myslíme přirozené číslo y takové, že y2≤ x < (y+1)2
laser 10 V řadě stojí N budov s h1, ..., hN patry a je potřeba je všechny zničit. K tomu máte doma eliminační laser, jímž na jeden výstřel můžete buďto zničit celou jednu konkrétní budovu, nebo celé jedno patro u všech budov (při zničení patra L se všem budovám s počtem pater alespoň L zmenší počet pater o 1). Na kolik nejméně výstřelů je možné eliminovat všechny budovy? (Pozor na to, že počet pater může být o hodně vyšší než N.)
25. 2. sito 10 Upravte Eratosthenovo síto, aby si vystačilo s pamětí O(sqrt(n)), a přitom nebylo asymptoticky pomalejší.
ram 9 Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti. Popis RAMu.
Úkol je za plný počet do konce výuky (tj. do začátku zkouškového).
podmatice 10 Pro (celočíselnou) matici s M řádky a N sloupci nalezněte největší souvislou (obdélníkovou) nulovou podmatici, tedy největší obdélník, 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ý obdélník.
Na cvičení jsme si ukazovali řešení v O(MN min(M,N)), najděte řešení v O(MN).
4. 3. stráž 10 Máme bludiště ve čtvercové síti o rozměrech NxN se zdmi, hrdinou a pokladem. Chceme najít nejkratší cestu hrdiny k pokladu, aniž by potkal stráž (vyskytl 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. (L si představujte jako malé číslo.)
hloupý robot 8 Máme opět bludiště ve čtvercové síti 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.
šéf 9 V paměti máte matici sousednosti orientovaného grafu G. Šéf je vrchol, ze kterého vede hrana do všech ostatních vrcholů a do něj samotného nevede žádná hrana. Najděte v G šéfa, nebo řekněte, že tam žádný šéf není.
11. 3. odtrhávání 9 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ý?
nezávislé 10 Podmnožina vrcholů grafu je nezávislá, pokud mezi žádnými dvěma vrcholy této podmnožiny nevede hrana. Jak pro daný strom spočítat, kolik je v něm nezávislých množin. (Výsledek bude exponenciální v počtu vrcholů, ale pro jednoduchost můžete i s takto velkými čísly počítat v O(1).)
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ě.
18. 3. # nejkratších 10 Je dán neohodnocený orientovaný graf a počáteční vrchol. Pro všechny ostatní vrcholy spočítejte, kolik do nich z počátečního vrcholu vede nejkratších cest. (Výsledek může být exponenciální v počtu vrcholů, ale pro jednoduchost můžete i s takto velkými čísly počítat v O(1).)
barvení 6 10 Máme rovinný graf a chceme jeho vrcholy obarvit 6 barvami. Algoritmus by měl mít lineární časovou složitost. (Za bonus barvení 5 barvami. Algoritmus už nemusí být lineární, ale čím rychlejší, tím lépe.)
unique 9 Vymyslete, jak poznat grafy, které lze topologicky uspořádat právě jedním způsobem.
25. 3. vyznačené na cyklu 7 Mějme orientovaný graf, v němž jsou některé vrcholy vyznačené. Jak poznat, jestli nějaký vyznačený vrchol leží na cyklu?
housenka 11 Housenka je neorientovaný strom, který se skládá z těla (cesty) 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.
d-degenerovanost 14 O grafu řekneme, že je d-degenerovaný, pokud existuje pořadí odtrhávání vrcholů takové, že každý odtrhávaný vrchol má aktuální stupeň maximálně d. Například stromy jsou 1-degenerované (trháme od listů) a rovinné grafy jsou 5-degenerované. Pro zadaný neorientovaný graf najděte nejmenší d takové, že G je d-degenerovaný. Nebojte se poslat i méně efektivní řešení než lineární, bude za něj nemalá část bodů.
1. 4. nejpropustnější cesta 8 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é. Můžete si to představit tak, že ohodnocení znamená šířku hrany a hledáme tedy nejširší cestu.
K-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í :-)
4-cyklus 8 Mějme ohodnocený orientovaný graf. Chceme v něm najít nejkratší cyklus ze čtyř hran v čase lepším než Θ(n^4).
8. 4. FW a záporné cykly 8 Upravte Floydův-Warshallův algoritmus, aby zjistil, zda v grafu existuje záporný cyklus (se zachování časové složitosti).
MK s listy 8 Máme dánu U, podmnožinu vrcholů souvislého grafu. Najděte minimální kostru takovou, že vrcholy z U jsou listy této kostry (ale i jiné vrcholy mohou být listy). Algoritmus by měl rozpoznat situaci, že taková kostra neexistuje.
relax exponenciální 10 Ukažte, jak pro každé n sestrojit ohodnocený graf na řádově n vrcholech, na kterém relaxační algoritmus s nešikovným pořadím relaxací provede řádově cn kroků (pro nějaké c > 1). Další 4 body, pokud to dokážete s relaxováním vrcholu s nejnižším ohodnocením jako v Dijkstrovi.
15. 4. vyvážení 10 Vymyslete algoritmus, který v lineárním čase přebuduje binární vyhledávací strom na dokonale vyvážený s pomocnou pamětí O(log n). Nemůžete si tedy pořídit ještě jednu kopii prvků. (Další 2 body, pokud si vystačíte s konstantní pomocnou pamětí.)
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).
22. 4. intervalový strom 8 Implementujte operace s minimovým intervalovým stromem (v uzlu není součet intervalu, ale minum): čtení prvku, zápis prvku a výpočet minima přes interval indexů. Stačí v pseudokódu.
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á".
k-tá permutace 10 Uvažme posloupnost všech permutací na množině 1,…,n uspořádanou lexikograficky (slovníkově). Jak nalézt k-tou permutaci v této posloupnosti?
29. 4. 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 sloučí do jednoho v logaritmickém čase vůči počtu jejich prvků (krát nějaká funkce parametrů a, b).
Všechny úkoly z 29.4. jsou za plný počet bodů až do 20.5.
čítač 10 Uvažme n-bitový čítač, který podporuje operace INC a DEC (přičtení a odečtení 1). Modifikujeme ho tak, že každý bit může nabývat hodnot 0, +1 a -1. Ukažte, že v této reprezentaci je amortizovaná složitost obou operací O(1), tj. k operací trvá O(k), když začneme s hodnotou nula.
6. 5. úsek bez opakování 10 Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, ve kterém se žádné číslo neopakuje.
Tento a následující úkoly jsou za plný počet bodů až do konce června.
přesmyčky 11 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.
nejčastější 8 Je dán text rozdělený na slova. Najděte nejčastější slovo.
20. 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).
komprimovaná trie 9 Naprogramujte komprimovanou trii, která umí (alespoň) operace INSERT, FIND a DELETE, ale stačí pro anglickou abecedu. (Chcete-li ji naprogramovat v jiném jazyce než C, C++, C#, Python, Java a Pascal, tak mi napište.)
fronta 9 Ukažte, jak pomocí dvou zásobníků simulovat frontu s amortizovaně konstantní časovou složitost na operaci (za předpokladu, že zásobník pracuje v konstantním čase).
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.

Body za úkoly

Již nejsou vidět.