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

Ve školním roce 2014/2015 vedeme s Jirkou Setničkou 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ý č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. 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í
2. 10. funf5Co dělá funkce f() z letáčku?
funb5Co dělá funkce bc() z letáčku?
xorn8Jak spočítat 1 XOR 2 XOR 3 XOR … XOR N v čase rychlejším než Θ(N)?
2mis15Princezně 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é?
14. 11. volby15Mějme M kandidátů, N voličů a přirozené číslo K≥2. Každý volič hlasuje pro jednoho kandidáta. Chceme najít všechny kandidáty, pro které hlasuje víc než N/K voličů. Víme, že N je větší než množství dostupné paměti a rozsah čísel kandidátů je ještě větší.

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
2. 10. Pár příkladů na úvod: Házení vajíček z mrakodrapu. Chybějící číslo (aneb princeznin náhrdelník). Číslo s lichým počtem výskytů. Robin Hood a euklidovská lukostřelba. Robin Hood a předvolební billboardy.
9. 10. Úlohy o posloupnostech: dvojice s daným součtem, úsek s daným součtem, úsek s maximálním součtem. Také jejich verze pro monotónní nebo nezápornou posloupnost.
16. 10. Nejdelší vyvážený úsek. Nejdelší bílý úsek v posloupnosti RGB a souvislosti s přihrádkovým tříděním.
23. 10. Největší prázdná podmatice: zadané velikosti, čtvercová, libovolná.
30. 10. Hledání v setříděné matici a umění dolních odhadů.
6. 11. Cvičení se nekoná, jsouc imatrikulace. Gaudeamus igitur!
13. 11. Volby na mnoho způsobů: bity, randomizace a konečně i lineární řešení. Propojování drátů, adaptivní i neadaptivní algoritmus.
20. 11. Generování všech objektů s danou vlastností: posloupnosti nul a jedniček, právě k jedniček, právě jedna změna; permutace. Náhodné permutace.
27. 11. O stromech, strážnících a mafiánech (neváženě, váženě, vypočítavě).
4. 12. Mafiáni a asfaltéři.
14. 12. Asfaltéři, tentokrát v obecných grafech. Vyvážená orientace grafů.
18. 12. Skorovyvážená orientace. Mafiánský kápo. Barvení rovinných grafů.
Stránku spravuje Martin Mareš