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
| 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. | |
| 6. 10. | 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é? |
| 12. 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. |
| 2. 11. | 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. | 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-tinu všech hlasů. Opět chceme lineární čas, spotřeba paměti smí záviset pouze na k. |
| 11. 1. | color | 10 | Uvaž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. |
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ů. |