Cvičení z Algoritmů a datových struktur 1 – Pondělí v 15:40 v S6

Podmínky zápočtu

Nasbírat alespoň 2/3 všech možných bodů, což předběžně vychází na 73. Pokud budete mít alespoň půlku (55), můžeme se dohodnout na nějakém alternativním způsobu získání zápočtu.

Domácí úkoly

Domácí úkoly budou typicky zadávány na cvičení a zadání se bude objevovat i na těchto stránkách. Budete-li mít s řešeními nějaký problém, můžete mi napsat a třeba vám pošlu nějakou nápovědu. Nad řešeními domácích úloh můžete přemýšlet i skupinově, řešení ale sepište každý sám. K tomu, jak vypadá matematický důkaz, najdete pár stručných rad zde (návod byl původně vytvořen pro potřeby diskrétky, ale i na ADSka se z velké části aplikuje).

Na odevzdávání sepsaných úkolů najdete návod tady.

Jsem si vědom faktu, že řešení některých domácích úloh lze najít na internetu. Na některá témata prostě neexistuje dostatek přiměřeně obtížných a přitom pěkných příkladů. Cílem domácích úkolů je ale připravit vás na zkoušku. Pokud se rozhodnete, že řešení raději vygooglíte, jste sami proti sobě.

Náplň cvičení

Datum Náplň cvičení Handout Poznámka
1. 18. 2. 2019 Úvod do Očkové notace Zde
2. 25. 2. 2019 Programování na RAMu Zde
3. 4. 3. 2019 BFS a jeho aplikace Není Toto cvičení vedl Petr Kučera
4. 11. 3. 2019 Další aplikace BFS. DFS a topologické třídění. Letmý dotek silně souvislých komponent. Zde
5. 18. 3. 2019 Pokračování aplikací topologického třídění a silně souvislých komponent. Nejkratší cesty, Dijkstra a další algoritmy Zde
6. 25. 3. 2019 Dijkstra a Bellman-Ford Zde
7. 1. 4. 2019 Kostry. Představení Borůvkova algoritmu Zde
8. 8. 4. 2019 Stromy. Něco málo o AVL. Zde
9. 15. 4. 2019 Další stromy Zde
10. 22. 4. 2019 Rozděl a panuj 1 Zde
11. 6. 5. 2019 Rozděl a panuj 2. Master theorem. Zde
12. 13. 5. 2019 Rozděl a panuj 3. Hashování. Zde
13. 20. 5. 2019 Hashování. Euklidův algoritmus. Zde

Domácí úkoly

Pokud je v den deadline cvičení, myslí se jeho začátek. Pokud ne, myslí se půlnoc, kterou příslušný den končí.

Jméno Datum zadání Deadline Zadání Body Poznámka
ram 25. 2. 2019 11. 3. 2019 Naprogramujte bubblesort na RAMu a spočítejte počet instrukcí (v nejhorším případě) na vstupu délky n. 10
kun 8. 3. 2019 22. 3. 2019 Kůň Šemík si vesele skákal po šachovnici n×n. Zlá čarodějnice ho zaklela, takže nyní se musí v lichých tazích pohybovat jako kůň, ale v sudých se musí pohnout o jedno políčko šikmo doprava a nahoru. Aby se své kletby zbavil, musí stoupnout na políčko, kde má čarodějnice postavený svůj domeček. Navrhněte mu algoritmus, kterým zjistí, jak se na toto políčko dostane pomocí nejmenšího možného počtu kroků. 10
polo 11. 3. 2019 25. 3. 2019 O orientovaném grafu řekneme, že je polosouvislý, pokud pro každé dva vrcholy u, v existuje orientovaná cesta z u do v nebo z v do u (nebo obě). Navrhněte co nejrychlejší algoitmus, který rozhodne, zda je daný orientovaný graf polosouvislý. Neslibuji vám, že máte před přednáškou v týdnu 11.–15. 3. dost informací k vyřešení tohoto úkolu. 10
15. 3. 2019 1. 4. 2019 Z úkolů path1, path2, path3 a path4 si vyberte nejvýše jeden. Do maxima se počítá úkol path3.
path1 Máte zadaný graf a v něm vrcholy u,v. Některé hrany grafu mají délku 1 a jiné n, kde n je počet vrcholů grafu. Vymyslete lineární (tj. O(m+n), kde m je počet hran grafu) algoritmus k nalezení nejkratší cesty z u do v. 5
path2 Máte zadaný graf a v něm vrcholy u,v. Některé hrany grafu mají délku 1 a jiné a, kde a je nějaké nezáporné reálné číslo. Vymyslete lineární (tj. O(m+n), kde m je počet hran grafu) algoritmus k nalezení nejkratší cesty z u do v. 8
path3 Máte zadaný ohodnocený graf takový, že hrany mají pouze K různých délek. a v něm vrcholy u,v. Vymyslete algoritmus k nalezení nejkratší cesty z u do v, který poběží v O(K×(m+n)) 10
path3 Máte zadaný ohodnocený graf takový, že hrany mají pouze K různých délek. a v něm vrcholy u,v. Vymyslete algoritmus k nalezení nejkratší cesty z u do v, který poběží v O(log (K)×(m+n)) 15
check 25. 3. 2019 8. 4. 2019 Alici by moc zajímalo, jak se dostane z každé křižovatky svého rodného domu co nejkratší cestou domů. Našla si mapu, kde je ke každé spojnici dvou křižovatek uvedena její délka. Protože však sama neprošla předmětem ADS 1 a tedy nezná žádný algoritmus, kterým by nejkratší cesty našla, požádala o pomoc svého kamaráda Boba. Zadala mu tedy, aby ke každé křižovatce i spočítal hodnoty di a pi, kde první z nich značí vzdálenost křižovatky od Alicina domu a druhý je ukazatelem na křižovatku, na kterou se má jako první ze své současné křižovatky vydat, pokud chce dojít domů nejkratší cestou. di má být nekonečno pro křižovatky, na něž se od Alicina domu nejde dostat (Alice bydlí v divném městě), ty pak mají mít, stejně jako Alicin dům, pi nastavený na hodnotu NULL. V Alicině městě se ale současně testuje nový systém teleportů, takže některé dvojice křižovatek mohou mít vzdálenost nula (záporné cesty ve městě nejsou, až tak divné není). Protože chce Alice pěší cesty, jsou všechny silnice (i teleporty) obousměrné (a v obou směrech stejně dlouhé)
Alice však Bobovi příliš nevěří, rozhodla se tedy, že po něm výpočet zkontroluje. Pro každý vrchol v tedy ověří následující:
  • Je-li v křižovatka, na níž je Alicin dům, pak dv=0 a pv=NULL
  • Je-li dv roven nekonečnu, pak je pv=NULL a di všech vrcholů i, které sousedí s v, je též nekonečno
  • Je-li dv konečný, ale v není Alicin dům, pak pv není NULL a dále pokud d(i,j) je délka spojnice mezi i a j, pak dv=d(v,pv)+dpv a současně je dv minimem z d(v,i) + di přes všechny sousedy i vrcholu v
Rozhodněte, zda, pokud Alice tímto testem neodhalila žádné problémy, pak už Bob nutně splnil její zadání. 		10
druha 3. 4. 2019 17. 4. 2019 Mějme graf s unikátními váhami hran. Najděte druhou nejlehčí kostru. Pokud vám to pomůže, může váš algoritmus dostat jako vstup krom grafu i minimální kostru v něm. Na plný počet bodů však není potřeba optimální řešení.
Nápověda: Nejprve si zkuste dokázat, že existuje alespoň jedna druhá nejlehčí kostra, která se od nejlehčí liší pouze výměnou jedné hrany. Za důkaz tohoto tvrzení dostanete částečné body. Též můžete získat částečné body za algoritmus využívající toto tvrzení, aniž byste ho dokázali. 		10
k-tý 8. 4. 2019 29. 4. 2019 Upravte AVL strom tak, abyste krom běžných operací navíc ještě dokázali pro libovolné 0 < k ≤ n najít k-tý nejmenší prvek v čase O(log n). Pokud se rozhodnete přidat si do vrcholů nějaké další informace, nezapomeňte popsat, jak je udržujete při vkládání, mazání a vyvažování 10
succ 13. 4. 2019 6. 5. 2019 Mějme vyhledávací strom s n vrcholy. Dokažte, že začneme-li v libovolném vrcholu a pak budeme k-krát hledat následníka, potrvá to O(k + hloubka stromu). 10
sroub 30. 4. 2019 13. 5. 2019 Dostali jste krabici n šroubků a krabici n matiček. Každé dva šroubky jsou různě velké a na kždý z nich pasuje právě jedna matička. JEdinou operaci, kterou smíte dělat, je pokusit se nasadit šroubek na matičku -- zjistíte, že je buď matička příliš velká, nebo příliš malá, nebo že pasuje. Na kolik nejméně pokusů v průměrném případě umíte přiřadit všechny matičky ke šroubkům? 10
rek 13. 5. 2019 Na tento a následující úkol máte teoreticky čas až do konce září. Ve zkouškovém a po něm však budu na maily reagovat ještě pomaleji než v semestru, a pokud úkol odevzdáte později než dejme tomu v půlce září, už vám neslibuji, že ho vůbec stihnu opravit.
Vyřešte následující dvě rekurence
  • T(n) = 3T(n/2) + O(1), T(1) = 1
  • T(n) = T(n/3) + T(n/7) + O(n), T(1) = 1
 10
euk 20. 5. 2019 Binární algoritmus na výpočet GCD funguje takto: Pokud x i y jsou sudá, pak gcd(x, y) = 2 gcd(x/2, y/2). Je-li x sudé a y liché, pak gcd(x, y) = gcd(x/2, y). Jsou-li obě lichá, odečteme menší od většího. Zastavíme se, až bude x = y. Dokažte, že tento algoritmus funguje a že provede nejvýše c(log x+ log y) kroků pro vhodnou konstantu c. 10

Body

Je-li v tabulce hvězdička, znamená to, že beru na vědomí, že jsem úkol dostal, ale ještě jsem ho neopravil.

Jméno Aktivita Domácí úkoly Součet
MAximum:0