[home]

ADS II (2016/2017)

Cvičení k přednášce Algoritmy a datové struktury II

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (tj. za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna 5 body (tj. více aktivity na jednom cvičení je stále 5 bodů).

Body

Smazáno kvůli GDPR.

Úkoly

5.10. (do 2.11.)

• Jak najít lexikograficky nejmenší rotaci řetězce v O(n)?
• Jak najít v řetězci nejdelší opakující se podřetězec v O(n^2)?
• Jak najít pro dva řetězce jejich nejdelší společný podřetězec?

12.10. (do 9.11.)

• V zadaném řetězci nalezněte nejdelší Fibonacciho podslovo.
• Pro daný slovník navrhněte datovou strukturu, která pro zadané slovo rozhodne, zda je ve slovníku jeho rotace.

19.10. (do 16.11.) - úkoly řešte pomocí toků

• Nalezněte co nejlepší pokrytí šachovnice s dírami kostičkami 2x1 (kostička nesmí ležet na díře)
• Pro daný neorientovaný graf nalezněte co největší k takové, že je graf hranově k-souvislý (tj. souvislý i po odebrání libovolných k-1 hran)
• Nalezněte minimální vrcholové pokrytí bipartitního grafu

26.10. (do 23.11.)

• Jak odstranit k hran tak, aby se co nejvíce zmenšil maximální tok? Uvažujte graf s jednotkovými kapacitami. Jak by se situace změnila pro obecné kapacity?
• Mějme síť s již nalezeným maximálním tokem a celočíselnými kapacitami. Co se stane, když některé z hran snížíme kapacitu o 1? Jak nalézt v takové síti co nejrychleji maximální tok?

2.11. (do 30.11.)

• Příklad sítě a běhu algoritmu, kdy Dinitzův algoritmus udělá co nejvíce kroků. (řádově O(n^2 * m))
• Uvažujme tokový algoritmus (například Ford-Fulkerson), který neuvažuje rezervy hran (jinými slovy, když něco pošlu po hraně, už to nemůžu vzít zpět). Nalezne takovýto algoritmus maximální tok? Pokud ne, nalezne vždy tok velikosti f_max / b pro nějaké pevné b?

9.11. (do 7.12.)

• Jak vypadá DFT reálného vektoru?
• Jak vypadá DFT antisymetrického vektoru? (antisymetrický vektor := x_i = komplexně sdružené x_{n-i}

16.11. (do 14.12.)

• Napište DFT vektorů (1,-1,1,-1, ... ) a (1,0,1,0,1, ... ).
• Napište FFT nerekurzivně.

23.11. (do 21.12.)

• Jak najít polynom P(x), který prochází zadanými body (x_i, y_i) pro i = 0, ..., n-1
• Máme funkci sin(2*k*pi*x), kterou navzorkujeme v n bodech. Tím získáme reálný vektor x délky n. Jak vypadá Fourierův obraz x? Jako primitivní odmocninu z 1 uvažujte e^((2*pi*i)/n)

30.11. (do 28.12.)

• Dokažte, že n-bitový OR nelze spočítat v menší než logaritmické hloubce.
• Ukažte, že libovolnou booleovskou funkci s k vstupy lze spočítat booleovským obvodem hloubky O(k) s O(2^k) hradly.

7.12. (do 4.1.)

• Sestrojte hradlovou síť (hloubky log n), která porovná dvě n-bitová čísla x a y a vrátí jedničku, pokud x < y.
• Ukažte jak přeložit komparátorovou síť na booleovský obvod. Čísla reprezentujte dvojkovým zápisem o n bitech. Můžete předpokládat, že máte k dispozici hradlovou síť z předchozího bodu.

14.12. (do 11.1.)

• Pro množinu n bodů v rovině sestrojte dva konvexní obaly (které dohromady pokryjí všech n vrcholů) tak, aby byl součet jejich obvodu co nejmenší.
• Jak k dané množině bodů v rovině sestrojit obdelník s nejmenším možným obvodem, který obsahuje všechny dané body? Obdelník nemusí mít strany rovnoběžné s osami.
• Vymyslete datovou strukturu, která bude udržovat konvexní obal množiny bodů a bude ho umět rychle přepočítat po přidání bodu do množiny.

21.12. (do 18.1.)

• Převodem jiného NP-úplného problému dokažte NP-úplnost libovolného z následujících problémů (příklady z přednášky a triviální převody neberu): Barvení grafu, Hamiltonovská cesta, Batoh, Dva loupežníci, SAT, 3,3-SAT