Cvičení z Algoritmů a datových struktur I ve Středu 12:20

Místnost

Cvičení probíhá v místnosti S11, což je na Malé strane v 1. patře.

Podmínky získání zápočtu

Zápočet se uděluje za získání 100 bodů za domácí úkoly.

Z čeho se učit

Poměrně dobrý zdroj informací o probírané látce je zde. Dole na této stránce jsou učební texty k jednotlivým tématům.

Konzultace

Pravidelné konzultace nejsou vypsány, ale k zastižení budu vždy po cvičení.
K zastižení taktéž bývám ve Středu a Čtvrtek v S323.
Při potřebě větší konzultace mi prostě napište email a domluvíme se na termínu.
A prosím nebojte se ptát. To, že něčemu nerozumíte není chyba, pokud to není až u zkoušky.

Domácí úkoly

Vždy 14 dní po zadání domácího úkolu se na cvičení řekne nápověda a poté bude za domácí úkol udělena pouze polovina bodů.

27.2.

8 bodů
Ukažte pro jaký vstup je Eukliduv algoritmus nejpomalejsi (ten s modulem).

10 bodů
Nalezněte algoritmus počítající celočíselnou druhou odmocninu. Tím pro dané x myslíme přirozené číslo y takové, že y2≤ x < (y+1)2.

8 bodů
Nalezněte algoritmus, který najde v posloupnosti celých čísel nejdelší "kopec", tedy podposloupnost, která nejprve roste a pak klesá (ostře).
Pozor, podposloupnost není nutně souvislá!

6.3.

10 bodů
Naprogramujte bublinkové třídění na RAMu.

8 bodů
Jaká je průměrná časová složitost bublinkového třídění?
Přesněji: pokud dostaneme na vstupu náhodnou permutaci čísel 1 až n, jaká bude střední hodnota doby výpočtu?

10 bodů
Mějme čtvercovou matici o nXn prvcích. A povolme si na RAMu libovolně dlouhá čisla (ale operace na nich jsou stále v konstantním čase). Navrhněte co nejrychlejší algoritmus na vynásobení 2 takovychto matic.

20.3.



10 bodů
Mějme městečko, jehož uliční síť má tvar stromu: hrany jsou ulice, vrcholy křižovatky (či slepé konce). U každého vrcholu víme, kolik peněz stojí postavit tam strážníka. Rozmyslete, jak co nejlevněji rozmístit strážníky tak, aby každá ulice byla aspoň z jedné strany hlídaná.

10 bodů
Mějme souvislý graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?

8 bodů
Navrhněte algoritmus, který na vstupu dostane orientovaný vážený graf, jeho topologické setřídění a 2 vrcholy. Úkolem algoritmu je najít mezi zadanými vrcholy nejdelší cestu.

27.3.



8 bodů
Může v nějakém grafu existovat množina vrcholů, která by byla současně vrcholovým pokrytím i nezávislou množinou? Charakterizujte všechny případy, kdy to nastane.
Vrcholové pokrytí: každá hrana má v pokrytí alespoň jeden vrchol
Nezávislá množina: každá hrana má v nezávislé množině maximálně jeden vrchol

10 bodů
Housenka je graf, který se skládá z těla (cesta) a štětin (listy připojené k vrcholům cesty). Najděte v daném stromu podgraf s největším počtem vrcholů, který je isomorfní s nějakou housenkou.

10 bodů
V tomto textíku na straně 4 je popsán Bellman-Fordův algoritmus. Algoritmus zmodififikujeme tak, že si bude držet zásobník vrcholů místo fronty. Nalezněte graf, na kterém poběží exponenciálně dlouho.

3.4.



10 bodů
Chceme najít nejpropustnější cestu. To je taková, že minimum z ohodnocení hran na cestě je maximální možné.

10 bodů
Chceme najít nejspolehlivější cestu. To je taková, že součin ohodnocení hran (0-1) je co největší.

10 bodů
Konverze men: mějme měny 1...n a smenné kurzy r_{i,j} z i-té měny na j-tou. Existuje zpusob, jak si postupným směnováním vydelat?

10.4.



8 bodů
Dostanete graf a seznam vrcholů (nějaké vybrané). Máte najít minimální kostru grafu, která má vrcholy ze seznamu jako listy.

8 bodů
Najděte druhu nejlepší kostru.

10 bodů
Dokažte kontrakční lemma: Nechť G je graf, T jeho minimální kostra, e hrana ležící v T. Nechť dále G/e je graf vzniklý z G kontrakcí hrany e (se zachováním násobných hran a smyček). Potom T/e je minimální kostra grafu G/e. (Jinými slovy, minimální kostru můžeme získat tak, že uhodneme jednu hranu, která v ní leží, zkontrahujeme ji, rekurzivně najdeme min. kostru menšího grafu a tu pak "odkontrahujeme".)

17.4.



8 bodů
Ukažte, jak upravit vyhledávací strom, aby navíc uměl efektivně provádět operaci Rank(x,y), která odpoví, kolik vrcholů stromu leží v intervalu [x,y]. Složitost všech operací včetně této by měla být O(hloubka).

10 bodů
Dostanete množinu intervalů na přímce. Spočítejte kolik dvojic intervalů se protíná.

10 bodů
Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený.
Má to ale háček, máte jen tolik paměti kolik je velikost stromu a k tomu konstantní prostor navíc.

25.4.



8 bodů
Nechť A, B jsou dva (a,b) stromy takové, že všechny kliče v A jsou menší než všechny klíče v B. Vymyslete algoritmus, který oba stromy v logaritmickém čase sloučí do jednoho.

1.5.



10 bodů
Šrouby a Matice - máme N různých šroubů a N odpovídajících matic. Umíme pro dvojici (šroub, matice) rozlišit stavy "pasují", "šroub moc velký", "šroub moc mály".
Vymyslete, jak šrouby s maticemi co nejrychleji spárovat.
Nejrychlejší je v tomto případě O(n*log(n)) randomizovaně (pospomínejte na QuickSort).

8 bodů
Mějme text rozdělený na slova, potřebujeme spočítat četnost jednotlivých slov.
Zde vzpomeňte na hashování.

8.5.



10 bodů
Je dána posloupnost levých a pravých závorek délky N. Vymyslete datovou strukturu, která umí operace "otoč závorku na pozici i" a "zjisti, jestli je posloupnost dobře uzávorkovaná".

10 bodů
Dokažte, že pro množiny reprezentované binárními vyhledávacími stromy není možné spočítat sjednocení v lepším než lineárním čase, a to ani v případě, kdy na vstupu dostanete dokonale vyvážené stromy a výstup nemusí být vyvážený.

15.5.



8 bodů
Vymyslete upravu BubbleSortu, ktera bude tridit v case O(n + #inverzi).

22.5.



10 bodů
Na Manhattanu se každou chvíli něco děje a to něco je určeno dvojicemi (čas, křižovatka). Navrhněte trasu pro fotografa místního bulvárního tisku tak, aby začala i skončila v redakci (bod (0,0)) a v čase každé události se fotograf nacházel na stejné avenue nebo street, jako ona událost.

10 bodů
Definujme minimový strom takto: v kořeni je minimum posloupnosti, levý podstrom je minimový strom prvků nalevo od minima, pravý analogicky. Vymyslete algoritmus, který v čase O(n) takový strom sestrojí.


Body

Jméno Úkoly Celkem
Jakub Pekárek euklid(8) sqrt(10) bubble(10) kopec(8) del(10) pok+nez(8) cesta(8) spoleh(10) propust(10) list-ST(8) 90 + 10
Michal Pokorný sqrt(10) euklid(8) bubble(10) matice(10) del(10) cesta(8) pokryti(10) pok+nez(8) exp(10) housenka(10) smena(10) spoleh(10) propust(10) 124
Petr Bělohlávek euklid(8) sqrt(10) kopec(8) bubble(10) perm(8) pokryti(10) del(10) pok+nez(8) cesta(8) smena(10) propust(10) zas_B-F(10) 110
Jan Klůj sqrt(10) euklid(8) bubble(10) perm(8) del(10) cesta(8) pokryti(10) zas_B-F(5) propust(10) spoleh(10) smena(10) 2-kostra(8) 107
Vojtěch Černý kopec(8) bubble(10) perm(8) sqrt(10) del(10) pokryti(10) cesta(8) pok+nez(8) smena(10) spoleh(10) propust(10) 102
Bedřich Pišl kopec(8) sqrt(10) euklid(8) bubble(10) perm(8) del(10) pokryti(10) pok+nez(8) housenka(10) propust(10) smeny(6) spoleh(10) 108
fifacz sqrt(10) euklid(8) bubble(10) perm(8) pokryti(10) del(10) cesta(8) kopec(4) spoleh(10) smeny(10) 2-kostra(8) sro+mat(10) cetnost(8) 114
Tru Hoang Van sqrt(10) euklid(8) bubble(10) pok+nez(5) del(5) list-ST(8) housenka(10) 2-kostra(8) rank(8) spojeni(8) int(10) spoleh(10) propust(10) 110
Jan Buchar sqrt(10) euklid(8) bubble(10) perm(8) del(10) cesta(8) pok+nez(8) zas_B-F(10) spoleh(10) list-ST(8) smena(10) 100
Martin Mirbauer sqrt(10) euklid(8) bubble(10) del(10) cesta(8) pok+nez(8) propust(10) list-ST(8) spoleh(10) rank(8) sro+mat(10) 100
Filip Šedivý sqrt(10) euklid(8) bubble(10) kopec(4) del(10) spoleh(10) perm(4) cesta(4) rank(8) zas_B-F(5) 2-kostra(4) smena(5) intervaly(10) propust(5) sro+mat(10) pokryti(5) 112 + 8
Michal Hruška sqrt(10) euklid(8) bubble(10) del(10) spoleh(10) propoust(10) rank(8) intervaly(10) 2-kostra(8) sro+mat(10) spojeni(8) zavorky(10) 102
Anikó Kuklis euklid(8) perm(8) bubble(10) sqrt(5) spoleh(10) kontrakce(5) housenka(5) pok+nez(4) intervaly(10) pokryti(5) del(5) sro+mat(10) 2-kostra(4) rank(4) zavorky(10) 103
Marek Behún euklid(4) sqrt(5) perm(4) cesta(4) list-ST(4) bubble(5) spoleh(5) smeny(5) perm2(4) inverze(8) sro+mat(10) kontrakce(5) exp(5) hash(4) pok+nez(4) rank(4) zavorky(10) intervaly(5) matice(5) 100
Margarita Vishnyakova euklid(4) bubble(10) del(10) pok+nez(8) housenka(10) propust(10) spoleh(10) kont-ST(10) sro+mat(10) hash(10) minima(10) 102
Imrich Kuklis euklid(8) perm(8) bubble(10) sqrt(10) del(10) spoleh(10) smeny(10) intervaly(10) rank(8) cetnost(4) sro+mat(10) sjednoceni(10) 108
Jiří Erhart bubble(10) del(10) pok+nez(8) intervaly(10) sro+mat(10) cetnost(8) spoleh(5) sqrt(5) cesta(4) list-ST(4) propust(5) inverze(10) euklid(4) minima(10) 103
Lenka Janišová euklid(8) bubble(10) 18
David Čepelík matice(10) bubble(10) euklid(8) sqrt(5) 33
Tibor Mosko bubble(10) perm(6) sqrt(6) cesta(8) 30
Andrei Yakubouski 0



Náplň cvičení

20.2.

Hříčky s rekurzivními funkcemi.

27.2.

Seznámení se s RAMem.
Euklidův algoritmus na RAMu.

6.3.

Hříčky s O-notací.
Erastenovo síto - RAM + složitost.

13.3.

Algoritmy BFS a DFS.
Hledaní společných podposloupností, editační vzdálenosti.

20.3.

Hledání mostů a artikulací.
Hledání komponent silné souvislosti.

27.3.

Relaxační algoritmy a hledání nejkratších cest.

3.4.

Dijkstrův algoritmus, jeho aplikace a modifikace.

10.4.

Hledání nejmenších koster.

17.4.

Binární vyhledávací stormy, hledání následníka. Hledání k-tého nejmenšího prvku. Vyvažování BVS.

25.4.

(a, b)-stromy, jejich vlastnosti a používání. Modifikace vyhledávacích stromů - např. hledání minima z intervalu.

1.5.

Statní svátek

8.5.

Statní svátek

15.5.

Hashování. Složitost mocnění. MergeSort.

22.5.

Počítání časových rekurzí.
Lexikografické třídění k-tic.