Cvičení z Programování II pro pokročilé
Ve letním semestru 2013/2014 vedeme s Jirkou Setničkou speciální cvičení z předmětu Programování II [NPRG031] 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. Tematicky bude navazovat na Programování I pro pokročilé z minulého semestru, ale jeho absolvování určitě nebude nutné pro účast na tomto cvičení.
Cvičení se koná každé pondělí od 15:40 v S4, kdo chcete chodit, přihlašte se 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í |
|---|---|---|---|
| 17. 2. | funrb | 7 | Co a proč dělá funkce rb() z letáčku? |
| 18. 2. | funm | 10 | Co a proč dělá funkce main() z letáčku? |
| 24. 2. | poly | 20 | Pro daný polynom P vymyslete datovou strukturu, která si cosi předpočítá pro posloupnost x1, … xn a pak bude umět v konstantním čase vyhodnocovat výrazy S(i,j) = Σk=0…j-i-1 P(k)*xi+k. Nápověda: zobecněte prefixové součty. |
| 31. 3. | pish | 10 | Vymyslete piškvorkovou datovou strukturu s lepší složitostí než Θ(log n) na operaci. |
| 19. 5. | rgb | 15 | Mějme posloupnost červených, zelených a modrých prvků. Najděte v ní nejdelší bílý úsek, tedy takový, v němž je stejně prvků každé barvy. Požadován lineární čas. Další body za verzi pro větší (ale pevný) počet barev. |
| 1. 9. | ksp | 0 | Doplňkové teoretické úlohy z KSP. Jen na požádání. |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 17. 2. | Okénková maxima v 1D i 2D. Dynamické programování poprvé: rozklad textu na slova. |
| 24. 2. | DP podruhé: optimalizování klávesnice mobilu, knihovna na mnoho způsobů. |
| 3. 3. | Optimální vyhledávací stromy. Luštění Vigenèrovy šifry. Řezání trámu. |
| 10. 3. | Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. Problém malíře kvadrantisty. RLE komprese a hledání největší souvislé oblasti. |
| 17. 3. | RLE a Union-Find. Body v rovině a jejich rozklad na dvě středově symetrické množiny. |
| 24. 3. | Věže na šachovnici a letmá zmínka o dámách. Piškvorková datová struktura. |
| 31. 3. | Piškvorky podruhé. Rozklad rovinných grafů na 5 lesů a jejich barvení 5 barvami. |
| 7. 4. | Jehla rozlámaná v seně. Buridan a kavárny (MO 63-3-1). |
| 14. 4. | Hledání cest v ohodnocených stromech: maximální délka, zadaná délka. |
| 21. 4. | Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace. |
| 28. 4. | ±1 + ±2 + … ±N = X. Make money fast aneb jak obehrát směnárnu. Pásové dopravníky. |
| 5. 5. | Slovní žebříky a okénkové hešování. Mřížové body v mnohoúhelnících a Pickova formule. |
| 12. 5. | Hanojské věže na mnoho způsobů. |
| 19. 5. | Kráva za plotem. Hledání pravidelného k-úhelníka mezi body na kružnici. Nejdelší bílá podposloupnost. |