Cvičení probíhají každou středu od 14:30 v učebně 1242 (budova A).
Body lze získat za:
Zápočet je za
Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229.
kontakt: tomas.valla@fit.cvut.cz
Doporučuji Průvodce labyrintem algoritmů.
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ů.
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í.
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ý.
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.
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.
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í.
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ě.
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.
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.
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.
Píšeme písemku.
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.
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.