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 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ě.
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 |
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í:
|
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
|
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 |
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 | |||