Cvičení z Algoritmů a grafů I. v ZS16/17

Cvičení probíhají každé úterý od 11:00 v učebně 1242 (budova A).


Podmínky zápočtu

Body lze získat za:

Zápočet je za

Konzultace

Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229.

kontakt: tomas.valla@fit.cvut.cz

Studijní materiály

K dispozici je vývojová verze studijních textů, které pokrývají některé kapitoly z předmětu.

Mentální trénink

Kdo si chce trénovat své algoritmické myšlení nad rámec cvičení (nebo zkrátka jen řešit pěkné úlohy ve volném čase), má možnost.

Doporučuji následující dva zdroje:

Oba zdroje obsahují takřka nekonečnou zásobu zajímavých algoritmických úloh, od lehkých po brutální, včetně vzorového řešení, u KSP i s rozsáhlou sadou studijních materiálů.


Obsah cvičení

4.10.

Podmínky na zápočet. Co nás v předmětu čeká. Úloha s házením vajíčka z paneláku. Hledání chybějícího čísla z 1..N na vstupu. A co když chybí 2? Asymptotická analýza počtu hvězdiček vypsaných několika kódy. Na vstupu N vzestupně setříděných čísel a číslo K. Jak co nejrychleji zjisti, zda mezi nimi existuje dvojice se součtem K? Lehký úvod do grafů. Pro jaké kombinace může a pro jaké nemůže existovat graf se zadaným počtem vrcholů a zadanými stupni. Pro jaká N existuje graf na N vrcholech se všemi stupni různými?

11.10.

Úloha házení vajíčka z paneláku, tentokrát jsou k dispozici 2 vajíčka. (Lze v O(sqrt(N))) Pro jaká N existuje graf na N vrcholech se všemi stupni různými až na dva? Určování, zda různé dvojice grafů jsou či nejsou izomorfní. Různa pozorování co musí izomorfní grafy zachovávat za vlastnosti. Počet všech grafů na N vrcholech. Všechny navzájem neizomorfní grafy na 4 vrcholech. Jak vypadají 0-regulární, 1-regulární, 2-regulární grafy.

18.10.

Dokažte: G je izomorfní H, právě když doplněk G je izomorfní doplňku H. Rozhodněte, zda každé dva (N-2)-regulární grafy na N vrcholech jsou izomorfní. Počet automorfismů K_n bez hrany. Existuje nesouvislý graf, jehož doplněk je také nesouvislý? Konstrukce strnulých grafů. Počet cest délky k mezi dvěma vrcholy v K_n. Modifikace DFS pro výpis cesty, pro cestu šachového koně v bludišti, a pro kulhavého koně v bludišti. Algoritmus na počet souvislých komponent grafu.

25.10.

Ukažte, že když graf obsahuje jako podgraf kružnici, tak potom obsahuje také nějakou kružnici jako indukovaný podgraf. Kolik navzájem neizomorfních kružnic obsahuje K_n jako podgrafy? Ukažte, že graf na 2n vrcholech se všemi stupni n je souvislý. Kolik maximálně hran může mít graf na n vrcholech s c komponentami souvislosti? Všechny navzájem neizomorfní stromy na 6 vrcholech. Náznaky k úlohám: jak řešit hlavolam s přeléváním nádob, úloha s Indiana Jonesem a mumií v labyrintu. G bez kružnic a |V|=|E|+1, potom je G strom.

1.11.

Ukažte, že graf na n vrcholech s c komponentami souvislosti má aspoň n-c hran. Ukažte, že strom T má aspoň Delta(T) listů, kde Delta(T) značí maximální stupeň T. Ať d_1,...,d_n jsou kladná celá čísla; ukažte tuto ekvivalenci: Existuje strom na n vrcholech se souborem stupňů d_1,...,d_n právě tehdy, když d_1+d_2+...+d_n = 2n-2. Efektivní realizace trhacího algoritmu TopSort. Modifikace DFS na hledání topologického uspořádání. Pro souvislý graf na aspoň 3 vrcholech existují vrcholy u,v, že G-u, G-v a (G-u)-v jsou souvislé.

8.11.

Ukažte, že pro souvislý G a každou jeho hranu e existuje kostra, která e obsahuje. Hlavolamy s nalezením těžší a jiné kuličky z N pomocí rovnoramenných vah. Slévání 2 a K setříděných posloupností. Min a max počet prvků v haldě s h hladinami. Delete v binární haldě.

15.11.

Operace ChangeKey v binární haldě. Co nejrychleji dotřiďte posloupnost takovou, že každý prvek v ní leží nejvýše K pozic od místa, kde by ležel ve vzestupně setříděné posloupnosti. Sečtěte řadu \sum_{i=1}^\infty i/2^i. Simulace fronty dvěma zásobníky. Amortizovaná analýza nafukovacího pole penízkovou metodou a binární sčítačky sčítací metodou. Delete a Changekey v binomiální haldě.

22.11.

Mějme funkci Next, která k prvku BVS najde nejbližší vyšší. Kolik času zabere proskákání celého BVS touto funkcí? Jak vyvážit BVS. Jak slít obsahy dvou BVS do jednoho. Algoritmus na nejdelší cestu ve stromu - bottom-up dynamické programování.

29.11.

Hodíme 10ti kostkami, puntíky sečteme. V jakém pstním prostoru se to odehrává? Jakou má tato náhodná veličina střední hodnotu? Jak dlouho průměrně čekám, než mi padne součet 11? Variace na tuto úlohu s jinými kostkami. Kolik je AVL stromů s 4 prvky. Jak generátorem náhodného bitu generovat obecná náhodná čísla. Generování náhodné permutace. Randomizované rozhazování kuliček na 3 hromádky.

6.12.

Co nejlepší hashovací funkce pro stringy a hledání kolizních párů. Pro N,M nesoudělná, proč výraz i.N mod M pro všechna i=0…M-1 vygeneruje postupně všechna čísla 0…M-1. Jak dlouho průměrně trvá shromáždit sbírku N kartiček pomocí nákupů naslepo. Filtr, který náhodně rovnoměrně vybere jeden z prvků ze vstupu. Proč algoritmus Hanoj je optimální. Náznak varianty hanojských věží, kde je zakázán přesun z A na B.

13.12.

Budeme psát písemku

20.12.

Úloha s kabelem. Co se stane, když v QS volíme jako pivota první prvek intervalu? Co když bereme aritmetický průměr? Jak třídit spoják v O(NlogN) s O(1) pomocnou pamětí a povídání o vnějším třídění. Třídění stringů v lineárním čase. Matice NxN, řádky a sloupce rostoucí, jak v O(N) najít zadaný prvek.

3.1.

Nejdelší rostoucí podposloupnost, která může obsahovat jeden pokles. Kolika způsoby lze vydláždit mřížku 2xN zadanou sadou dlaždiček? Dána matice čísel, jak najít cesty shora dolů s maximálním součtem? Jak rozsekat string na minimální počet palindromů. Optimální vysázení textu do bloku. Nejkratší/nejdelší cesta v DAGu. Náznak jak hledat minimální kostru když jsou váhy malé integery.

Úlohy k vyřešení