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
| Datum | Kód | Body | Zadání |
|---|---|---|---|
| 2. 10. | funf | 5 | Co dělá funkce f() z letáčku? |
| funb | 5 | Co dělá funkce bc() z letáčku? | |
| xorn | 8 | Jak spočítat 1 XOR 2 XOR 3 XOR … XOR N v čase rychlejším než Θ(N)? | |
| 2mis | 15 | 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é? | |
| 14. 11. | volby | 15 | Mě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ů. |