Cvičení z Programování II

Ve školním roce 2004/2005 vedu cvičení z předmětu Programování II [NPRG031]. Cvičení se koná každou středu od 12:20 v posluchárně S6.

Podmínky k získání zápočtu jsou:

Domácí úkoly

DatumIDBodyPříklady
23. 2. lmir1Je dán jednosměrný spojový seznam. Napište funkci, která prvky seznamu přeskládá do opačného pořadí. (Prvky přepojujte, nic nekopírujte.)
dyna1Implementujte "nafukovací pole", tj. dynamicky alokované pole, které bude na počátku prázdné a postupně do něj budete přidávat zadané prvky, přičemž kdykoliv dojde v poli místo, alokujete nové pole dvojnásobné velikosti a prvky ze starého pole do něj zkopírujete. (Všimněte si, že přidání N prvků stojí čas O(N).)
2. 3. ldel1Napište funkci, které ze zadaného jednosměrného spojového seznamu odstraní všechny prvky se zadanou hodnotou.
lspl1... která zadaný jednosměrný spojový seznam rozdělí na seznam obsahující prvky se sudými a druhý s lichými hodnotami. Prvky nekopírujte, jen přepojujte.
loop2... která o zadaném jednosměrném spojovém seznamu určí, zda je či není zacyklený (tj. poslední prvek má jako další nikoliv nil, nýbrž některý z předchozích prvků). Žádá se lineární čas a konstantní pomocná paměť (to speciálně znamená, že zadaný seznam nesmíte nijak modifikovat).
pola1Naprogramujte sčítání řídkých polynomů (řídký polynom je seznam dvojic (koeficient, exponent) setříděný vzestupně podle exponentu; žádný z koeficientů není nulový).
polm2Naprogramujte násobení řídkých polynomů.
swap2Pole P se skládá ze dvou různě dlouhých úseků. Napište proceduru, která tyto úseky prohodí a zvládne to v lineárním čase a konstantní pomocné paměti.
iplm4Pole P se skládá ze dvou setřiděných úseků. V lineárním čase tyto úseky slijte do jedné setříděné posloupnosti, aniž byste použili větší než konstantní pomocnou paměť. Není to úplně jednoduché, ale pan Google vám muže pomoci.
9. 3. lmrg2Napište funkci, která setřídí jednosměrný spojový seznam pomocí MergeSortu.
lins2Napište funkci, která setřídí jednosměrný spojový seznam některým z triviálních třídících algoritmů (InsertSort, SelectSort, BubbleSort).
16. 3. tcut2Stvořte funkci pro ořezávání binárního vyhledávacího stromu intervalem. Tj. je zadán BVS a interval hodnot <a,b> a je třeba odstranit ze stromu všechny hodnoty, které leží mimo interval.
twlk1Napište proceduru pro nerekursivní projití BVS pomocí hledání následníka prvku.
bbtr3Naprogramujte funkci pro vložení prvku do BB-1/2-stromu. Takové stromy fungují tak, že si v každém vrcholu udržují velikost podstromu a kontrolují, že velikost levého a pravého podstromu se liší nejvýše 2-krát. Při insertu stačí updatovat velikosti podstromů, zkontrolovat, jestli někde není podmínka porušena a pokud ano, najít nejvyšší takové místo, celý podstrom rozebrat a postavit optimálně vyvážený. Ačkoliv jedna operace může být pomalá, v průměru trvají O(log n). Přesněji: Pokud každý insert přispěje časem O(log n), zaplatí se tím všechna vyvažování.
23. 3. avli3Naprogramujte funkci pro vložení prvku do AVL-stromu. Hezký popis toho, jak s AVL-stromy zacházet, najdete v Programátorské kuchařce KSP.
iset2Vymyslete a naprogramujte algoritmus, který v zadaném zakořeněneném stromu (ne nutně binárním) nalezne největší možnou nezávislou množinu (tj. množinu vrcholů takovou, že mezi žádnými dvěma nevede hrana).
30. 3. dice2Napište program, který bude pomocí hodů k-stěnnou kostkou (kterou považujeme za zdroj rovnoměrně rozložených nezávislých náhodných čísel) simulovat hody kostkou l-stěnnou.
rsel3Na vstupu je libovolně dlouhá posloupnost řádků (dopředu nevíte, jak dlouhá) a číslo k. Váš program má z této posloupnosti vybrat náhodnou k-tici řádků tak, aby všechny k-tice měly stejnou pravděpodobnost. Číslo k je dostatečně malé, takže vybrané řádky se určitě do paměti vejdou, vstupní posloupnost ovšem nemusí.
6. 4. xpos1Naprogramujte funkci, která z orientovaného grafu zadaného pomocí seznamů sousedů vrcholů (ve dvou polích: pole hran setříděné podle zdrojového vrcholu a pole vrcholů ukazující na první hranu vedoucí z daného vrcholu) vytvoří graf obsahující přesně opačné hrany.
[+1 bod] ... použijete-li mimo vstupní a výstupní dvojice polí jenom konstantně mnoho pomocné paměti.
comp1Naprogramujte funkci, která rozloží neorientovaný graf na komponenty souvislosti.
13. 4. tsrt2Napište program pro topologické třídění orientovaného grafu, tj. program, který k zadanému grafu nalezne topologické pořadí vrcholů ((x,y) je hrana => x<y) nebo odpoví, že graf není acyklický.
imst2Napište program, který v zadaném neorientovaném grafu s hranami ohodnocenými přirozenými čísly 1...5 nalezne minimální kostru.
20. 4. cycr2Je dán neorientovaný graf. Nelezněte v lineárním čase takovou jeho orientaci, aby se vstupní a výstupní stupeň každého vrcholu lišily nejvýše o 1.
eulr2Je dán neorientovaný graf. Nalezněte v lineárním čase eulerovský tah v tomto grafu, případně vypište, že neexistuje.
nump2Je dán acyklický orientovaný graf a dvojice vrcholů. Spočtěte v lineárním čase, kolik mezi těmito vrcholy vede cest.
27. 4. 6col2Je dán neorientovaný rovinný graf. Nalezněte v lineárním čase jeho obarvení šesti barvami.
[+0.5 bodu] obarvení pěti barvami v kvadratickém čase,
[+1 bod] obarvení pěti barvami v lineárním čase.
peri2Je dána permutace. Spočtěte, kolik má inverzí, tj. dvojic (i,j) takových, že i<j, ale xi>xj. Časová složitost: lepší než kvadratická.
pero2Opět je dána permutace. Zjistěte v lineárním čase, zda je sudá nebo lichá.
perr2Ještě jednou permutace. Najděte nejmenší takové k> 0, že k-té složení permutace se sebou samou dá identitu.
perx2Pro změnu permutace :) Napište funkce, které budou umět k permutaci najít její pořadové číslo v lexikografickém uspořádání, a naopak k číslu najít permutaci.
[+1 bod] Vyberte si jiné uspořádání, v němž zvládnete převod v lineárním čase.
4. 5. 3lou2Problém tří loupežníků: tři loupežníci společně naloupili n cenností o známých cenách (to jsou celá čísla v rozsahu 1 až 1000) a chtějí se o ně šábnout. Napište program, který zjistí, zda je možné lup rozdělit na 3 stejně cenné části (ceny jsou aditivní a předměty nelze dělit) a pokud ano, tak takové rozdělení vypíše.
11. 5. Cvičení se nekonalo (Jarní Škola Kombinatoriky)
18. 5. foun2Problém telefonní číselnice: je dána N-znaková abeceda, četnosti jednotlivých znaků abecedy a telefon s K tlačítky. Napište program, který najde optimální rozmístění abecedy na tlačítka, tj. takové, které zachová pořadí znaků v abecedě, a přitom bude vyžadovat nejmenší možný počet zmáčknutí vzhledem k zadaným četnostem (první znak na tlačítku potřebuje jeden stisk, druhý dva atd.). Viz též tabulka četností písmen v češtině.
book2Problém knihovníkův: máme N knih o šířkách ti a výškách hi a místnost vysokou H (všechno můžeme považovat za rozumně malé celé počty milimetrů). Knihovna se skládá z P stejně širokých polic umístěných nad sebou, každá police má tloušťku 10mm. Vaším úkolem je nalézt rozmístění knih do co nejužší knihovny tak, aby se knihovna vešla do místnosti a knihy byly uspořádány abecedně (tj. v zadaném pořadí).
edst2Problém tiskařského šotka: napište funkci, která spočte editační vzdálenost zadaných dvou slov, což je minimální počet editačních operací (vložení znaku, smazání znaku, přepsání znaku jiným), jimiž lze první slovo přetvořit na druhé.
iseq2Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost.
[+1 bod] ... v čase O(n*log n).
25. 5. Žádné domácí úkoly
Stránku spravuje Martin Mareš