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

Ve školním roce 2016/2017 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ždou středu 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. Také se můžete podívat na reklamní letáček.

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.
6. 10. 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é?
12. 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.
2. 11. 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. 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-tinu všech hlasů. Opět chceme lineární čas, spotřeba paměti smí záviset pouze na k.
11. 1. color10Uvažujme následující algoritmus na barvení rovinných grafů: Vyberu libovolný vrchol stupně nejvýše 5. Obarvím ho barvou s nejmenším číslem, kterou ještě nepoužívají sousedé. Opakuji, přičemž do stupně už nezapočítávám hrany do obarvených vrcholů. Dokažte, že pro každé K existuje rovinný graf, na jehož obarvení tomuto algoritmu nestačí K barev.

Výsledky

JménoTeoretické příkladyCodExBodůZápočťák
Alfonz2mis(10) funf(5)85100 Suffixový strom
Viktor Bahýľ00
Jiří Benešfunf(5) funb(5) 2mis(10) mdpx(10)70100 Scheme  OK Z
Jan Gocníkfunb(5) funf(5) 2mis(10)80100 Chat server s pexesem  OK Z
Miroslav Hutárfunf(5) funb(5) 2mis(10) mdpx(10)70100 Databázová knihovna
Kyrylo Karlovfunf(5) 2mis(10) rep3(10)75100 Účetnictví v květinářství  OK Z
Tomáš Krňák2mis(10) funf(5) funb(5) color(10)75105 Pythoní průzkumník  OK Z
Martin Kubešafunf(5) 2mis(10)015
Jakub Matěna2mis(10) funb(5)95110 Lineární rovnice  OK Z
Ondřej Měkotafunf(5) 2mis(10) mdpx(10)75100 AVL stromy  OK Z
Yury Nudgafunf(5)5055
Zdeněk Pavlátka2mis(10) funf(5) mdpx(10)75100 Trochu pokročilejší Malování  OK Z
Patrícia Schmidtová00
Jiří Sejkorafunf(5) 2mis(10)85100 Prázdný papír  OK Z
Václav Skála2020
Roman Sobkuliakfunf(5) 2mis(10)85100 Treap  OK Z
Jakub Suchánekfunb(5) 2mis(10) funf(5)5575
Jakub Štuller00
Jakub Tětek2mis(10) funf(5) mdpx(10) rep3(10) color(10)60105 Funnelsort  OK Z
Lucia Tódová00

Body z CodExu se přepočítávají jednou nočně. 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
5. 10. Chybějící číslo (aneb princeznin náhrdelník). Házení vajíček z mrakodrapu.
12. 10. Nejdelší úsek bez opakování. Okénková minima a amortizace. (Zítra slavíme mezinárodní den zpětné kompatibility. Anebo nad ním truchlíme.)
19. 10. Úsek se zadaným součtem. Bílý úsek. Největší prázdná podmatice.
26. 10. Podmatice s největším součtem: zadané velikosti, čtvercová, libovolná.
2. 11. Nejmenší chybějící číslo. Ještě trocha podmatic. Dvojrozměrné prefixové součty.
9. 11. Volby na mnoho způsobů: randomizace, různé druhy půlení intervalu. Na příště: lineární řešení?
16. 11. Lineární řešení voleb. Generování všech objektů s danou vlastností: posloupnosti nul a jedniček, právě jedna změna.
23. 11. Generování: právě k jedniček.
30. 11. Generování permutací: rekurze, lexikografický následník a náhodné permutace.
7. 12. O stromech, strážnících a mafiánech (neváženě, váženě, vypočítavě).
14. 12. Mafiáni v podzemí, asfaltéři na povrchu. Asfaltování obecných grafů.
21. 12. Bipartitní podgraf s alespoň polovinou hran. Mafiánský kápo.
4. 1. Ještě jednou kápo. Barvení rovinných grafů 6 a 5 barvami.
11. 1. Barvení rovinných grafů. Vyvážená a skorovyvážená orientace grafů.
Stránku spravuje Martin Mareš