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

Ve letním semestru 2021/2022 vedu speciální cvičení z předmětu Programování 2 [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í koná ve středu od 15:40 v N3.

Podmínky na získání zápočtu najdete v pravidlech hry.

Přihlašte se prosím do ReCodExu a Poštovní sovy.

Pokud chcete cokoliv konzultovat, ozvěte se mi na adresu mares+p2x@kam.mff.cuni.cz.

Co jsme dělali

datum	co se cvičilo
16. 2.	Dynamické programování poprvé – úlohy o knihovnách: plnění zadané knihovny, nejnižší a nejužší knihovna.
23. 2.	Dynamické programování podruhé: nejdelší rostoucí podposloupnost, nejdelší společná podposloupnost, editační vzdálenost.
2. 3.	Optimální stromy. Řezání trámu.
9. 3.	Počítání trojúhelníků a čtyřcyklů v grafech: obecně, s omezenými stupni, v rovinných grafech. Existence čtyřcyklu.
16. 3.	Dokončení z minulých dvou cvičení.
23. 3.	Středeční chvilka geometrie: Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny. Prázdný trojúhelník. Hledání obdélníka.
30. 3.	Geometrie podruhé: Obsah mnohoúhelníka a počet mřížových bodů v něm. Rotování kamínků na šachovnici.
6. 4.	Dokončení z minulého cvičení.
13. 4.	Povídání o domácích úkolech. A ještě kamínky.
20. 4.	Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. Problém malíře kvadrantisty (a jeho komprimovaná verze). RLE komprese a hledání největší souvislé oblasti.
27. 4.	Pokračování z minula. Komprese LZ77 a histogram četností znaků.
4. 5.	Orákula: zdroj v grafu, A[i,j]=i+j, kráva za plotem, hádání čísel se lží.
11. 5.	Rektorský sportovní den. Necvičíme, protože cvičíme.
18. 5.	Dvakrát seznamy: hledání cyklu, hledání srůstu. Volby. Trampoty jeřábníkovy. Dělostřelci v řadě a v grafu.