Warning
This page is located in archive.

Rozvrh na FEL Posluchači ALG Odevzdávací systém BRUTE Diskusní fórum

V letním semestru 2017/2018 jsou přednášky a cvičení organizovány společně s předmětem 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 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í 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
První domácí úloha , Její ladící veřejná data: datapub.zip.

Druhá domácí úloha, její ladící veřejná data: datapub2.zip.

Třetí domácí úloha, její ladící veřejná data: datapub3.zip.

Čtvrtá domácí úloha, její ladící veřejná data: datapub4.zip.

Pátá domácí úloha, její ladící veřejná data: 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: Plagiáty.

Upload systém
Komunikace s upload systémem je popsána v oddílu 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í – pdf

Cvičení Prezentace Prezentace 14.30, 16.15 Kódy Další materiály
1. pdf pdf jednoduché pomocné výpočty: pdf, řešené příklady
2. pdf pdf
3. pdf pdf zip
4. pdf2 pdf zip simulace 1, simulace 2, kolekce
5. pdf, pdf pdf zip
6. pdf pdf zip, řešeni
7. pdf pdf zip
8. pdf a pdf a docx pdf
9. Není přednáška, opakování témat 1.-5. Některé náměty: zde, pdf
10. pdf, rozšířená v doc. pdf zip, řešeni
11. pdf plus protoslidy pdf DP pro LCS
12. pdf
13. Odpadá - rektorský den
14. pdf pdf

Úlohy k procvičování a zkoušce

Řád růstu funkcí a asymptotická složitost
Bez řešení a_complex_alg_unsol.pdf a s řešením a_complex_alg.pdf
Rekurze
Bez řešení b_recur_alg_unsol.pdf a s řešením b_recur_alg.pdf
Stromy, průchod stromy
Bez řešení c_treestq_alg_unsol.pdf a s řešením c_treestq_alg.pdf
Vyhledávací stromy
Bez řešení d_bst_avl_b_alg_unsol.pdf a s řešením d_bst_avl_b_alg.pdf
Řazení
Bez řešení e_sort_alg_unsol.pdf a s řešením e_sort_alg.pdf
Hash (rozptylovací tabulky)
Bez řešení f_hash_alg_unsol.pdf a s řešením f_hash_alg.pdf
Dynamické programování
Bez řešení g_dynpgm_alg_unsol.pdf a s řešením g_dynpgm_alg.pdf

courses/a4b33alg/cviceni.txt · Last modified: 2018/05/05 20:31 by berezovs