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:
- písemky: 2×10 bodů
- progtestové úlohy: 3 úlohy celkem za 30 bodů (25% bonus za odevzdání 1. týden)
- ACM soutěž: 2 body za úlohu z CTU Open, 6 bodů za úlohy vyšších kol
- aktivita: 1 bod za správně vyřešenou úlohu předvedenou u tabule
Zápočet je za
- alespoň 10 bodů z písemek, a současně
- alespoň 28 bodů celkem
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í
- Kontrukce řešení u úloh optimální závorkování a LCS pro k=2.
- LCS pro k=3 nebo větší.
- Maximální vybraná rostoucí podposloupnost v případě, že čísla jsou malé integery, třeba 1..100.
- operace Merge dvou Bstromů T1, T2, kde hodnoty v T2 jsou všechny větší než ty v T1 (v O(log n))
- operace Split Bstromu - rozdělit podle zadané hodnoty na dva Bstromy (v O(log n))
- Setřiďte stringy v čase O(součet délek).
- Dáno N a na vstupu N čísel z rozsahu 1,…,N^3, navrhněte jak je setřídit v čase O(N).
- Dokažte, že pro nalezení těžší kuličky z N je třeba alespoň \Omega(log N) vážení.
- Dokažte, že pro nalezení nejmenšího prvku z N je třeba vždy provést alespoň N-1 porovnání.
- Navrhněte co nejkvalitnější hashovací funkci pro hashování stringů.
- Na vstupu N-2 přeházených čísel z 1..N, právě dvě chybí. Jak je najít?
- Dáno pole P_1,...,P_n, definitoricky P_0=P_{n+1}=\infty. Řekneme, že P_i je lokální minimum,
pokud P_{i-1}≥P_i≤P_{i+1}. Navrhněte nějaký rychlý algoritmus, který najde nějaké lokální minimum.
- Analyzujte složitost Eratosthenova síta