Cvičení z Programování I pro pokročilé

Ve školním roce 2015/2016 vedeme s Ondrou Hlavatý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.

Cvičení se koná každé úterý od 9:00 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. Také se můžete podívat na reklamní letáček.

Svým cvičícím pište na adresu mami@ucw.cz.

Teoretické úkoly

Datum	Kód	Body	Zadání
13. 10.	funf	5	Co dělá funkce f() z letáčku? Odpověď nezapomeňte zdůvodnit.
13. 10.	funb	5	Co dělá funkce bc() z letáčku? Odpověď nezapomeňte zdůvodnit.
27. 10.	mdpx	15	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.
10. 11.	volby	15	Mějme K kandidátů, N voličů a přirozené číslo T≥2. Každý volič hlasuje pro jednoho kandidáta. Chceme najít všechny kandidáty, pro které hlasuje víc než N/T voličů. Víme, že N je větší než množství dostupné paměti a rozsah čísel kandidátů je ještě větší.
12. 1.	jerab	20	Vymyslete datovou strukturu pro zjišťování pozic háků stromového jeřábu. Měla by podporovat operace "otoč úsekem X o Y stupňů okolo kloubu, na němž je připojen" a "zjisti pozici háku H".
12. 1.	kvadr	20	Vymyslete lepší než kvadratické řešení na úlohu o kvádru z prken.

Co jsme dělali

datum	co se cvičilo
6. 10.	Pár příkladů na úvod: Chybějící číslo (aneb princeznin náhrdelník). Co když chybí čísla dvě? Cestovatelův deník (nejčastější výška).
13. 10.	Házení vajíček z mrakodrapu.
20. 10.	Úlohy o posloupnostech: úsek s daným součtem, úsek s maximálním součtem. Nejdelší bílý úsek v posloupnosti RGB a souvislost s přihrádkovým tříděním.
27. 10.	Úlohy o maticích: podmatice s maximálním součtem, podmatice se zadaným součtem. Dvojrozměrné prefixové součty.
3. 11.	Největší prázdná podmatice: zadané velikosti, čtvercová, libovolná. Hledání v setříděné matici a jemné umění dolních odhadů.
10. 11.	Volby na mnoho způsobů: bity, randomizace, velká čísla a konečně i lineární řešení.
17. 11.	Cvičení se nekoná. Vyberte si svůj svátek :)
24. 11.	Generování všech objektů s danou vlastností: posloupnosti nul a jedniček, právě k jedniček, právě jedna změna.
1. 12.	Generování permutací: lexikografický následník a mnoho způsobů, jak generovat náhodnou permutaci.
8. 12.	O stromech, strážnících a mafiánech (neváženě, váženě, vypočítavě).
15. 12.	Mafiáni v podzemí, asfaltéři na povrchu.
22. 12.	Ještě jednou asfaltéři, tentokrát v obecných grafech. Bipartitní podgraf s alespoň polovinou hran.
5. 1.	Vyvážená a skorovyvážená orientace grafů. Barvení rovinných grafů 6 a 5 barvami.
12. 1.	Jeřábníkovy starosti. Pokrývání bažiny hatěmi. Kvádr z prken.