[[http://www.fel.cvut.cz/cz/education/rozvrhy-ng.B172/public/html/predmety/12/57/p12579904.html|Rozvrh na FEL]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B172/public/html/paralelky/P12/57/par12579904.1.html|Posluchači ALG]] [[https://cw.felk.cvut.cz/brute/|Odevzdávací systém BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1489.html|Diskusní fórum]] V letním semestru 2017/2018 jsou přednášky a cvičení organizovány společně s předmětem [[https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/start| DSA (odkaz)]]. \\ Domácí úlohy, zápočet a zkouška probíhají podle pravidel ALG popsaných na těchto stránkách ALG. ====== Cvičení ====== ===== Provoz v semestru ===== **Programovací úlohy**\\ Semestr obsahuje 8 domácích programovacích úloh sumárně ohodnocených 16 body, z čehož je k získání zápočtu nutno získat alespoň 8 bodů. Úlohy jsou zadávány a řešení vyhodnocována prostřednictvím [[https://cw.felk.cvut.cz/brute//|odevzdávacího systému BRUTE]]. * Každá úloha implementuje některé téma přednášky, toto téma může být pouze dílčí částí úlohy. K řešení může být někdy vhodné nastudovat samostatně některý z dalších běžných algoritmů neprobíraných v přednáškách ALG (např. minimální kostry, nejkratší cesty apod.) * Akceptované řešení úlohy je takové, které správně spočte výsledky na alespoň 9 z 10 testovacích souborů. * Řešení musí být také efektivně naprogramováno, každý datový soubor má stanovený časový limit, do nějž musí být data zpracována a vypsán výsledek. Limit je většinou dvojnásobek času, za který soubor zpracuje autorské referenční řešení v Javě. Limit se zaokrouhluje nahoru na celé sekundy, typicky nepřekračuje 5-10 vteřin. * Termíny úloh je třeba dodržet, lze je prodloužit pouze individuálně v odůvodněných případech (nemoc, zahraniční cesta apod). * Individuálně se lze domlouvat o posunutí termínu, když o to student s předstihem požádá. * Otázky týkající se domácích uloh i dalších událostí během semestru je vhodné řešit pomocí [[https://cw.felk.cvut.cz/forum/forum-1389.html|diskusního fóra ALG]]. **Termíny a hodnocení domácích úloh **\\ zadání -- odevzdání 1. 23.2. -- 22.3. ( Asymptotic complexity ) 2. 9.3. -- 29.3. ( Tree traversal ) 3. 16.3. -- 5.4. ( Graph search ) 4. 23.3. -- 12.4. ( Graph search ) 5. 30.3. -- 19.4. ( BST processing ) 6. 6.4. -- 26.4. ( AVL processing ) 7. 7.4. -- 3.5. ( DP ) 8. 20.4. -- 10.5. ( DP ) Správně spočtených 10 z 10 testovacích případů ... 2 body Správně spočtených 9 z 10 testovacích případů ... 1 bod Správně spočtených 8 nebo méně testovacích případů ... 0 bodů **Zadání domácích úloh **\\ {{ :courses:a4b33alg:desc.pdf | První domácí úloha }}, Její ladící veřejná data: {{ :courses:a4b33alg:datapub.zip |}}. {{ :courses:a4b33alg:fullpaths.pdf | Druhá domácí úloha}}, její ladící veřejná data: {{ :courses:a4b33alg:datapub2.zip |}}. {{ :courses:a4b33alg:colorgraph.pdf | Třetí domácí úloha}}, její ladící veřejná data: {{ :courses:a4b33alg:datapub3.zip |}}. {{ :courses:a4b33alg:colorgraphii.pdf | Čtvrtá domácí úloha}}, její ladící veřejná data: {{ :courses:a4b33alg:datapub4.zip |}}. {{ :courses:a4b33alg:colorgraph3.pdf | Pátá domácí úloha}}, její ladící veřejná data: {{ :courses:a4b33alg:datapub5.zip |}}. **Zápočet**\\ Kromě minima 10 z možných 16 bodů za řešení úloh je ke získání zápočtu nezbytná pravidelná docházka do cvičení s max. 2 neomluvenými absencemi. Předpokládáme, že posluchači se vyvarují odevzdávání plagiátů a seznámí se s pravidly uvedenými na společné stránce: [[help:common:plagiaty_opisovani| Plagiáty]].\\ **Upload systém**\\ Komunikace s upload systémem je popsána v oddílu [[courses:a4b33alg:upload_system| Upload System]].\\ Každou úlohu doprovází sada neveřejných testovacích souborů a sada veřejných souborů se správnými výsledky. Veřejné soubory jsou uloženy v odevzdávacím systému a systém spouští řešitelovu úlohu pokaždé rovněž na těchto datech a vrací řešiteli kompletní výstup jeho řešení na STDOUT a STDERR pro každý veřejný soubor. Veřejné soubory jsou součástí zadání úlohy a jejich obsah je podobný obsahu testovacích souborů a poskytuje tak další příležitost k účinnému ladění. Počet testovacích a veřejných souborů není pevně určen a pro různé úlohy se může lišit, zejména veřejné soubory mohou z trénovacích důvodů zcela chybět.\\ ===== Materiály na cvičení ===== Tabulka s porovnáním složitostí -- {{:courses:a4b33alg:cviceni_-_slozitost_-_tabulka.pdf| pdf}} \\ ^ Cvičení ^ Prezentace ^ Prezentace 14.30, 16.15 ^ Kódy ^ Další materiály ^ | **1.** | {{:courses:a4b33alg:cviceni02upd.pdf|pdf}} | {{:courses:a4b33alg:cviceni1resene.pdf|pdf}} | | jednoduché pomocné výpočty: {{:courses:a4b33alg:cviceni01upd.pdf| pdf}}, {{:courses:a4b33alg:a4b33alg_s01_solutions.pdf| řešené příklady}} | | **2.** | {{:courses:a4b33alg:cviceni03upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni2resene.pdf| pdf}} | | | | **3.** | {{:courses:a4b33alg:cviceni04upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni3resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni3code.zip| zip}} | | | **4.** | {{:courses:a4b33alg:cv05stromgrafnosol.pdf|pdf2}} | {{:courses:a4b33alg:cviceni4resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni4problem5.zip| zip}} | [[http://akidsheart.com/math/mathgames/leapfrog.htm|simulace 1]], [[http://www.learn4good.com/games/puzzle/boat.htm|simulace 2]], {{:courses:a4b33alg:a4b33alg_s04_collections1.pdf|kolekce}} | | **5.** | {{:courses:a4b33alg:cviceni07upd.pdf|pdf}}, {{:courses:a4b33alg:cviceni_05.pdf|pdf}} | {{:courses:a4b33alg:cviceni5resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni5code.zip| zip}} | | | **6.** | {{:courses:a4b33alg:cv06_2017_avl.pdf| pdf }} | {{:courses:a4b33alg:cviceni7resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni7code.zip| zip}}, {{:courses:a4b33alg:tree.java|řešeni}} | | | **7.** | {{:courses:a4b33alg:cviceni05upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni8resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni8code.zip| zip}} | | | **8.** | {{:courses:a4b33alg:cviceni_09x.pdf| pdf}} a {{:courses:a4b33alg:cviceni_10x.pdf| pdf}} a {{:courses:a4b33alg:cv10sorty3.docx| docx }} | {{:courses:a4b33alg:cviceni9.pdf| pdf}} | | | | **9.** | Není přednáška, opakování témat 1.-5. Některé náměty: {{:courses:a4b33alg:cv06.doc| zde}}, | {{:courses:a4b33alg:cviceni6resene.pdf| pdf}} | | | | **10.** | {{:courses:a4b33alg:cv10.pdf| pdf}}, rozšířená v {{:courses:a4b33alg:cv10.doc| doc.}} | {{:courses:a4b33alg:cviceni10resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni10code.zip| zip}}, {{:courses:a4b33alg:dynamicprogramming.java|řešeni}} | | | **11.** | {{:courses:a4b33alg:cvi11.pdf| pdf}} plus {{:courses:a4b33alg:protosli11.docx| protoslidy}} | {{:courses:a4b33alg:cviceni11.pdf| pdf}} | {{:courses:a4b33alg:main.java| DP pro LCS}} | | | **12.** | {{:courses:a4b33alg:cvi12.pdf| pdf}} | | **13.** | Odpadá - rektorský den | | **14.** | {{:courses:a4b33alg:cviceni_12.pdf| pdf}} | {{:courses:a4b33alg:cviceni12resene.pdf| pdf}} | ===== Úlohy k procvičování a zkoušce ===== **Řád růstu funkcí a asymptotická složitost**\\ Bez řešení {{:courses:a4b33alg:a_complex_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:a_complex_alg.pdf|}} \\ **Rekurze**\\ Bez řešení {{:courses:a4b33alg:b_recur_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:b_recur_alg.pdf|}}\\ **Stromy, průchod stromy**\\ Bez řešení {{:courses:a4b33alg:c_treestq_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:c_treestq_alg.pdf|}} \\ **Vyhledávací stromy**\\ Bez řešení {{:courses:a4b33alg:d_bst_avl_b_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:d_bst_avl_b_alg.pdf|}} \\ **Řazení**\\ Bez řešení {{:courses:a4b33alg:e_sort_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:e_sort_alg.pdf|}} \\ **Hash (rozptylovací tabulky)**\\ Bez řešení {{:courses:a4b33alg:f_hash_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:f_hash_alg.pdf|}} \\ **Dynamické programování**\\ Bez řešení {{:courses:a4b33alg:g_dynpgm_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:g_dynpgm_alg.pdf|}} \\