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

DatumKódBodyZadání
5. 10. funf5Co dělá funkce f() z letáčku? Odpověď nezapomeňte zdůvodnit.
funb5Co dělá funkce bc() z letáčku? Odpověď nezapomeňte zdůvodnit.
2mis10Princezně 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. rep310Je 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.
mdpx10Vymyslete 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. okmin10Je 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. kmaj15Uvaž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. perm10Naprogramujte 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ší ednič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.
Stránku spravuje Martin Mareš