Info

  • Kontakt: blazeva1 (na) fit.cvut.cz
  • Konzultace: Po domluvě emailem
  • Kde mě najdete: A-1256 (pá NB 341b)

AG1 pro paralelky 106 (16:15) a 107 (18:00). Body za aktivitu budou za domácí úkoly (max 5b).

Zde bude seznam probrané látky a úkoly do dalšího cvičení.

Úkoly pošlete mailem nebo doneste vypracovené na papíře. Opravené budou další týden. Bodované jsou pouze aktuální úkoly – ty se každý týden chvíli po cvičení obměňují.

Body (max 5) <- dostupné pod fit.čvut účtem

Aktuální seznam úkolů

Tyto úlohy lze odevzdávat i ve zkouškovém, posílejte mailem:

  • (1.5b) Navrhněte, dokažte správnost a zanalyzujte časovou a paměťovou složitost algoritmu řešící následující úlohu: Mějme DAG ↗ G a v něm označený zdroj Z a stok S. Pro každý vrchol zjistěte, kolik existuje různých cest ze Z do S, které vedou přes onen vrchol.
  • (0.5b) Upravte Bellman-Fordův algoritmus tak, aby uměl detekovat záporný cyklus v grafu.
  • (1.0b) Mějme graf, reprezentující železniční síť české republiky. Na hranách jsou definovány vlakové spoje s časy, kdy je možné po hraně přejet. Spoj má čas výjezdu a čas příjezdu (v minutách). Navrhněte algoritmus, který pro zadaný graf a spoje zjistí nejnižší čas, kdy se dokážeme z města A dostat do města B pouze pomocí vlakových spojů. Začínáme v čase 0:00 a pokud nestihneme přijet do 23:59, tak je výstupem chyba.
  • (0.5b) Mějme pole s N čísly. Jak lze v $O(1)$ zodpovídat querry, které se ptají na součet prvků v rozsahu indexů A až B (A<B)?
  • (0.8b) Navrhněte algoritmus, který zjistí nejmenší počet palindromických kusů, na které lze rozdělit zadaný řetězec. Např. abbabb lze rozdělit na abba, bb, což jsou oba palindromy a zároveň je to nejmenší počet kusů.
  • (0.8b) Navrhněte algoritmus, který dokáže v BVS rychle zjistit jestli ve stromě existuje podstrom, který má přesně K listů. Strom by měl zvládat insert (klasickým BVS způsobem) a zodpovězení definované otázky.

12. cvičení

Kostry a nejkratší cesty, Unioin-Find algoritmus

Probrané úlohy

  • Jak definovat kostru pro nesouvislé grafy?
  • Jak se liší kostra G a G-e?
  • Jak najít druhou nejmenší kostru?
  • Jak se použije Union-Find (aneb. Disjoint Set Union) v implementaci Kruskala?
  • Jak rychle hledat kostru grafu s omezenýma váhama, třeba 1 až 5? (pro Kruskala i Jarníka)
  • Vypište všechny hrany, pro které existuje nějaká nejkratší cesta ve které jsou. Nejkratší cesty bereme mezi vrcholy s a e na váženém grafu G.

11. cvičení 12.12.2017 (vedl Peter a Tom)

Dynamické programování

Probrané úlohy

  • počet cest mezi N městy (iterativně, DP)
  • dláždění plochy $N \times 2$ pomocí různých bloků
  • DP na nejdelší cestu ve stromě
  • Longest Increasing Subsequence (LIS) v čase $O(n \log n)$
  • LIS s jedním poklesem (lze zobecnit na až k poklesů)
  • hledání nejdelšího palindromu v řetězci
  • rychlé mocnění pomocí metody square multiply

Úkoly

  • (0.4b / AC) [zůstává z minula] Pokud radši implementujete, tak naprogramujte úlohy z CF #447 ↗, pak mi napište username a dostanete 0.4b za jednu přijatou úlohu.

10. cvičení 5.12.2017 (semestrální test)

9. cvičení 28.11.2017

Hešování, Řazení

Probrané úlohy

  • Rozptylování (hešování) a vyhledávací tabulky - hešování stringů a hledání kolizí, mazání náhrobkem a proč je potřeba
  • Algoritmus na zjištění duplikátů v N prvkovém poli.
  • řazení - CountingSort, RadixSort, řazení řetězců, hledání prvku v uspořádaném 2D poli

Úkoly

  • (0.8b) Navrhněte algoritmus, který rychle najde maximum v poli. Prvky v poli tvoří konkávní posloupnost – tedy v poli je právě jedno maximum a pro ostatní prvky platí, že je prvek menší než jeden jeho soused. Analyzujte složisost.
  • (1.2b) Mějme dlouhý kabel, ze kterého na obou koncích čouhá $n$ optických vláken. Na jednom konci můžeme do jednotlicých vláken zapojit světlo tak, že na druhé straně budeme moci naměřit jestli se do kabelu svítí nebo ne. Zapojení i měření musíme dělat ručně a konce tohoto kabelu jsou daleko od sebe. Kolikrát musíme mezi konci přejít, abychom zjistili které konce vláken patří ke stejným vláknům. (např. zasvícením do jednoho zjistíme s jistotou jeden, ale to je pomalé)

8. cvičení 21.11.2017

Rekurzivní algoritmy a metoda Rozděl a panuj

Probrané úlohy

  • hanojské věže - proč je $2^n-1$ optimální, řešení pokud nemůžeme přesouvat mezi dvěma z kup přímo
  • řazení spojového seznamu
  • zjišťování špatných vstupů quick sortu pro danou volbu pivota
  • počítání inverzí pomocí úpravy merge sortu
  • rychlé násobení (Karatsuba)

Úkoly

  • (0.5b) Ukažte, že následující kód negeneruje náhodnou permutaci.

Kód:

for i = 0; i < n; ++i:
    x = rand() mod n
    swap(a[i], a[x])
  • (0.5b) Mějme dvojté hashování s hashovací funkcí: $h(k,i)=(k + i,h_2(k)) \bmod 11$; kde $h_2(k)=2+k \bmod 3$; vložte do hashovací tabulky (s velikostí jedenáct) prvky 2,4,6,12,11,42 a 46
  • (0.5b) najděte alespoň 2 hodnoty, pro které (u předchozí úlohy) platí, že budou mít stejnou fci $h$ i $h_2$ jako číslo 13?

7. cvičení 14.11.2017 (vedl Radovan)

AVL, pravděpodobnost

Probrané úlohy

  • Insert, Delete AVL
  • Náhodné generování čísla $1-N$ s uniformní pravděpodobností pomocí férové mince.
  • Generování náhodné permutace čísel $1,\dots,N$ tak, že každá z $N!$ permutací má stejnou pravděpodobnost.
  • DK věty o opakování jevu

Úkoly

  • (1.0b) Zjistěte jestli se pošle vyvažovací signál výše, a jaké příznaky budou v AVL po vymazání nějakého prvku z levého podstromu vrcholu X, pokud X měl příznak (+) a jeho pravý syn (Y) měl příznak (-). (rozeberte případy)
  • (0.5b) Jak z velikého souboru vybrat náhodně jednu řádku? Předem nevíme kolik má soubor řádek. Soubor se nevejde do pracovní paměti. Každá řádka má nakonec mít stejnou pravděpodobost výběru.
  • (0.5b) Jak z velikého soboru vybrat K náhodných řádek tak, aby každá měla stejnou pravděpodobnost? (opět nemůžeme soubor načíst celý a neznáme jeho délku)

6. cvičení 07.11.2017

Binární haldy ↗, Binomiální haldy ↗, BV stromy ↗, AVL stromy ↗

Probrané úlohy

  • opakování binomiálních hald - extract min, merge, decrease, delete, increase value (z úkolu)
  • úkol - Jak zakódovat aritmetický výraz se závorkami a operacemi $+,-,\times,/$ do stromu. Algoritmus, který strom se zakódovaným výrazem zderivuje.
  • pre,in,post-order průchody stromu
  • BVS ↗, následník, složitost průchodu
  • Algoritmus, který vyváží BVS v $O(n)$. Vylepšení, které udrží BVS vyvážený amortizovaně v $O(\sqrt{n})$.
  • Vyvažované stromy - AVL ↗, vyvažovací rotace

5. cvičení 31.10.2017

amortizovaná analýza, binární haldy, heap sort

Probrané úlohy

  • úkoly z minula, hlavně vážení kuliček
  • mocnina matice sousednosti A (v mat. je $A_{a,b}=1$ pokud vede hrana z a do b, 0 jinak) na K, nová matice $A^K$ vyjadřuje počet různých sledů z vrcholu a do b
  • nafukovací pole účetní metodou
  • increase bin. čísla přímým výpočtem
  • sloučení k seřazených posloupností v $nk \log(k)$
  • nakreslit binární haldu veliksoti 51

Úkoly

  • (0.5b) Zanalizujte amortizovanou složitost simulace fronty pomocí dvou zásobníků. (pushuje se do 1. zásobníku, pulluje se z 2. zásobníku, když je 2. prázdný, tak se všechny prvky postupně přesunou z 1. do 2. zásobníku.)
  • (1.0b) Navrhněte, jak zakódovat aritmetický výraz se závorkami a operacemi $+,-,\times,/$ do stromu. Ukažte algoritmus, který strom se zakódovaným výrazem zderivuje.
  • (0.5b) Nakreslete binomiální haldu s 42 prvkama.
  • (0.5b) Navrhněte operaci increase value prvku binomiální haldy (máte pointer a novou hodnotu) v $\log n$. Pamatujte, že nelze procházet všechny syny, páč jich je moc, a nevyšla by dobrá složitost.

4. cvičení 24.10.2017

topologické uspořádání, sqrt dekompozice, řazení ↗

Probrané úlohy

  • kulhavý kůň, extrémní počty hran v grafu s c komponentami
  • Běžci si pamatují některé, kteří doběhli před nimi, je možné rekonstuovat jednoznačné pořadí pouze z této informace?
  • hledání topologického uspořádání pomocí odřezávání listů
  • počet topologických uspořádání v orientovaném $K_n, K_{n,n}, n \times C_4$
  • Jak rychle najít k-tý nejmenší prvek v neseřazeném poli?
  • Hledání sqrt(n) nejmenších prvků v čase O(n)
  • binární haldy ( postavení v O(n) ), heap sort

Úkoly

  • (0.5b) vyberme hranu e z grafu G, existuje vždy kostra taková, že obsahuje hranu e?
  • (0.5b) jaká je (maximální) délka nejkratší cesty mezi libovolnými uzly $u,v$ v grafech: $K_n, K_{n,m}, C_n, $
  • (1.0b, 30% funkční, 60% rychlý, 100% optimální) Mějme graf G se startem a cílem ve kterém má každá hrana danou nosnost. Ve startu stojí nákladní vůz k neomezenou kapacitou. Jak těžký náklad lze na nákladní vůz naložit tak, aby se dostal do cíle po hranách s větší nostností, než je váha jeho nákladu?
  • (1.0b) Mějme rovnoramenné váhy, které umí rozhodnout která hromada kuliček je těžší.
    • Na kolik vážení zjistíme, která z devíti kuliček je těžší?
    • Na kolik vážení to lze pro 12 kuliček, a proč to nejde pouze na 2?
    • Co když není jedna z kuliček těžší, ale má jinou váhu (je tedy buď těžší nebo lehčí)? Kolik vážení je potřeba pro 13 kuliček?
  • (0.5b) Jaké řazení pole délky n použijeme, pokud prohození prvků trvá $O(n)$? Analyzujte složitost, porovnejte s dalšími algoritmy řazení.

3. cvičení 17.10.2017

symetrizace, zdroj, stok, izolovaný vrchol, silná souvislost ↗, stromy (zakořeněné), DFS, BFS, kostry, vzdálenost vrcholů

Probrané úlohy

  • vlastnosti stromů (souvislý, bez cyklů)
  • omezení počtu listů (2 – n-2) a extrémní grafy, dolní mez $|L| \geq \Delta(T)$

  • listů pro zadaný počet vnitřních vrcholů a jejich stupňě

  • vnitřních uzlů pro zadaný počet listů a stupeň je $\frac{l-2}{d-2}$

  • počet koster grafů $P_n, T, K_n, K_{1,n}, C_n, K_{2,n}$
  • jak v DFS
    • vypsat cestu ze startu do cíle?
    • spočíst souvislé komponenty?
  • jak v BFS
    • zjistit nejmenší vzdálenost vrcholů?
    • najít nejkratší cestu?

Úkoly

  • (0.5b) nejvyšší / nejnižší počet hran G s n vrcholy a c komponentami
  • (0.5b) počet koster $K_{2,n}$
  • (1.0b) Mějme mřížku NxN, některá políčka jsou dostupná a jiná jsou zdi. Na mřížce máme figurku ‘kulhavého koně’. Kůň začíná na políčku s a chceme dojít na políčko e. Kulhavý kůň se pohybuje každý lichý krok jako kůň, a každý sudý krok jako král. Navrhněte algoritmus, který najde nejkratší (nejméně pohybů) cestu tohoto koně z s do e.
  • (0.5b) Máme 3 nádoby, které mají kapacity A, B a C. Navrhněte algoritmus, který zjistí jak odměřit D litrů? (nelze zloušet od oka, lze pouze nádoba naplnit, vylýt, přelít apod.)

2. cvičení 10.10.2017

slabá ↗ souvislost, indukovaný podgraf, isomorfismus

Probrané úlohy

  • Jsou každé dva $(n-2)$-regulární grafy izomorfní (|V|=n, n>1)?
  • Graf obsahující kružnici jako podgraf obsahuje i indukovanou kružnici jako podgraf.
  • Existuje nesouvislý graf G, který má nesouvislý doplněk?
  • Grafy jsou isomorfní právě tehdy pokud jsou jejich doplňky izomorfní.
  • Kolik existuje různých cest délky M uvnitř kliky $K_n$ nebo v bipartitním grafu $K_{n,n}$?

Úkoly

  • (0.5b) Dokažte nebo vyvtaťte, že v oritentovaném grafu se vstupním i výstupním stupni >= 1 vždy existuje orientovaný cyklus.
  • (0.5b) Kolik existuje $C_4$ na 4-partitním grafu $K_{n,n,n,n}$?
  • (0.5b) Kolik existuje různých cest délky M mezi uzly x a y uvnitř kliky $K_n$ nebo v bipartitním grafu $K_{n,n}$?
  • (0.5b) Určete (nakreslete) všechny indukované podgrafy kliky $K_5 - e$ (K5 bez hrany).
  • (0.5b) Určete (nakreslete) všechny (neizomorfní, tzn. prostě všechny) podgrafy kliky K4.

1. cvičení 03.10.2017

podmínky zápočtu ↗, vrchol, hrana, stupeň, soubor stupňů, princip sudosti, regularita

Probrané úlohy

  • Kolik vypíše program hvězdiček?
  • Seřadit funkce podle asymptotické složitosti ($n \log n$, $2^n$, $n^2$, $\sqrt{n}$, $n!$, $\log^2 n$, $\log {\sqrt{n}}$, $\sqrt{\log{n}}$, $n^{21}$)
  • házení teleportéru a hledání smrtící hranice (jedno, dvě, N)
  • formální zápis grafu $G=(\{1,2,3\},\{\{1,2\},\{2,3\}\})$
  • Pro která n existuje graf, ve kterém má každý vrchol jiný stupeň? (nelze)
  • Pro která n existuje graf, ve kterém má každý vrchol jiný stupeň, kromě dvou, které mají stejné? (konstukcí)
  • Jsou každé dva $(n-1)$-regulární grafy izomorfní (|V|=n, n>0)? (ano, jsou to kliky)
  • podmínky isomorfismu ↗ (#uzlů, #hran, stupně, sousedi, …)

Úkoly

foo(q)
	for i := 1 to q do
		print(#)
foo2(N)
	for i := 1 to N do
		foo(i)
		j=1
		while j<=N do
			foo(j)
			j=j*2
  • (1.5b) Kolik se vypíše znaků # pro výše uvedený program při zavolání funkce foo2?
  • (0.5b) Kolik hodů perlou potřebuju, abych zjistil pozici bariéry, pokud mám jen tři perly?
  • (0,5b) Pro jaká N lze sestrojit graf, ve kterém mají pouze dva uzly stejný stupeň?
  • (0.5b) Navrhněte dvojici grafů, každý s alespoň šesti vrcholy, které nejsou isomorfní, ale mají stejný soubor stupňů.
  • (0.5b) Zjistěte počet automorfismů pro kliku o šesti vrcholech, ze které jsme odebrali dvě hrany, které spolu nesousedí (tj. hrany bez společného uzlu), zkuste zobecnit na kliku s N vrcholy bez dvou hran.
  • (1.0b) Lze rozložit úplný graf $K_n$ (n je sudé) na sjednocení hranově disjunktních 2-regulárních grafů?