Cvičení z Algoritmů a grafů I. v ZS17/18

Cvičení probíhají každou středu od 14:30 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

Doporučuji Průvodce labyrintem algoritmů.

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. Asymptotická analýza počtu hvězdiček vypsaných několika kódy. 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. Určování, zda různé dvojice grafů jsou či nejsou izomorfní.

11.10.

Pro jaká N existuje graf na N vrcholech se všemi stupni různými. G je izomorfní H, právě když doplněk G je izomorfní doplňku H. Počet automorfismů K_n, P_n, C_n. Každé dva (N-1)-regulární grafy na N vrcholech jsou izomorfní. Počet indukovaných podgrafů K_n. Rozhodněte, zda existuje nesouvislý graf, jehož doplněk je také nesouvislý.

18.10.

Jak na RAMu zakompresit paměť na O(1)? Pro jaká N existuje graf na N vrcholech se všemi stupni různými až na dva? Najděte příklad netriviálního strnulého grafu. Dokažte, že když graf G obsahuje nějakou kružnici jako podgraf, tak také obsahuje nějakou kružnici jako indukovaný podgraf. Graf na 2n vrcholech a stupeň každého je n, potom je souvislý. Hledání (nejkratší) cesty v bludišti jako šachový kůň. Složitost BFS. Algoritmus na test, zda je v grafu kružnice. Algoritmus na počet souvislých komponent grafu.

25.10.

Počet podgrafů K_n. Dokažte, že strom T má alespoň Δ(T) listů. Upravte DFS, aby hledal topologické uspořádání orientovaného grafu. Navrhněte algoritmus na hledání (nejkratší) cesty v bludišti figurkou "kulhavého" koně. Kolik maximálně a minimálně může mít hran graf s C komponentami souvislosti. Počet koster grafu K2,n.

1.11.

Ukažte, že v souvislém grafu na aspoň 3 vrcholech existují vrcholy u,v, že G-u, G-v a (G-u)-v jsou souvislé. 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. Co udává druhá mocnina matice sousednosti grafu? HeapSort in-place. Jak slévat haldou k setříděných posloupností. Na hledání minima je třeba aspoň n-1 porovnání.

8.11.

ChangeKey a Delete v binární haldě. Navrhněte algoritmus na odměřování K litrů pomocí přelévání nádob. Analýza nafukovacího pole penízkově. Simulace fronty pomocí dvou zásobníků. Úloha s výhledem na tabuli. Úloha se zemětřesením. ExtractMin v binomiální haldě.

15.11.

Dokažte, že v binomiálním strum B_n je na i-té hladině (n nad i) vrcholů. Úloha s výhledem na tabuli: řešení v O(N). Následník v BVS. Proč proskákání BVS voláním následníka trvá O(N). Postavení/převážení dokonale vyváženého BVS. AVLInsert. Generátor náhodných čísel.

22.11.

Jak náhodně zvolit jeden řádek ze streamu dat na vstupu. Generátor náhodné permutace. Náhodně hodíme 10 hracích kostek a posčítáme puntíky; v jakém pstním prostoru se pokus odehrává a jaká je střední hodnota počtu puntíků? Návrh hashovací funkce pro stringy a hledání kolizních párů. Randomizované rozhazování kuliček na 3 hromádky.

30.11.

Náhodně střílím do pole velikosti M, jaká je střední hodnota počtu pokusů, kdy označím všechna políčka? Třídění spojáku. Paměťová složitost Karacuby. Úloha s kabelem.

6.12.

Píšeme písemku.

13.12.

Countingsort, Radixsort, trideni stringu. Třídění N integerů z intervalu 0..N^3-1. Počet vydláždění mřížky 2xN různými typy dlaždic. Cesta s max. součtem v trojúhelníku čísel.

27.12.

Matice NxN, řádky a sloupce rostoucí, jak v O(N) najít zadaný prvek. Počet cest v acyklickém orientovaném grafu. Rozklad stringu na minimální počet palindromických bloků. Optimální zalomení textu do řádek. Matice, z jejíž n-té mocniny lze vyčíst n-té Fibonacciho číslo.

Úlohy k vyřešení