• Home|
• Kontakty

Jirka Setnička

„… budete obviněn z mnoha trestných činů zahrnujících několikanásobnou vraždu tupým předmětem, konkrétně drakem“ _Zeměplocha

Cvičení z předmětu Algoritmy a datové struktury I (NTIN060) k přednáška Ondřeje Čepka (stránky přednášky).

Kontakt:

Pro účely cvičení mě můžete kontaktovat na emailu setnicka+ads@kam.mff.cuni.cz (usnadní mi to třídění pošty a zrychlí čas na odpověď), nebo můžete použít jinou metodu ze stránky s kontakty. Nebo mě někdy prostě odchyťte na chodbě :-)

Kdy a kde:

Cvičení se konají každé pondělí od 9:00 v učebně S10.

Zápočet:

V průběhu semestru se budou objevovat (převážně teoretické) domácí úkoly, za které bude potřeba získat alespoň 100 bodů. Úloh bude vypsáno alespoň za 150 bodů, možná i více. Další body navíc půjde získat i za hezký zápočtový program nebo aktivitu během cvik.

Druhou podmínkou je vypracování zápočtového programu, který bude nějak implementovat či používat některou z technik odpřednesených na přednášce. Téma se mnou nejdřív konzultujte, abyste nedělali něco moc těžkého, nebo naopak něco, co nepůjde uznat za zápočet.

Detaily k zápočťákům

Domlouvali jsme na cviku 27. března, kdyžtak se ptejte. Níže jsou shrnuty hlavní body:

• Hlavním účelem zápočťáku je zkusit si implementovat prakticky (včetně odladění) nějakou datovou strukturu nebo algoritmus z látky ADS I – klidně to může být jednoduchá knihovna na třídící algoritmy, algoritmus na hledání nejkratších cest, některý z rozumně těžkých domácích úkolů ze cvik, … (ale pokud chcete, klidně jen nějaký algoritmus/datovou strukturu použijte v rámci většího programu, třeba hry nebo editoru MP3 souborů.
• Až si vyberete téma zápočťáku, tak mi napište email s tématem a jazykem, abych včas podchytil věci zbytečně složité, nebo naopak příliš jednoduché na zápočet.
• Můžete psát v jakémkoliv rozumném imperativním jazyce jazyce (C, C++, C#, Java, Python, Pascal, Perl, Go, …), jiné jazyky konzultujte.
• K zápočťáku je potřeba dokumentace:
  • Programátorská dokumentace popisující implementaci (jak algoritmus interně funguje, jaké ve stručnosti používá funkční bloky, ...)
  • Uživatelská dokumentace popisující použití – u knihoven jejich rozhraní (API) a ukázky použití, u samostatných programů popis jejich vstupního a výstupního formátu, nebo třeba popis ovládání.
  Celkově by dokumentace neměla přesáhnout více jak jednu A4 oboustranně (buďte spíše struční a výstižní).
• Termín odevzdání ideálně alespoň týden předtím, než budete potřebovat zápočet. Ale nejlépe do konce zkouškového (spíše doporučení, než deadline, přijímám zápočťáky až do konce akademického roku).

Získané body:

Jméno	Úkoly	Bonusy	Bodů	Zápočťák	Zápočet
Ando	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(4), bludiste(10), ruzneCesty(10), kamion(10)		116	Třídící algoritmy	OK
ASRock	vazeni(8), inverze(10), treeDiam(5)		23	--	NE
Atsuko Kagari	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), druhyNejmensi(10)		100	Mergesort knihovna	OK
Budgie	posloupnost(5), soucetK(5), odmocnina(7), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), ruzneCesty(7), medianPos(10), presmycky(5), anketa(5)	Hezký zápočťák: 5	102	AVL strom	OK
Diana Cavendish	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8)		102	Heapsort knihovna	OK
drozdo	posloupnost(10), soucetK(10), odmocnina(7), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), kamion(10), ruzneCesty(10), druhyNejmensi(10)		104	Knihovna nejkratších cest	OK
Falešný Martin Kubeša	posloupnost(10), soucetK(10), odmocnina(7), vazeni(8), mergesort(10), sroubky(12), median(5), druhyNejmensi(10), anketa(5), kamion(5), odtrhavani(5), ruzneCesty(5), legie(4)	Hezký zápočťák: 5	101	Dijkstra	OK
GOG	posloupnost(10), soucetK(10), podmatice(10), vazeni(8), mergesort(10), sroubky(9), odtrhavani(10), cyklus(5), legie(8), kamion(10)	Hezký zápočťák: 10	100	Bludiště	OK
Honza	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10)		102	Červeno-černé stromy	OK
Idefix	posloupnost(10), soucetK(10), odmocnina(7), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), kamion(10), ruzneCesty(10), median(5)	Aktivita na cviku: 6 (3+3)	103	Dijsktra	OK
Jakub Matěna	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10), ruzneCesty(10)		102	Dijsktrův algoritmus	OK
Kartoffel	soucetK(10), podmatice(10), vazeni(8), odtrhavani(10), cyklus(5), legie(8), bludiste(8), ruzneCesty(10), kamion(10)		79	--	NE
krokodyl	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(5), mergesort(10), sroubky(11), odtrhavani(10), cyklus(5), bludiste(10), ruzneCesty(10), druhyNejmensi(10)		108	Editační vzdálenost	OK
Kyrylo	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(8), ruzneCesty(10)		108	Podmatice	OK
Martin Kubeša	posloupnost(10), soucetK(10), odmocnina(7), sroubky(12), odtrhavani(10), cyklus(5), median(2), kamion(10), ruzneCesty(10), treeDiam(5), medianPos(10), presmycky(10)		101	Funnel sort	OK
Michal Nemčok	posloupnost(7), soucetK(4), odmocnina(7), vazeni(8)		26	--	NE
OR	posloupnost(10), soucetK(10), odmocnina(7), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), kamion(10), druhyNejmensi(10)	Aktivita na cviku: 3 (3) Hezký zápočťák: 10	113	Knihovna pro AVL stromy	OK
Oskar	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8), ruzneCesty(10)		110	Splay stromy	OK
Pán Historie	posloupnost(10), soucetK(10), odmocnina(7), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8), kamion(10), ruzneCesty(10)		110	(a,b)-stromy	OK
Pán Mraků	posloupnost(10), soucetK(10), odmocnina(7), vazeni(5), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8), ruzneCesty(10), kamion(10), treeDiam(5)	Hezký zápočťák: 10	112	B-stromy	OK
rcn	posloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10)		102	Nejkratší cesty	OK
SSS	posloupnost(5), odmocnina(3), soucetK(10), vazeni(8), mergesort(10), sroubky(10), odtrhavani(10), cyklus(2), kamion(10), legie(5), presmycky(10), medianPos(10), anketa(5)	Hezký zápočťák: 5	103	Maticová knihovna	OK
Stepo	posloupnost(5), soucetK(10), odmocnina(7), podmatice(10), vazeni(5), mergesort(10), odtrhavani(10), cyklus(5)		62	--	NE
weiXiao	posloupnost(10), vazeni(10)		20	--	NE

Studijní materiály

• (ADS)Skripta k ADS od Martina Mareše – Skvělý studijní materiál pokrývající dobře skoro celou látku
• (KSP)Programátorské kuchařky Korespondenčního semináře z programování – dobře pokrytá některá témata, mělo by být pochopitelné i středoškoláky. Je dobré k pochopení probírané látky, ale nejsou zde příliš formální důkazy.

Na některé materiály se budu odkazovat u jednotlivých cvičení – ADS nebo KSP v závorce značí, kam materiály odkazují.

Rozvrh cvičení (aneb co jsme dělali a co se chystá):

20.2.	Úvodní cvičení Pár problémů na rozcvičení: Úvodní formality k zápočtům a úkolům Házení vajíček z mrakodrapu – Vajíčko se rozbije při pádu z nějaké výšky (nikdy ne níže), zjistětě tuto výšku na co nejméně pokusů pro 1 vajíčko, 2 vajíčka, $k$ vajíček … CD z koncertu – Na koncertu jsme nahráli posloupnost různě dlouhých písniček, chceme z nich teď vybrat souvislou část o délce právě $k$ minut (aby se nám vešla na CDčko) – postupně jsme dosáhli $\O(N^3)$, $\O(N^2)$ a $\O(N)$ a dokázali, že lépe už to nejde. Vojáci v řadě – $N-1$ vojáků očíslovaných čísly $1\dots N$ (jeden tedy chybí) stojí uspořádáni v řadě. Na co nejméně podívání se určete, voják jakého čísla dezertoval – umíme v $\O(\log N)$. Úkoly: posloupnost Studijní materiály: Základní algoritmy(KSP), Pár příkladů na úvod(ADS)
27.2.	Záskok: Verča Slívová Pokračování v úvodu: Počítání s časovou složitostí Rekurze Studijní materiály: Časová a paměťová složitost(ADS), Složitost(KSP)
6.3.	Matice, RAM: Příklad s maticí: Chceme si v lese postavit co největší obdélníkový dům, ale nechceme přitom pokácet ani jeden strom. Hledáme tedy v matici s 1 (stromy) a 0 (prázdné místo) největší nulovou podmatici. Řešení v $\O(R^3 S^3)$ zkoušením všech možných podmatic a jejich kontrolou Řešení v $\O(R^2 S^2)$ zkoušením všech možných podmatic, kontrola pomocí 2D prefixových součtů Řešení v $\O(R S\cdot \min(R,S))$ pomocí počítání "hloubky" každé nuly (kolik nul je ve sloupci/řádku za ní) Úvod do RAMu – definice a nepřímá adresace, vysvětlení proč neomezená paměť nedává smysl (je to pak příliš mocný model) Úkoly: soucetK, odmocnina, podmatice Studijní materiály: Popis RAMu(ADS)
13.3.	Hashování, úvod do rozděl a panuj: Opakování hashování z přednášky – princip, kolize, řešení kolizí řetězením a sléváním Lehký příklad na hashování: Mějme přirozená čísla $A_1,\dots,A_n$ a čı́slo $K$. Jak zjistit, zda existuje dvojice $A_i$ a $A_j$ se součtem právě $K$? – Došli jsme nejdříve k hashování do tabulky velké $K$ a pak do tabulky velké $N$. Mějme neznámou hashovacı́ funkci $h$ hashující prvky z univerza do množiny velké $m$. Pokud o této funkci nic dalšı́ho nevı́te, kolik pokusů v nejhorším případě potřebujete, abyste našli $k$-tici prvků, které se všechny zobrazı́ do téže přihrádky? – $(k-1)\cdot m + 1$ Hanojské věže – Tři tyče, na první z nich vyskládané těžké kotouče od největšího (vespod) po nejlehčí (nahoře). Vždy lze hýbat jen s jedním kotoučem najednou a nelze položit větší kotouč na menší. Vymyslete algoritmus přesunující všechny kotouče z první tyče na poslední. – nápověda: rozděl a panuj Úkoly: vazeni (pozor, jen do příštího cvika) Studijní materiály: Hešování(KSP)
20.3.	Rozděl a panuj: Dodělání úkolu s vážením kuliček Nastínění idei důkazu spodního odhadu třídění a spodní odhad na nutný počet porovnání při vážení kuliček Probrání domácího úkolu posloupnost MergeSort dělící ne na poloviny, ale na $k$ částí – ukázali jsme si, že není lepší, než binární mergesort. Příklad s kabelem: Máme tlustý kabel obsahující $N$ drátů. Na jednom konci je máme očíslované a na druhém chceme zjistit, jaký drát je spojen s jakým na druhém konci. Můžeme na jedné straně na nějaké dráty přivést proud a na druhém konci zjistit, které nám rozsvítí žárovku (obvod uzavřeme třeba přes železnou kostru budovy, pro elektrotechnické fajnšmekry). Na co nejméně přecházení mezi konci kabelu (případně na co nejméně elementárních operací) zjistěte, který drát je který. Zvládli jsme na $N$ přechodů s $\O(N^2)$ operací, nebo na $\log N$ přechodů s $\O(N\log N)$ operací, nebo pomocí triku na $2$ přechody s $\O(N^2)$ operacemi. Úkoly: mergesort, sroubky Studijní materiály: Rozděl a panuj(ADS), Rozděl a panuj(KSP)
27.3.	Třídění: BubbleSort – Připomenutí a ukázání si, pro jaké vstupy: Potřebuje kvadratický čas (vstup setříděný pozpátku) Mu stačí lineární čas (již setříděný vstup) Udělá $k$ hlavních cyklů (při $k$ prvcích posunutých proti směru průchodu) Zig-zag verze pro praktické použití QuickSort – Jak se dá volit pivot a nešťastné vstupy: Pro volbu prvního prvku jako pivota – již setřídění posloupnost Pro volbu prostředního prvku jako pivota – $\dots5,3,1,2,4\dots$ Máme $N$ papírků $K$ různých barev (kde $N$ je výrazně větší, než $K$). Setřiďte je co nejrychleji s $\O(K)$ pomocné paměti. Umíte ale papírky jen porovnat a dva prohodit – zvládli jsme v čase $\O(N)$. Třídíme $K$-písmenná jména z abecedy a-z. Jak je utřídit co nejrychleji? – Víceúrovňové přihrádkové třídění prováděné od posledního písmena k prvnímu (pro zachování stability). Povídání o zápočtových programech Studijní materiály: Třídění(ADS), Třídění(KSP)
3.4.	Grafy: Reprezentace grafů v počítači: Matice sousednosti (dvourozměrné pole) Seznam sousedů (pole spojových seznamů) Matice incidence (příliš se nepoužívá) Poznávání grafu stromu – pomocí DFS a sledování zpětných hran Poznávání bipartitního grafu – DFS s číslováním a nacházení cyklů liché délky, BFS s barvením 2 barvami Počítání průměru grafu (délky nejdelší cesty): Pomocí násobení matic sousednosti – poslední objevivší se jednička značí nejdelší cestu (v čase $\O(N^4)$) Pomocí DFS z každého listu v $\O(N^2)$ Pomocí dvou DFS – prvním DFS najdu nějaký nejvzdálenější vrchol, ten bude na nějaké nejdelší cestě (potřeba dokázat), druhým DFS z tohoto vrcholu již najdu nejdelší cestu (v čase $\O(N)$) Pomocí jednoho DFS – procházím rekurzivně z nějakého vrcholu, z rekurze si vracím hloubku podstromů a v každém vrcholu zkouším složit nejdelší cestu jako kombinaci dvou nejhlubších podstromů (v čase $\O(N)$) Úkoly: odtrhavani, cyklus Studijní materiály: Grafy(KSP)
10.4.	Pokračování grafů Uvažme ulice na Manhattanu jako čtvercovou síť (bludiště). Máme porouchané auto, které umí jezdit jen dopředu a zatáčet vpravo. Jak najdeme nejrychlejší cestu do servisu? Nafouknutí stavového prostoru na 4 Manhattany, jeden pro každé otočení, natáhnutí správných hran a BFS na tomto grafu. Hledání silně souvislých komponent (SSK) pomocí Tarjanova algoritmu (s číslováním vrcholů) Hledání mostů a artikulací v grafu Definice vrcholového pokrytí grafu Úkoly: bludiste, legie Studijní materiály: Základní grafové algoritmy(ADS)
17.4.	Velikonoční pondělí – cviko není
24.4.	Hledání cest: Dijsktrův algoritmus na hledání nejkratších cest + zopakování haldy Úprava grafu pro Dijkstru: odstranění záporných hran přičtením (odečtením) nejvíce záporné hrany – nefunguje Bellman-Fordův algoritmus – zvládá záporné hrany (ale ne záporné cykly) Proč je problém se zápornými cykly Floyd-Warshallův algoritmus (hledání nejkratší cesty mezi všemi dvojicemi měst) Obchodníkem za starých časů: Mějme mapu království s městy a cestami mezi nimi. Na cestách číhají lupiči – u každé cesty mezi městy je poznamenána pravděpodobnost, že karavana jedoucí po této cestě projede v pořádku. Naplánujte nejbezpečnější trasu z jednoho města do druhého. Úkoly: ruzneCesty, kamion Studijní materiály: Halda, heapsort a Dijkstrův algoritmus(KSP), Studijní materiály: Nejkratší cesty(ADS)
1.5.	Svátek práce – oslavíme nepracováním (cviko není)
8.5.	Den osvobození – cviko není
9.5.	Náhradní cviko – od 17:20 v S10 Intervalové stromy: Úvodní motivace – připomenutí prefixových součtů (konstrukce v $\O(N)$, dotaz v $\O(1)$). Co prefixové součty neumí? Zadefinování intervalových stromů Konstrukce Tvrzení s důkazem: Každý interval lze seskládat nejvýše z $2\log N$ triviálních intervalů Update v $\O(\log N)$ Jak modifikovat intervalový strom, když chci ne součet, ale maximum nebo minimum na intervalu? Problém malíře chodníků – Máme chodník (rozdělený po celých metrech) délky $N$ a máme $Q$ příkazů "Namaluj chodník od $a$ do $b$ barvou $c$". Chtěli bychom vědět barvu každého políčka chodníku po provedení všech příkazů a pak obarvit chodník až výsledným obarvením. Spočtěte to co nejrychleji aneb intervalové updaty. Robotické rameno – máme robota s $N$ klouby a $N$ rameny mezi nimi délek $l_1, l_2, \dots$. Budou nám postupně přicházet příkazy "Otoč $i$-tý kloub o $\alpha$ stupňů" a po každém takovém příkazu chceme vrátit pozici manipulátoru na konci posledního ramene. Kontrola správného uzávorkování – Máme $2N$ závorek a chceme nad nimi provádět rychle operace "Otoč $i$-tou závorku a urči, jestli jsou nyní závorky správně uzávorkované" Úkoly: druhyNejmensi, median Studijní materiály: Intervalové stromy(KSP)
15.5.	Vyhledávací stromy: Zopakování principu BVS a důvodů, proč chtít vyvážené BVS AVL stromy – Vyvážené stromy s podmínkou, že výška podstromů každého vrcholu se liší maximálně o jedna. Zopakování rotací. Červeno-černé (red-black) stromy – Několik různých definic: Všechny cesty od kořene k listům obsahují stejně černých vrcholů Každý červený vrchol má právě 2 černé syny (tedy nikdy nejsou dva červené za sebou) Všude, kde není pokračování, tak visí virtuální (černé) listy – to vede k tomu, že každý vnitřní vrchol má vždy dva syny (třebaže virtuální) $(a,b)$-stromy – Každý vrchol má od $a$ do $b$ synů (včetně) pro nějaké $b\ge 2a-1$, hodnoty jsou v listech a všechny na stejné hladině. Při přidávání lze při přesáhnutí $b$ předávat vrcholy sousedovi, nebo vrchol rozštěpit a přidat odštěpený vrchol rekurzivně do otce. Při odebrání podobně (půjčujeme vrcholy od sousedů a případně slepujeme sousedy). Výstavba BVS z pole a ze spojáku v $\O(N)$ Úvod do minimálních koster (pokračování na dalším cviku) Úkoly: treeDiam, inverze Studijní materiály: Vyhledávací stromy(ADS), Vyhledávací stromy(KSP)
22.5.	Minimální kostry a opakování: Řezové lemma – nejlehčí hrana z každého řezu patří do minimální kostry Jarníkův, Borůvkův a Kruskalův algoritmus (Jarník a Kruskal z přednášky, Borůvka navíc) Jarník – jeden postupně narůstající stromeček, vždy (pomocí haldy) přidáváme nejlehčí hranu z řezu mezi narůstajícím stromečkem a zbytkem grafu. Borůvka – mnoho najednou narůstajících "borůvkových keříků", jeden krok (spojení každého keříku s nejbližším jiným) zabere přes všechny keříky čas $\O(M)$, kroků je potřeba $\O(\log N)$. Kruskal – utřídí si hrany a pak přidává hrany od nejlehčí, pokud nevytvoří cyklus, na to se hodí Union-Find umějící rychle provádět dotazy na komponenty a spojování komponent. Jak se změní algoritmy (a řezové lemma), pokud povolíme neunikátní váhy hran? Algoritmy nijak, lemma je upraveno, že existuje alespoň jedna minimální kostra, která obsahuje danou minimální hranu z řezu. Barvení rovinných grafů pomocí 6 barev v $\O(N)$ Úkoly: medianPos, presmycky, anketa Studijní materiály: Minimální kostry(ADS), Minimální kostry(KSP)
A to je tento semestr vše, přeji hodně zdaru u zkoušek a získávání zápočtů :-)

Domácí úkoly

Aby se podpořila práce během semestru, tak má každý úkol stanovený termín (typicky tři týdny, platí odevzdání do začátku cvičení) kdy je za plný počet bodů. Po termínu je ho možné odevzdat až do začátku zkouškového období za dolní celou část poloviny bodů.

Preferovaný způsob odevzdání je emailem (přímo v těle emailu, PDF, čistý text v UTF-8, čistý text v ASCII, …). Při prvním odevzdání úkolu si zvolte přezdívku, pod kterou chcete být uvedeni v tabulce bodů, nebo napište že na webu nechcete být uvedeni vůbec.

Datum	Úkol	Body	Zadání
20.02. Termín: 06.03.	posloupnost	10	Vodohospodáři každou minutu sledovali přítok/odtok z vodojemu a zaznamenávali si tato čísla. Máte tedy posloupnost $N$ celých čísel (kladná značí přítok, záporná odtok). Vodohospodáři by chtěli označit souvislý úsek, ve kterém měli největší přítok, neboli souvislou podposloupnost s největším součtem.
06.03. Termín: 27.03.	soucetK	10	Na stole nám stojí řada různě plných lahví uspořádaných od nejprázdnější po nejplnější. V každé z nich je nějaký celočíselný počet mililitrů vody. Chtěli bychom v této posloupnosti lahví najít dvě takové, které v součtu mají dohromady přesně $K$ mililitrů vody.
	odmocnina	7	Jak co nejrchleji spočítat celočíselnou odmocninu čísla $x$? Tedy najít $y$ takové, že $y^2 \le x < (y+1)^2$. Vymyslete řešení rychlejší, než lineární k $x$ (nejlépe ještě rychlejší, než $O(\log x)$).
	podmatice	10	BONUS (pokračování ze cvik): Vymyslete postup, který v matici $R\times S$ z jedniček a nul najde největší (co do obsahu) nulovou podmatici. Na cvičení jsme zvládli $\O(RS\cdot\min(R,S))$, zkuste vyřešit v $\O(RS)$.
13.03. Termín: 20.03.	vazeni	8	Jen do příštího cvika: a) Máme 12 kuliček a rovnoramenné váhy. Víme, že jedna kulička je lehčí nebo těžší (ale nevíme co z toho), než ostatní. Kolik nejméně vážení potřebuji (při jednom vážení mohu na misky na každou misku vah i více kuliček), abych určil, která to je a rozhodl, zdali je lehčí nebo těžší než ostatní. b) To stejné, ale s 13 kuličkami, jak se situace změní?
20.03. Termín: 03.04.	mergesort	10	Implementujte mergesort bez použití rekurze. Řešení můžete sepsat v pseudokódu nebo jako zdroják v nějakém imperativním programovacím jazyce – Pascal, C, C#, Java, …
	sroubky	12	Máme $N$ šroubků a $N$ matiček různých velikostí. Vždy právě jedna matička pasuje na právě jeden šroubek, o ostatních zjistíme jen, jestli je matička malá anebo velká, jinak jsou matičky i šrouky mezi sebou neporovnatelné (nezjistíme, jaký šroubek je větší, nebo o kolik nesedí matička). Vymyslete jak s co nejmenším počtem pokusů spárovat všechny šroubečky a matičky dohromady.
03.04. Termín: 18.04.	odtrhavani	10	Mějme souvislý neorientovaný graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?
	cyklus	5	Poznejte, jestli označený vrchol v neorientovaném grafu leží na cyklu
10.04. Termín: 24.04.	bludiste	10	Máme bludiště zadané grafem (s $N$ vrcholy a $M$ hranami), ve kterém se nachází (malé) $K$ barevných zamčených dveří a $K$ barevných klíčů. Klíč vždy pasuje ke stejně barevným dveřím a klíčů můžete nést najednou, kolik chcete. Na začátku startujeme od hradní brány a v bludišti je princezna, ke které se chceme dostat. Najděte k ní nejkratší cestu.
	legie	8	Za dob starého Říma byl velký problém s barbary, kteří loupili na obchodních cestách. Císař proto chce nechat každou cestu hlídat. Cesty v říši mají tvar stromu (nikde není z cest cyklus, kořenem stromu je Řím – podle úsloví, že všechny cesty vedou do Říma) a v každém vrcholu je město. Cesta je hlídána, pokud alespoň na jednom jejím konci je umístěna legie. Jenže legií je nedostatek a tak by Císař po vás chtěl ohlídat (pokrýt) všechny cesty mezi městy, ale použít na to co možná nejméně legií.
24.04. Termín: 15.05.	ruzneCesty	10	Mějme mapu města – orientovaný graf silnic a jeden označený vrchol jako radnici. Radní by pro všechny ostatní vrcholy zajímalo, kolik do nich z radnice vede různých nejkratších cest = cest s nejmenším možným počtem silnic. Dvě cesty považujeme za různé, pokud se liší alespoň v jedné hraně.
	kamion	10	Mějme mapu města ve tvaru orientovaného grafu. Každou hranu ohodnotíme podle toho, jaký nejvyšší kamion po dané ulici může projet. Po cestě tedy projede maximálně tak vysoký náklad, kolik je minimum z ohodnocení jejich hran. Jak pro zadané dva vrcholy najít cestu, po níž projede co nejvyšší náklad?
09.05. Termín: 22.05.	druhyNejmensi	10	Naprogramujte (stačí sepsat v pseudokódu nebo jako zdroják v nějakém imperativním programovacím jazyce – Pascal, C, C#, Java, …) intervalový strom vracející druhý nejmenší prvek na zadaném intervalu. Stačí dvě základní operace: Aktualizace hodnoty na indexu i Vrácení druhého nejmenšího prvku na intervalu (a,b)
	median	5	Upravte binární vyhledávací strom tak, abyste vždy zvládli v čase $\O(\log N)$ najít medián (prostřední prvek).
15.05. Termín: 29.05.	treeDiam	5	Na vstupu dostanete binární strom (obecně nevyvážený). Úkolem je vymyslet algorimus, který na tomto stromě najde nejdelší cestu mezi dvěma vrcholy.
	inverze	10	Inverze v permutaci je jakákoliv dvojice prvků, která se vyskytne v opačném pořadí (více viz Wikipedia). Navrhněte algoritmus počítající počet inverzí v zadané permutaci (nápověda: použijte binární vyhledávací stromy)
22.05. Termín: 30.06.	medianPos	10	Budete postupně dostávat čísla (neutříděná). Sestrojte datovou strukturu, která po každém přidání čísla zvládne vypsat, jaký je aktuální medián (prostřední prvek) této posloupnosti.
	presmycky	10	Dostanete slovník a seznam hledaných slov. Ke každému hledanému slovu najděte ve slovníku všechny anagramy neboli přesmyčky, které z tohoto slova můžou vzniknout.
	anketa	5	Feedback aneb napište, co se vám na cviku nelíbilo (můžete i co se vám líbilo) a jak by se ještě dalo vylepšit. Třeba: Celková atmosféra cvika - vysvětloval jsem všechno jasně, bylo mi rozumět? Čas věnovaný jednotlivým tématům - nebylo něčeho moc? Podmínky na získání zápočtu - lehké, těžké? Domácí úkoly - přišly vám lehké/těžké? radši více menších nebo málo větších úkolů? Vztah přednášky a cvika - chodili jste na přednášku? Chápali jste věci na přednášce, hodilo se opakování na cviku? … Díky za dobré připomínky :-)
Celkem:		175