Cvičení z Efektivních algoritmů v ZS15/16

Cvičení probíhají každou středu od 12:45 a 16:15 v učebně 1242 (budova A).


Podmínky zápočtu

Body lze získat za:

Zápočet je za

Konzultace

Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229.

kontakt: tomas.valla@fit.cvut.cz

Studijní materiály

K dispozici je vývojová verze studijních textů, které pokrývají některé kapitoly z předmětu.

Mentální trénink

Kdo si chce trénovat své algoritmické myšlení nad rámec cvičení (nebo zkrátka jen řešit pěkné úlohy ve volném čase), má možnost.

Doporučuji následující dva zdroje:

Oba zdroje obsahují takřka nekonečnou zásobu zajímavých algoritmických úloh, od lehkých po brutální, včetně vzorového řešení, u KSP i s rozsáhlou sadou studijních materiálů.


Obsah cvičení

7.10.

Podmínky na zápočet. Co nás v předmětu čeká. Úloha s házením vajíčka z paneláku (1, 2, neomezeně vajíček). Asymptotická analýza počtu hvězdiček vypsaných několika kódy. Model RAM, jak vypadá jeho kód. Triky s neomezenou kapacitou buňky, aneb jak zakompresit veškerou paměť programu na RAMu do konstantně mnoha buněk. Hledání chybějícího čísla z 1..N na vstupu. Na vstupu N vzestupně setříděných čísel a číslo K. Jak co nejrychleji zjisti, zda mezi nimi existuje dvojice se součtem K?

14.10.

Jak slévat 2 (3) vzestupně utříděné spojáky. Jak pomocí dvou zásobníků (a ničeho dalšího) simulovat funkcionalitu fronty. Na obvodu kružnice je N bodů, jak najít rychle dvojici, jejíž spojnice prochází středem kružnice.

21.10.

Kolikrát průměrně potřebujeme hodit mincí, aby padla panna? A co když je mince falešná a panna padá s pravděpodobností p? Důkaz Věty 7 z 2. přednášky Jak dlouho průměrně trvá shromáždit sbírku N kartiček pomocí nákupů naslepo? Hlavolamy s nalezením těžší a jiné kuličky z N pomocí rovnoramenných vah. Analýza Mergesortu. Modifikace Quicksortu na hledání K-tého nejmenšího prvku včetně analýzy.

28.10.

Binární halda a operace s ní. Na vstupu K a N prvková posloupnost, kde každý prvek leží nejvýše K pozic od místa, kde by ležel v setříděné posloupnosti; jak co nejrychleji posloupnost dotřídit. Slévání K setříděných posloupností. Posloupnost, z níž lze odebrat K prvků, aby byla setříděná; jak ji setřídit.

4.11.

Suplování.

11.11.

Suplování.

18.11.

Jak vytisknout data z BVS vzestupne setridena. Proc nemuze byt Insert v BVS rychlejsi nez O(log N)? Jak v BVS najit k prvku nejblizsi vyssi? Proc kdyz N-krat (zacneme v minimu) zavolame predchozi funkci (a projdeme tak strom), zabere to cas jen O(N)? Neboli amortizovane O(1) na jedno volani. Jak najit nejdelsi cestu ve stromu

25.11.

Psali jsme písemku.

2.12.

N mest, z kazdeho vedou max 2 cesty do mesta s vyssim cislem. Kolika zpusoby se lze dostat z mesta 1 do mesta N? Konstrukce grafu, ktery "pocita" fibonacciho cisla - a tupa rekurze tudiz bude pomala. A co kdyz mam hrany ohodnocene delkou v kilometrech a ptam se na delku nejkratsi/nejdelsi cesty 1..N? Co kdyz pocet hran neni omezeny na 2, ale je libovolny? Je dan trojuhelnik cisel, Zacnu nahore a sestupuju po radcich dolu, v kazdem kroku se rozhodnu, jestli postoupim do stejneho sloupce, ci do o 1 napravo, cil: najit cestu shora dolu s maximalnim souctem. Co cesta s maximalnim soucinem?

9.12.

Minimální vrcholové pokrytí (váženého) stromu. Nejdelší rostoucí podposloupnost. Analýza logaritmické hloubky AVL a RB stromů.

16.12.

Rychlý výpočet Fibonacciho čísel mocněním matice a algoritmus rychlého mocnění. Obecný rychlý výpočet lineárních rekurencí. Počet vydláždění mřížky. Nejdelší rostoucí podposloupnost s jedním poklesem. Rozřezání stringu na minimální počet palindromických bloků.

21.12.

Vysvětlování Fibonacciho hald. Join dvou B-stromů.

6.1.

Psala se písemka.

Úlohy k vyřešení