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:

Vypracování domácích úkolů za alespoň 8 bodů. Domácí úkoly budou zadávány v průběhu semestru na cvičeních a rovněž se budou objevovat na těchto stránkách. Pokud úkol vyřešíte do 28 dnů od zadání, platí počet bodů uvedený v tabulce, později se redukuje na polovinu.
Vypracování zápočtového programu v Pascalu (případně po domluvě v jiném procedurálním programovacím jazyce). Program by měl splňovat následující:
- Téma: může být libovolné, má-li odpovídající obtížnost. Ideální bude, když s nějakým přijdete sami, nerozhodným nabízím poměrně rozsáhlý seznam témat (na skladě též zdrojový text v TeXu a pěkně vysázená verze v PDF), přiměřené pro letní semestr jsou úlohy obtížnosti 5 a vyšší, ostatní berte jako návnadu pro vaši fantazii). Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře, archiv Matematické Olympiády kategorie P, stránka Roberta Špalka.
- Odevzdání specifikace programu do 14. května. Tím mám na mysli krátký popis toho, co všechno by program měl umět. Vyhnete se tak tomu, že by váš zápočtový program odevzdaný den před koncem zkouškového období byl odmítnut jako příliš triviální nebo příliš podobný programu někoho z vašich kolegů.
- Nedílnou součástí zápočtového programu je dokumentace, a to jak uživatelská (vysvětující, jak se program ovládá), tak programátorská (ta popisuje, jak program uvnitř funguje; postrádá smysl popisovat každou funkci či proměnnou, zaměřte se spíš na celkový návrh programu a použité algoritmy, pokud jste je sami nevymysleli, nestyďte se za ně a uveďte odkazy na zdroje, z nichž jste čerpali).
- Specifikaci i dokumentaci odevzdávejte buďto v papírové podobě nebo chcete-li šetřit naše lesy, elektronicky v libovolném otevřeném formátu (tím se myslí formát, jehož struktura je všeobecně známa a na jehož prohlížení není potřeba žádný komerční software; speciálně tedy ne MS Word!), nejlépe jako čistý text, HTML, PostScript či PDF.
- Hotový program mi mužete předat buďto na cvičení nahraný na disketě či CD nebo jej poslat po Internetu, buďto e-mailem nebo (pokud je poněkud větších rozměrů, řekněme nad 0.5MB) uploadem do ftp://atrey.karlin.mff.cuni.cz/pub/priv/ (ale pak mi pošlete mail se jménem souboru). Pokud se zápočťák skládá z většího množství souborů, raději jej předtím zabalte ZIPem nebo TARem (RAR, prosím, ne).
- Zápočtový program musí mít přiměřeně ošetřené vstupy. Tím se myslí, že komunikuje-li s uživatelem, měl by počítat s tím, že uživatel je nešika a občas zadá špatný vstup a nenechat se tím zmást a bez zaváhání je odmítnout. Naopak, pokud programujete knihovnu funkcí, můžete předpokládat, že všechny vstupy jsou korektní.

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]

Datum	ID	Body	Příklady
21. 2.	lrev	1	Je 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)]
	lmrg	2	Napiš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)]
	loop	2	... 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.	elec	2	(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 10⁹. 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)]
	pmul	2	Napiš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(n²) / O(n)]
	cbra	1	Hříč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.	mtrp	2	Naprogramujte 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(n²), kde n je velikost řídké reprezentace] [+1 bod] za řešení v čase O(nlog n) (hint: použijte haldu nebo metodu Rozděl a panuj)*
	lsrt	1	Tř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(n²)]
	linl	1	Napiš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)]
	self	2	Další hříčka: Sestrojte program, který vypíše svůj vlastní zdrojový text.
14. 3.	mors	1	Napište program pro převod do Morseovy abecedy a zpět pomocí binárních stromů kódovaných v poli.
	bstr	2	Napiš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)]
	drtr	2	Napište funkci, která binární strom přehledně vypíše (textově, například takhle).
	walk	1	Vypiš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.	pinv	2	Počí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.
21. 3.	isec	2	Je 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.	tcov	2	Nalezně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)]
	tgua	2	Je 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)]
	huse	2	Housenka 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.	abtr	2	Naprogramujte 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á).
	qsrt	1	Naprogramujte QuickSort a dejte si pozor na případy, kdy si jako pivota vyberete minimum nebo maximum.
	medi	1	Naprogramujte výběr k-tého nejmenšího prvku modifikovaným Quicksortem.
11. 4.	ssrt	2	Jakpak byste vyřešili, když by vám někdo zadal řetězce x₁, ..., x_n a chtěl je lexikograficky setřídit v čase lineárním v součtu jejich délek? Hint: Použijte písmenkový strom.
	uniq	2	Dostali 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.
	hsrt	2	Naprogramujte HeapSort (třídění pomocí haldy). [O(n*log n)]
	pali	2	Napiš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 :)
	amor	2	Dokaž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.	umax	2	Je 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]
	ugiv	2	Opět dána posloupnost celých čísel. Nalezněte úsek se zadaným součtem. [O(n) průměrně]
	ubal	2	Zase 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.	grtr	1	Je 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)]
	tsrt	2	Napiš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)]
	spth	1	Orientovaný graf. Wanted: nejkratší cesta mezi dvěma vrcholy. [O(m+n)]
2. 5.	Hic erat Maiales et nullum exercitium.
9. 5.	arti	2	Naprogramujte 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í.
	pcnt	2	Je 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í.
	sssp	1	Je 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(n²)] [+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 ≥ n^1+ε. Hint: k-regulární halda pro vhodné k.
	issp	1	Totéž v grafu ohodnoceném přirozenými čísly 1...5. [O(m+n)] Hint: Nevymýšlejte nic složitého :)
	mstr	1	Neorientovaný graf s hranami ohodnocenými celými čísly. Wanted: minimální kostra. [O(n²)] [+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.
	imst	2	Totéž v grafu ohodnoceném přirozenými čísly 1...5. [O(m+n)]
16. 5.	tsp1	1	Problé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.
	tsp2	3	Řešení problému obchodního cestujícího v čase O(2ⁿ). Hint: Dynamické programování.
	tapx	2	Napiš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.
	ktah	3	Je 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.	foun	2	Problé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)]
	book	2	Problém knihovníkův: máme N knih o šířkách t_i a výškách h_i 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)]
	edst	2	Problé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)]
	iseq	2	Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost. [O(n²] [+1 bod] ... v čase O(n*log n).
	lcsq	2	Naprogramujte funkci, která pro dvě posloupnosti nalezne jejich nejdelší společnou vybranou podposloupnost. [O(poly)]