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

Ve školním roce 2018/2019 vedeme s Jirkou Sejkorou 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é pondělí od 14:00 v S10. 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í
1. 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é?
22. 10. 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.
29. 10. imed8Ukažte, jak pomocí výpočtu okénkového mediánu třídit. Přesněji řečeno dokažte, že máme-li algoritmus pro medián okénka velikosti k pracující v čase lepším než Θ(log k), lze z něj sestrojit třídicí algoritmus se složitostí lepší než Θ(n log n).

Výsledky

JménoTeoretické příkladyCodExBodůZápočťák
Patrik Beliansky6969 Maticová knihovna
Filip Čermák2mis(10) funf(5) mdpx(10) funb(5)6494 Binomiální halda
Peter Fačko2828
Petr Gebauer2mis(10) funf(5)7489 Intervalové stromy
Nodari Gogatishvili2mis(10)1828
Břetislav Hájek9090 Doplňování diakritiky
Miroslav Hrabal6464 Piškvorky
Michal Hýsek5050 Nejbližší dvojice bodů
Viktor Jančík2mis(10)7484 Pružinkový model grafu
Martin Koreček2mis(10) funf(5) funb(5) mdpx(10)6090 Lineární rovnice
Tomáš Korenýfunf(5)5055
Jakub Kozel88
Tomáš Kubíček2mis(10) funf(5) funb(5) mdpx(10)6090 Kalkulačka s velkými čísly
Filip Masár7474 Intervalový strom
Jakub Medek6060
Matěj Míček5050 Simulace rostlin
Ondřej Mózesfunf(5)1823 Hangman
Jakub Pelcfunf(5) funb(5) mdpx(10) imed(8)74102 Aurora Renderer
Jiří Škrobánekfunf(5) funb(5) 2mis(10) mdpx(10) imed(8)64102 (a,b)-stromy
Tomáš Zeman2mis(10)3545 Netradiční kalkulačka

Pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, dejte nám vědět.

Co jsme dělali

datum co se cvičilo
1. 10. Jedno chybějící číslo. Házení vajíček z mrakodrapu.
8. 10. Nejdelší úsek bez opakování. Úsek s maximálním součtem. Úsek se zadaným součtem.
15. 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í.
22. 10. Největší jedničková podmatice na mnoho způsobů (zadané velikosti, zadané výšky, čtvercová, libovolná). Podmatice s maximálním součtem.
29. 10. Okénkova minima a mediány.
5. 11. Náhodné permutace a k-tice. Randomizované třídicí algoritmy.
12. 11. Nápovědy k praktickým úkolům. Rozvrhování přednášek a intervalové grafy.
19. 11. 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.
26. 11. Rank a unrank permutace, konstrukce lexikograficky následující permutace. (Zaskakoval Pavel Turinský.)
3. 12. O stromech, strážnících a mafiánech váženě i neváženě.
10. 12. Ještě o strážnících a mafiánech.
Stránku spravuje Martin Mareš