Algoritmy a datové struktury 1, cvičení jaro 2014

Cvičení vede každou středu 14:00 v S10 Tomáš Gavenčiak (gavento@ucw.cz). Cvičení volně sleduje přednášku Ondřeje Čepka.

Zápočet

Účast na cvičení není povinná. Zápočet je za zisk 100 bodů z domácích úloh případného zápočtového programu či práce.

Zápočtový program za cca 30 bodů (dle obtížnosti a kvality splnění) je implementace nějaké varianty datové struktury či algoritmu z přednášky. Jazyk je omezen jen schopnostmi cvičícího (tedy C, C++, Python, C#, Java, Pascal, Haskell, Lisp a další jsou OK), implementace musí být funkčí a obsahovat krátký popis (co a jak je implementováno) a testovací data či testovací kód (knihovna tedy nemusí řešit načítání dat ze souboru a pod.). Pokud bude téma složitější, může být práce jen teoretická (pseudokód).

Termín na domluvení programu je do 14. května června, termín odevzdání hotové verze pak konec června. Ostatní domácí úlohy mají až na výjimky termín do konce května.

Domácí úkoly

Domácích úloh bude vypsáno za cca 170 bodů, zveřejněny jsou vždy níže na stránce. Na odevzdání za plný počet bodů máte 14 dní 4 týdny (prodlouženo, protože nestíhám dost rychle opravovat domácí úkoly) od zadání (do začátku cvičení), finální termín odevzdání je konec výuky v letním semestru (konec května) krom několika posledních sérií.

Domácí úlohy odevzdávejte emailem nejlépe jako čistý text či jako PDF. Neposílejte mi fotky ručně psaného textu, ale dobře nafocené obrázky jsou v pořádku. Pokud nechcete být uvedeni ve veřejné tabulce bodů či preferujete přezdívku (nechcete třeba být vyhledatelní), napište to ke každému vašemu řešení.

V řešení domácích úloh se soustřeďte na jasný popis nejen algoritmů, ale i myšlenek, tvrzení a jejich důkazů. Nezapomeňte u algoritmů uvádět časovou, a je-li to vhodné, i paměťovou slozitost, a obě zdůvodněte. Správnost každého algoritmu je nutné nějak dokázat, či alespoň popsat ho tak, že je zřejmá.

Můžete uvést i funkční kód, pokud chcete, ale sám o sobě není řešením – není z něj poznat ani to, jak algoritmus funguje, jeho složitost ani správnost.

Body za domácí úlohy najdete v této tabulce:

Jednotlivá cvičení

19. 2.O algoritmech obecně a práce s poli

Nebyly zadány žádné domácí úkoly.

26. 2.Binární vyhledávací, AVL a R-B stromy

Úloha inverze (6b, plný počet do 12. 3., 14:00)

Navrhněte algoritmus, který spočte inverze zadané permutace $p$, tedy "dvojic ve špatném pořadí": $\{(a,b)|a<b, p(a)>p(b)\}$. Najděte algoritmus rychlejší než $O(n^2)$.

Úloha unikum (6b, plný počet do 12. 3., 14:00)

Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje. Najděte algoritmus rychlejší než $O(n^2)$.

Úloha medián (8b, plný počet do 12. 3., 14:00)

Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností?

Vstup je zadan jako už načtená pole jen ke čtení, nebo alternativně jako orakulum (funkce), ktere umi vratit $i$-tý prvek z dane vstupni posloupnosti.

Hint: Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností.

5. 3.R-B stromy, různá hashování, nafukovací hash-tabulky

Úloha rovnováha (9b, plný počet do 19. 3., 14:00)

Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený. Nemáte dost paměti na to, abyste si mohli pořídit ještě jednu kopii prvků – kromě stromu si smíte pamatovat O(1) hodnot (pointerů; počitadel do řádově $n$; kopií hodnot).

Úloha merge (8b, plný počet do 19. 3., 14:00)

Navrhněte algoritmus pro sloučení dvou AVL stromů $A$ a $B$, kde všechny prvky $A$ leží před všemi prvky $B$, do jediného AVL stromu $C$. Hledáme řešení s lepší složitostí než $O(\min(|A|,|B|))$. Na cvičení 26. 2. jsme řešení lehce naznačili, ale je potřeba ho popsat podrobněji.

12. 3.Aplikace hashování, složitost rekurzivních funkcí

Pokročilé aplikace hashování: hash s posuvným okénkem, Rabin-carp algoritmus na hledání v textu, Bloom filter. Dále pak počítání a odhadování rekurzivních funkcí, Master theorem.

Úloha rekurence-1 (5b, plný počet do 26. 3., 14:00)

Mějme rekurzivní algoritmus pracující v čase $T(n)$ na datech velikosti $n$. Jeho rekurence je popsána jako $$T(n) = k T(n/k) + c k n.$$

Odvoďte uzavřenou formulku pro funkci $T(n) = f(c,k,n)$ a zapište v $O$ notaci.

Kdybyste měli k dispozici tři verze tohoto algoritmu, pracující s $k = 2,3$ nebo $4$, který byste si vybrali?

Úloha rekurence-2 (6b, plný počet do 26. 3., 14:00)

Odvoďte uzavřenou formulku pro funkci $$T(n) = \frac{2}{n}(T(0) + T(1) + \cdots + T(n − 1)) + c,$$ kde $T(0) = 0$, a zapište ji v $O$ notaci.

Úloha dráty (5+4b, plný počet do 2. 4., 14:00)

Dostali jste nádherný $n$-žilový kabel, ale protože jste barvoslepí, nevíte, který drát z levého konce kabelu je spojený se kterým na pravém konci. Levé i pravé konce si tedy očíslujete, připravíte si zdroj nízkého napětí a zkoušečku nízkého napětí a pustíte se do práce.

Jedna operace je připojení napětí na jeden z vodičů vlevo, odpojení napětí z vodiče vlevo, a zkouška jednoho vodiče vpravo, zda je pod napětím. Vlevo může být připojeno i více vodičů najednou, vpravo testujete vodiče po jednom. Cílem je zjistit, které vodiče jsou spojené (vždy jeden vlevo s jedním vpravo) a minimalizovat při tom počet operací (asymptoticky, tedy v $O$-notaci). Jde to řádově lépe než v $O(n^2)$.

Další 4 body získáte za důkaz, že to řádově rychleji zjistit nelze, tedy že je tolik měření potřeba. Správná dolní mez je lepší než $\Omega(n)$.

19. 3.Rekurzivní algoritmy a rozděl a panuj

Rychlé násobení dlouhých čísel; optimální strategie pro obecné pozice Hanojských věží; nejbližší dva body v rovině v $O(n\log(n))$; majorita v čase $O(n)$ a $O(\log(n))$ paměti; řešení rekurence $T(n)=2T(n/2)+\log_2(n)$.

Úloha min-strom (8b, plný počet do 2. 4., 14:00)

Minimový binární strom (též Kartézský strom) $M(a)$ pro zadanou posloupnost $a=(a_1\dots a_n)$ bez opakujících se prvků je definován takto:

Buď $a_i$ minimální prvek $a=(a_1\dots a_n)$; pak kořen $M(a)$ je $a_i$, jeho levý podstrom je $M(a_1\dots a_{i-1})$ a pravý podstrom $M(a_{i+1}\dots a_n)$. $M(\emptyset)$ je prázdný strom.

Pro zadanou posloupnost postavte minimový strom v čase $O(n)$.

Úloha tridena-majorita (5+5b, plný počet do 2. 4., 14:00)

Majorita posloupnosti je prvek, který se v ní vyskytuje na více než polovině pozic (posloupnost tedy má jednu nebo žádnou majoritu). Na cvičení jsme dělali příklad, kdy je úkolem najít majoritu, pokud existuje, s pamětí $O(1)$ (resp. $O(\log n)$ na RAMu) v čase $O(n)$.

Pokud je posloupnost setříděná, lze zda má majoritu zjistit a zároveň ji najít mnohem rychleji, a to v čase $O(\log n)$. Popište takový algoritmus.

Pro 5 bodů navíc dokažte, že rychleji toto není možné zjistit. Pro plný počet by tento důkaz měl být jasný a úplný.

26. 3.Rozděl a panuj, dolní odhady

Dolní odhad na složitost obecného merge (vyvážených/AVL/$(a,b)$/...) stromů; dosažitelnost a počet sledů v grafu; umocňování matic a čísel obecně; násobení matic na RAMu s lib. dlouhými slovy.

Úloha mezi (7b, plný počet do 9. 4. 14:00)

Ukažte, jak upravit vyhledávací strom (například AVL), aby navíc uměl efektivně provádět operaci $\mathrm{mezi}(x,y)$, která odpoví, kolik vrcholů stromu leží v intervalu $[x,y]$ (kde $x$ a $y$ nemusí být ve stromě přítomny). Složitost všech operací včetně této by měla být $O(\mathrm{hloubka})$.

Úloha srouby (8b, plný počet do 9. 4. 14:00)

Máme $n$ různě velkých šroubů a $n$ odpovídajících matic (existuje mezi nimi párování). Umíme pro dvojici (šroub, matice) rozlišit stavy "pasují", "šroub moc velký", "šroub moc malý", šrouby mezi sebou navzájem nelze porovnávat, totéž platí o maticích. Vymyslete, jak šrouby s maticemi co nejrychleji spárovat, pokud je dostanete náhodně zamíchané, v čase průměrně $O(n\log(n))$ randomizovaně.

2. 4.Radix sort a podobná třídění, úvod do grafů (zaskakuje Martin Koutecký)

Zaskakuje Martin Koutecký, přihrádkové a jiné třídění celých čísel, úvod do algoritmů na grafech; též podle předneseného.

Úloha stříhání (7b, plný počet do 30. 4. 14:00)

Mějme souvislý graf $G$. Jak graf ostříhat, tedy v jakém pořadí můžeme postupně (po jednom) smazat všechny jeho vrcholy tak, aby byl po každém kroku mazání graf stále souvislý? Miřte na složitost $O(n+m)$ nebo velmi blízkou a rozeberte, jestli je to pro možné udělat pro každý souvislý graf nebo ukažtě nějaký, kde to nepůjde.

Úloha zakázka (10b, plný počet do 30. 4. 14:00)

Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a nezáporné celočíselné váhy hran $w(u,v)$ (kde $w(u,v)=w(v,u)$) spočítal nejkratší cesty z vrcholu $s$ do všech ostatních vrcholů. Konkrétně má Láďa spočíst dvě funkce: $d(v)$ má být délka nejkratší cesty z $s$ do $v$ (nebo $\infty$, pokud taková není), a $\pi(v)$ má být předposlední vrchol na nějaké nejkratší cestě z $s$ do $v$ (nebo $\NIL$, pokud taková není).

Olga ale moc nevěří Láďově pečlivosti, a tak si chce výsledky ověřit, což se jí zdá jednodušší, než si je spočíst sama. Konkrétně ověří následující podmínky:

  1. $d(s)=0$
  2. $\pi(s)=\NIL$
  3. $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$
  4. $\forall v\in V: \pi(v)\neq\NIL\Rightarrow d(v) = d(\pi(v)) + w(\pi(v),v)$
  5. $\forall v\in V, v\neq s: d(v) < \infty \Rightarrow \pi(v) \neq \NIL$

Jak může Láďa Olze dát data $d$ a $\pi$, která nejsou korektní podle Olžina zadání, ale splňují tyto ověřovací podmínky? Konkrétně: najděte takový graf, funkci $w$, vrchol $s$ a funkce $d$ a $\pi$, nebo ještě lépe popište takové případy obecněji. Za drué upravte či doplňte podmínky tak, aby už každé řešení splňující tytpo podmínky popisovalo nejkratší vzdálenosti a cesty.

9. 4.Prohledávání grafů a stromů do hloubky a do šířky

DFS pomocí zásobníku a rekurze, vlastnosti DFS stromu, BFS algoritmus pomocí fronty, vlastnosti fronty v průběhu a vlastnosti BFS stromu, vše i na orientovaných grafech.

Orientovaná cesta $u\to v$ v acyklickém orient. grafu neimplikuje ani to, že je v DFS $u$ nad $v$, ani že je $u$ před $v$. Městečko Palermo: VertexCover na stromech. Kanály městečka Palerma: oddělování množiny vrcholů na stromech. Stavový prostor a bludiště: jeden robot, dveře a klíče 3 barev; jeden robot jedoucí až ke zdi; Ricochet Robots. (další varianty: dva roboti se stejnými příkazy UDPL; periodická stráž/pasti; Lloydova 15 a reprezentace jejího stavového prostoru) Hledání stoku v orientovaném turnaji zadaném načtenou maticí sousednosti v $O(n)$.

Úloha housenka (9b, plný počet do 7. 5. 14:00)

Najděte v zadaném stromě housenku na co nejvíce vrcholech. Housenka je podgraf, který se skládá z cesty na jejímž každém vrcholu jsou až čtyři listy (nožičky), ale můžou tam být i vrcholy bez nožiček. Není to totéž, co nejdelší cesta, protože nejde o housenku co nejdelší, ale na největším počtu vrcholů (tedy i s nožičkami). Řešení by mělo být v $O(n)$.

Úloha kůň (8b, plný počet do 7. 5. 14:00)

Na jedné šachovnici $N\times N$ žil byl kulhavý kůň. To je je šachová figurka, která v sudém tahu táhne jako jezdec, v lichém jako pěšec (o 1 dopředu, vždy stejným směrem). Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?

16. 4.Další příklady průchodu grafů

Hledání artikulací a komponenty 2-souvislosti. Hledání stoku v turnaji (úplný graf, kde mezi každými $u$ a $v$ vede buď jen hrana $uv$ a nebo jen hrana $vu$). Jak rychle najít uzavřený Eulerovský tah v Eulerovském grafu a jak najít $k$ disjinktních tahů pokrývajících rany grafu s $2k$ vrcholy lichého stupně. O tom, co je to graf stavů hry dvou hráčů (též stavový prostor) a jak rozhodnout, kdo hru vyhraje a jak pro acyklické hry; též úvaha nad tím, co když je hra potenciálně cyklická.

Úloha polosouvislost (9b, plný počet do 14. 5. 14:00)

Řekněme, že orientovaný graf $G$ je polosouvislý, když pro každé dva vrcholy $u$ a $v$ platí, že existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Toto je silnější vlastnost, než slabá souvislost grafu, ale slabší vlastnost, než silná souvislost grafu. Jak v čase $O(m+n)$ zjistit, zda je $G$ polosouvislý?

Úloha holubi (9b, plný počet do 14. 5. 14:00)

Každý poštovní holub, je-li vypuštěn se zprávou, s ní doletí jen na jedno místo, které je pro konkrétního holuba pevné. Ve spolku pěstitelů holubů má každý člen holuby, kteří mohou doručit zprávu k několika dalším členům. Svolat všepěstitelské setkání je možné jen tak, že ho jeden ze členů vyhlásí rozesláním zpráv všem členům, na které má holuby, a ti pak pošlou zprávu dál svými holuby.

Když znáte strukturu spolku, v čase lineárním s počtem zůčastněných holubů a členů zjistěte, zda vůbec existuje někdo, kdo má možnost setkání všech členů svolat.

23. 4.Cesty v grafu a Dijkstrův algoritmus

Dokončení značkování herních grafů. Optimalizace nákladů jako nejkratší cesta v grafu. Které grafy mají unikátní topologické třídění a jak je poznat? V $O(n^3)$ zjistěte, zda graf (zadaný mat. sous.) obsahuje $C_4$ jako podgraf; uměli byste počet $C_4$ i spočítat? Mějme vážený orientovaný graf, kde hrany z $v$ mohou mít i záporné váhy, do $v$ žádné hrany nevedou a ostatní váhy jsou kladné; lze použít Dijkstrův algoritmus na nalezení nejkratších cest z $v$?

Úloha nejkratsi (7b, plný počet do 21. 5. 14:00)

Navrhněte algoritmus, který v neorientovaném váženém grafu najde nejkratší cesty z daného vrcholu $v$ do všech ostatních vrcholů takové, že mezi všemi nejkratšími cestami navíc obsahuje nejméně hran, a to celé v čase $O((m+n)\log n)$. Například cesty s délkami hran $(2,2,2)$ a $(3,3)$ jsou stejně dlouhé, ale algoritmus by měl preferovat ty druhou.

Úloha abeceda (9b, plný počet do 21. 5. 14:00)

Nalezli jste knihovnu ztracené civilizace a zkoumáte její abecedu o $n$ prapodivných znacích. Každá kniha má na svém hřbetu nápis touto abecedou a doufáte, že jsou knihy seřazené abecedně (lexikograficky). Rádi byste věděli, jestli z pořadí knížek lze zjistit jednoznačné pořadí znaků abecedy, jestli je pro to informací málo, či zda dokonce takové pořadí nemůže existovat (a knihovnu tedy někdo přeházel).

Zadání si představte třeba jako seznam slov bez mezer z abecedy "a-z", otázkou je pak pořadí znaků "a-z" v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete předpokládat, že se každé písmeno mezi nápisy vyskytne.

30. 4.Další nejkratší cesty: B-F a F-W

Opakování Belman-Fordova a Floyd-Warshallova algoritmu. Dijkstrův algoritmus pro grafy s ohodnocením hran $\{1,\dots K\}$ v časech $O(nK+m)$ a $O((n+m)\log K)$. Délka nejkratší kružnice procházející danou hranou; délka nejkratší kružnice v grafu vůbec v $O(mn)$. Pro jeden startovní vrchol zjistěte, do kterých vrcholů je z něj nejkratší cesta unikátní. Upravte algoritmy pro nejkratší cestu tak, aby minimalizovaly ne součet délek hran, ale jejich maximum a nebo součin; pro jaké funkce (krom maxima, sumy a produktu) obecně můžete hledat minimální cestu pomocí Dijkstrova či B-F algoritmu?

Úloha negative-floyd (8b, plný počet do 21. 5. 14:00)

Co udělá F-W algoritmus na grafu se zápornými vahami, ale bez záporných cyklů? A co udělá F-W na grafu se záporným cyklem? Svá tvrzení dokažte.

Pro bonus vysvětlete (potenciálně chybný) výsledek algoritmu a význam získaných hodnot (tedy zda výsledná čísla přeci jen něco popisují).

Úloha cheating (7b, plný počet do 21. 5. 14:00)

Závod bludištěm z živých plotů! Jste rozhodnuti vyhrát a to i za cenu malé ... zkratky, kterou pravidla zapoměla zmínit. Nejste ale ochotni se křovím prodrat víc než jednou, ještě by si toho někdo všiml a mohl by to ... špatně pochopit.

Bludiště je popsáno grafem se startem, cílem, délkami hran a dvěma typy hran – chodby bludištěm a zkratky křovím, kterými se ještě jde prodrat. Navrhněte algoritmus pro nejkratší cestu do cíle v co nejlepším čase.

7. 5.Floyd-Warshall a minimální kostry (zaskakuje Honza Musílek)

Matice předposledních vrcholů nejkratších cest z F-W. Řezové a kružnicové barvící pravidla pro minimální kostru; další úvahy o řezech a cyklech. Úprava min. kostry po změně váhy jedné hrany. Minimální kostra grafu s vahami 1, 2, 3 (či jiná konstanta) v čase $O(m)$. Druhá nejlehčí kostra.

Úloha listy-kostry (10b, plný počet do 21. 5. 14:00)

Máme dánu $U$ jako podmnožinu vrcholů souvislého grafu $G$ s váhami hran $w$. Najděte minimální kostru $G$ ze všech takových koster, které mají vrcholy z $U$ jako listy. Algoritmus by měl být stejně rychlý jako jiné vám známé algoritmy na min. kostru a měl by rozpoznat situaci, že taková kostra neexistuje.

Tento domácí úkol je poslední.

14. 5.Sportovní den

Cvičení odpadá.

21. 5.Eukleidův algoritmus a Eratosthenovo síto

Opakování Eratosthenova síta; výpis prvočísel $1,\dots n$ s ušetřením paměti na $O(\sqrt{n})$; výpočet počtu dělitelů u každého čísla. Eukleidův algoritmus pro hledání největšího společný dělitele; nejhorší vstup pro Eukleidův algoritmus jsou po sobě jdoucí Fibonacciho čísla; zobecněný Eukleidův algoritmus, který najde i $x$ a $y$ takové, že $ax+by=\mathrm{gcd}(a,b)$.

Nebyl zadán domácí úkol.

Materiály

Left-leaning red-black tree (doleva nakloněné červeno černé stromy) — relativně čerstvá a výrazně jednodušší varianta červeno-černých stromů [Prezentace] [Článek]

Kapitoly z připravovaných skript Martina Mareše

Programátorská kuchařka KSP — nepříliš formální textíky o různých algoritmech

Dasgupta, Papadimitriou, Vazirani: Algorithms — velice pěkná knížka pokrývající většinu přednášky (dostupná online aktuálně po kapitolách)

Jakub Černý: Základní grafové algoritmy — knížka vzniklá ze zápisků algoritmických přednášek na MFF

Jaj