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:

Získané body:

Jméno Úkoly Bonusy Bodů Zápočťák Zápočet
Andoposloupnost(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)116Třídící algoritmyOK
ASRockvazeni(8), inverze(10), treeDiam(5)23--NE
Atsuko Kagariposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), druhyNejmensi(10)100Mergesort knihovnaOK
Budgieposloupnost(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
102AVL stromOK
Diana Cavendishposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8)102Heapsort knihovnaOK
drozdoposloupnost(10), soucetK(10), odmocnina(7), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), kamion(10), ruzneCesty(10), druhyNejmensi(10)104Knihovna nejkratších cestOK
Falešný Martin Kubešaposloupnost(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
101DijkstraOK
GOGposloupnost(10), soucetK(10), podmatice(10), vazeni(8), mergesort(10), sroubky(9), odtrhavani(10), cyklus(5), legie(8), kamion(10)
  • Hezký zápočťák: 10
100BludištěOK
Honzaposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10)102Červeno-černé stromyOK
Idefixposloupnost(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)
103DijsktraOK
Jakub Matěnaposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10), ruzneCesty(10)102Dijsktrův algoritmusOK
KartoffelsoucetK(10), podmatice(10), vazeni(8), odtrhavani(10), cyklus(5), legie(8), bludiste(8), ruzneCesty(10), kamion(10)79--NE
krokodylposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(5), mergesort(10), sroubky(11), odtrhavani(10), cyklus(5), bludiste(10), ruzneCesty(10), druhyNejmensi(10)108Editační vzdálenostOK
Kyryloposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(8), ruzneCesty(10)108PodmaticeOK
Martin Kubešaposloupnost(10), soucetK(10), odmocnina(7), sroubky(12), odtrhavani(10), cyklus(5), median(2), kamion(10), ruzneCesty(10), treeDiam(5), medianPos(10), presmycky(10)101Funnel sortOK
Michal Nemčokposloupnost(7), soucetK(4), odmocnina(7), vazeni(8)26--NE
ORposloupnost(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
113Knihovna pro AVL stromyOK
Oskarposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(8), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), bludiste(10), legie(8), ruzneCesty(10)110Splay stromyOK
Pán Historieposloupnost(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)-stromyOK
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
112B-stromyOK
rcnposloupnost(10), soucetK(10), odmocnina(7), podmatice(10), vazeni(10), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), legie(8), bludiste(10)102Nejkratší cestyOK
SSSposloupnost(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
103Maticová knihovnaOK
Stepoposloupnost(5), soucetK(10), odmocnina(7), podmatice(10), vazeni(5), mergesort(10), odtrhavani(10), cyklus(5)62--NE
weiXiaoposloupnost(10), vazeni(10)20--NE

Studijní materiály


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