Cvičení z Programování II

Ve školním roce 2005/2006 vedu cvičení z předmětu Programování II [PRG031]. Cvičení se koná každé úterý od 17:20 v posluchárně T6, konsultace obvykle těsně po cvičení, nebo po domluvě kdykoliv jindy.

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

Domácí úkoly

[V hranatých závorkách je u některých úkolů uvedena požadovaná časová/paměťová složitost; některé úlohy jdou samozřejmě vyřešit i efektivněji]

DatumIDBodyPříklady
21. 2. lrev1Je 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.) [O(N)/O(1)]
lmrg2Napište funkci pro spojení dvou setříděných jednosměrných seznamů do jednoho. Prvky nekopírujte, pouze přepojujte. [O(N)/O(1)]
[+1 bod] ... a pomocí ní třídění seznamů mergesortem [O(N*log N)/O(log N)]
loop2... funkci, 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).
28. 2. elec2(Jak pomoci Číňanům k demokracii...) Ve volbách hlasovalo N voličů, každý odevzdal jeden hlas pro jednoho z kandidátů očíslovaných od 1 do 109. Vyhraje ten kandidát, pro nějž hlasovala více než polovina voličů. Napište program, který co nejefektivněji tohoto kandidáta najde. Vstup máte připravený v poli (A[i]=j značí, že i-tý volič hlasoval pro j-tého kandidáta), toto pole smíte pouze číst. [čas O(n) / paměť O(1)]
pmul2Napište násobení polynomů v řídké reprezentaci (spojový seznam dvojic (koef, exponent) uspořádaný vzestupně podle exponentu; členy s nulovými koef. chybí; sčítání jsme dělali na cvičení). [O(n2) / O(n)]
cbra1Hříčka: Vymyslete program, který vypíše, zda kompilátor, jímž byl zkompilován, podporuje vnořování komentářů ({ { komentar } take } uz ne) nebo nikoliv ({ komentar { take } uz ne } uz vubec ne).
7. 3. mtrp2Naprogramujte funkci pro transpozici matice v řídké reprezentaci (matice je seznam nenulových řádků, každý řádek ukazuje na seznam svých nenulových prvků). [O(n2), kde n je velikost řídké reprezentace]
[+1 bod] za řešení v čase O(n*log n) (hint: použijte haldu nebo metodu Rozděl a panuj)
lsrt1Třiďte jednosměrný seznam pomocí některého z primitivních třídících algoritmů (insert-sort, bubble-sort, select-sort...). Prvky nekopírujte, pouze přepojujte. [O(n2)]
linl1Napište funkci pro vložení jednoho obousměrného cyklického seznamu za určený prvek druhého seznamu. Pozor na prázdné seznamy. [O(1)]
self2Další hříčka: Sestrojte program, který vypíše svůj vlastní zdrojový text.
14. 3. mors1Napište program pro převod do Morseovy abecedy a zpět pomocí binárních stromů kódovaných v poli.
bstr2Napište funkce pro vkládání a odebírání prvku v binárním vyhledávacím stromu (bez vyvažování). [O(hloubka)]
drtr2Napište funkci, která binární strom přehledně vypíše (textově, například takhle).
walk1Vypište binární vyhledávací strom nerekurzivně: nalezněte minimum a pak vždy vyhledejte následníka. Předpokládejte, že každý prvek stromu si pamatuje svého otce. [O(n)]
21. 3. pinv2Počítejte inverze v zadané permutaci. Inverze je dvojice indexů (i,j) taková, že i<j a zároveň p(i)>p(j). [O(n log n)] Hint: zkuste využít binární vyhledávací stromy, nejlépe i s trikem popsaným na cvičení, kterým lze celý strom zakódovat do jednoho pole.
isec2Je zadána množina intervalů na celočíselné přímce. Spočítejte, kolik je dvojic protínajících se intervalů. [O(n log n), ale pozor, samotných dvojic může být víc] Hint: Opět vyhledávací stromy.
28. 3. tcov2Nalezněte minimální vrcholové pokrytí zadaného stromu (to je nejmenší možná množina vrcholů taková, že každá hrana má alespoň jeden ze svých konců v této množině). [O(n)]
tgua2Je dán strom s ohodnocením vrcholů (města a počty obyvatel). Navrhněte, do kterých měst postavit hlídky tak, aby v těchto městech bylo co nejvíce obyvatel, a přitom aby nikdy nebyly více než tři hlídky vedle sebe (formálně řečeno, aby podgraf indukovaný vrcholy s hlídkami neobsahoval komponenty o více než třech vrcholech). [O(n)]
huse2Housenka se skládá z páteře (cesta) a nožiček (ke každému vrcholu páteře mohou být navíc připojeny 0-2 listy). Nalezněte v zadaném stromu housenku tvořenou co největším počtem vrcholů. [O(n)]
4. 4. abtr2Naprogramujte základní operace s (2,3)-stromy: Find, Insert, Delete. [O(log n)]
[+1 bod] a Merge (sloučení dvou stromů do jednoho)
[+1 bod] a Split (rozdělení stromu na dva obsahující hodnoty větší, resp. menší než zadaná).
qsrt1Naprogramujte QuickSort a dejte si pozor na případy, kdy si jako pivota vyberete minimum nebo maximum.
medi1Naprogramujte výběr k-tého nejmenšího prvku modifikovaným Quicksortem.
11. 4. ssrt2Jakpak byste vyřešili, když by vám někdo zadal řetězce x1, ..., xn a chtěl je lexikograficky setřídit v čase lineárním v součtu jejich délek? Hint: Použijte písmenkový strom.
uniq2Dostali jste posloupnost N přirozených čísel a máte v průměrně lineárním čase rozhodnout, zda se v ní nějaké číslo vyskytuje vícekrát.
hsrt2Naprogramujte HeapSort (třídění pomocí haldy). [O(n*log n)]
pali2Napište program, který je palindromický (tj. čte se stejně popředu jako pozpátku); nebo program, který vypíše, zda byl zadán popředu nebo pozpátku :)
amor2Dokažte, že hledání následníka v binárním vyhledávacím stromu (viz úloha walk) má amortizovanou časovou složitost O(1), pokud inicializaci přisoudíme amortizovanou složitost O(hloubka stromu). Hint: Vymyslete vhodný potenciál nebo zkuste upravit důkaz lineární časové složitosti úlohy walk, aby fungoval i pro částečné projití stromu.
18. 4. umax2Je dána posloupnost celých čísel. Nalezněte úsek (tj. souvislou podposloupnost) s maximálním součtem. [O(n); pokud program není evidentní, rád bych i důkaz správnosti]
ugiv2Opět dána posloupnost celých čísel. Nalezněte úsek se zadaným součtem. [O(n) průměrně]
ubal2Zase jednou posloupnost celých čísel. Nalezněte co nejdelší úsek, ve kterém je stejně kladných jako záporných čísel. [O(n)]
25. 4. grtr1Je dán orientovaný graf seznamem sousedů vrcholů uloženým pomocí dvou polí. Napište funkci, která vygeneruje reprezentaci grafu lišícího se od zadaného otočením orientace hran. [O(m+n)]
tsrt2Napište proceduru, která topologicky uspořádá zadaný orientovaný graf, případně odpoví, že to není možné, neb v grafu jsou cykly. [O(m+n)]
spth1Orientovaný graf. Wanted: nejkratší cesta mezi dvěma vrcholy. [O(m+n)]
2. 5. Hic erat Maiales et nullum exercitium.
9. 5. arti2Naprogramujte proceduru, která v souvislém neorientovaném grafu najde všechny artikulace, což jsou vrcholy takové, že jejím odebráním přestane graf být souvislý. [O(m+n)]
Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období.
pcnt2Je zadán acyklický orientovaný graf a v něm dva význačné vrcholy. Spočítejte, kolik mezi těmito vrcholy existuje orientovaných cest. [O(m+n)] Hint: topologické třídění.
sssp1Je zadán orientovaný graf s hranami ohodnocenými nezápornými čísly a dva vrcholy x,y. Nalezněte a vypište nejkratší cestu z x do y. [O(n2)]
[+1 bod] za řešení v čase O((m+n)*log n). Hint: halda.
[+2 body] za řešení v čase O(m+n) pro grafy s m ≥ n1+ε. Hint: k-regulární halda pro vhodné k.
issp1Totéž v grafu ohodnoceném přirozenými čísly 1...5. [O(m+n)] Hint: Nevymýšlejte nic složitého :)
mstr1Neorientovaný graf s hranami ohodnocenými celými čísly. Wanted: minimální kostra. [O(n2)]
[+1 bod] řešení v čase O((m+n)*log n). Hint: pokud používáte hladový algoritmus, zkuste vylepšit udržování komponent souvislosti; pokud nějaký jiný, zkuste pro hledání minim použít haldu.
imst2Totéž v grafu ohodnoceném přirozenými čísly 1...5. [O(m+n)]
16. 5. tsp11Problém obchodního cestujícího: je dán neorientovaný graf s hranami ohodnocenými přirozenými čísly. Nalezněte nejkratší uzavřený tah procházející všemi vrcholy. Polynomiálně ho zatím nikdo nalézt neumí, zkuste napsat řešení backtrackingem.
tsp23Řešení problému obchodního cestujícího v čase O(2n). Hint: Dynamické programování.
tapx2Napište program, který v polynomiálním čase nalezne 2-aproximaci problému obchodního cestujícího, tj. uzavřený tah, který je maximálně dvakrát delší než ten nejkratší. Hint: Minimální kostra.
ktah3Je zadán neorientovaný graf. Nalezněte jeho nakreslení nejmenším možným počtem tahů (mohou být uzavřené i otevřené). [O(m+n)]
23. 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ě. [O(NK)]
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í). [O(poly)]
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é. [O(MN)]
iseq2Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost. [O(n2]
[+1 bod] ... v čase O(n*log n).
lcsq2Naprogramujte funkci, která pro dvě posloupnosti nalezne jejich nejdelší společnou vybranou podposloupnost. [O(poly)]
Stránku spravuje Martin Mareš