Cvičení z Programování I pro pokročilé
Ve školním roce 2017/2018 vedeme s Filipem Štědronským speciální cvičení z předmětu Programování I [NPRG030] pro pokročilé studenty, kteří již nasbírali nějaké zkušenosti z programování (třeba v olympiádách a korespondenčních seminářích) a chtěli by se naučit víc. Podívejte se na reklamní letáček.
Cvičení se koná každý čtvrtek od 15:40 v S8. Kdo chcete chodit, přihlašte se, prosíme, v SISu, případně nám pošlete mail, pokud vám to SIS nedovolí.
Podmínky na získání zápočtu najdete v pravidlech hry.
Svým cvičícím pište na adresu mami@ucw.cz.
Teoretické úkoly
| Datum | Kód | Body | Zadání |
|---|---|---|---|
| 5. 10. | funf | 5 | Co dělá funkce f() z letáčku? Odpověď nezapomeňte zdůvodnit. |
| funb | 5 | Co dělá funkce bc() z letáčku? Odpověď nezapomeňte zdůvodnit. | |
| 2mis | 10 | Princezně se rozsypaly perly z náhrdelníku (očíslované 1 až N) a dvě z nich se ztratily. Jak v lineárním čase a konstantní paměti zjistit, které? | |
| 26. 10. | rep3 | 10 | Je dána posloupnost n čísel z rozsahu 0, … n3-1. Nalezněte v čase O(n) nejdelší úsek, v němž se žádné číslo neopakuje. |
| mdpx | 10 | Vymyslete d-rozměrnou variantu prefixových součtů, tedy strukturu, která si pro d-rozměrnou matici v lineárním čase něco předpočítá a pak bude umět v konstantním čase vypočíst součet libovolné d-rozměrné souvislé podmatice. Předpokládejte, že d je konstanta. | |
| 16. 11. | okmin | 10 | Je dána posloupnost celých čísel. Pro každé k zjistěte, jaké je maximum z minim okének délky k. Existuje řešení v lineárním čase. |
| 30. 11. | kmaj | 15 | Uvažujme následující variantu úlohy o volbách: je dáno k, chceme najít všechny kandidáty, kteří dostali víc než jednu (k+1)-tinu všech hlasů. Opět chceme lineární čas, spotřeba paměti smí záviset pouze na k. |
| 14. 12. | perm | 10 | Naprogramujte rekurzivní generátor permutací z cvičení tak, aby měl časovou složitost O(n!) bez vypisování permutací. |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 5. 10. | Jedno chybějící číslo. Číslo s lichým počtem výskytů. Robin Hood a euklidovská lukostřelba. Robin Hood a předvolební billboardy. |
| 12. 10. | Nejdelší úsek bez opakování. Úsek se zadaným součtem. |
| 19. 10. | Nejdelší vyvážený úsek. Úsek se zadaným průměrem. Nejdelší bílý úsek, komplexní čísla a přihrádkové třídění. |
| 26. 10. | Nejkratší úsek obsahující všechny prvky. Největší jedničková podmatice na mnoho způsobů (zadané velikosti, zadané výšky, čtvercová, libovolná). Okénková minima. |
| 2. 11. | Pokračování z minula. |
| 9. 11. | Okénkové mediány. Jak pro každou velikost okénka zjistit maximum z minim. Předvýpočet: nejbližší vyšší prvek oběma směry. |
| 16. 11. | Náhodné permutace a k-tice. Randomizované třídicí algoritmy. |
| 23. 11. | Cvičení se nekoná, dnes otevíráme dveře. |
| 30. 11. | Volby na mnoho způsobů: randomizace, různé druhy půlení intervalu, lineární řešení. |
| 7. 12. | Generování všech objektů s danou vlastností: posloupnosti nul a jedniček, právě jedna změna, nejvýše k jedniček za sebou. |
| 14. 12. | Generování permutací: rekurze, lexikografický následník, rank a unrank. |
| 21. 12. | O stromech a strážnících váženě i neváženě. |
| 4. 1. | O strážnících, mafiánech a asfaltérech. |
| 11. 1. | Asfaltování obecných grafů. Mafiánský kápo. Barvení rovinných grafů 6 a 5 barvami. |