Cvičení z Algoritmů a datových struktur I

Zde jsou informace pro studenty předmětu Algoritmy a datové struktury I (2016/2017), cvičení v pondělí od 9:00.

Co se dělalo na cvičení

• 1. týden: Informace k výuce, příklady jednoduchých algoritmů a jejich porovnání. Nastínění asymptotické časové složitosti.
  • Hledání souvislé podposloupnosti celých čísel s nejvyšším součtem.
  • Počítání n-tého Fibonacciho čísla.
  • Na zamyšlení do příště: Upravte algoritmus na hledání úseku posloupnosti s nejvyšším součtem tak, aby počítal i hranice úseku, nejenom součet.
• 2. týden: Příklady na asymptotickou notaci a jednoduché algoritmy.
  • Házení vajíček z mrakodrapu.
  • Hledání nejmenšího přirozeného čísla, které chybí v rostoucí posloupnosti přirozených čísel.
  • Hledání největší nulové podmatice.
  • Na zamyšlení do příště: Dokažte, že $\log n\in O(n^\varepsilon)$ pro všechna $\varepsilon > 0$.
• 3. týden: Byla krátká písemka na $O$-notaci. Výpočetní model RAM.
  • Jak zakódovat posloupnost celých čísel do jednoho.
  • Úvahy o RAMu s různou cenou aritmetických instrukcí.
  • Interpretace programu na RAMu a časová analýza.
• 4. týden: Jsem pryč, zaskakuje Verča Slívová. Cvičení na hešování.
• 5. týden: Rozděl a panuj. Dokázali jsme si Master theorem pomocí počítání práce na jednotlivých patrech stromu rekurze.
  • Počítání rekurencí.
  • Přiřazování matiček ke šroubkům.
  • Počítání počtu inverzí v posloupnosti.
  • Na zamyšlení do příště: Najděte příklad alogritmu typu rozděl a panuj, který tráví většinu času v kořeni (tedy takový, kde je ${a / b^c} < 1$).
• 6. týden: Třídící algoritmy.
  • Špatné vstupy pro Bubblesort a Quicksort.
  • Heapsort.
  • Třízení $K$-písmenných jmen v $O(Ka)N$.
  • Třízení $N$ papírku $K$ různých barev s $O(K)$ pomocné paměti.
  • Třízení skoro setřízené poslupnosti.
  • Vícecestný mergesort.
• 7. týden: Základní grafové algoritmy. BFS, DFS.
  • Odtrhávání vrcholů grafu zachovávající souvislost.
  • Prohledávání stavového prostoru.
  • Rozbité auto na Manhattonu.
  • Hledání cesty v bludišti se dveřmi a klíči.
• 8. týden:Pokračování BFS a DFS. Nastínění nekratších cest.
  • Hledání mostů a artikulací.
  • Dva roboti v bludišti.
  • Hledání maximální nezávislé množiny a vrcholového pokrytí.
  • Nalévání vody do grafu, nastavování budíků a Dijkstrův algoritmus.
  • Hledání nejvyšší cesty pro průjezd kamionu.
• 9. týden: Velikonoční pondělí, cvičení odpadá.
• 10. týden: Nejkratší cesty – Dijkstra, Floyd-Warshall, Bellman-Ford a jejich modifikace.
• 11. týden: Svátek práce, cvičení odpadá.
• 12. týden: Den vítězství, cvičení odpadá.
• 13. týden:Binární vyhledávací stromy. (a,b)-stromy, (2,4)-stromy a jejich souvislost s červeno-černými stromy.
• 14. týden: Minimální kostry. Borůvka, Jarník, Kruskal. Datová struktura Union-Find.
  • Hledání nejtěžší kostry.
  • Hledání druhé nejlehčí kostry.
  • Hledání nejlehčí kostry s předepsanými listy.
  • Hledání minimální kostry v grafu, kde jsou ohodnocení hran z malá čísla omezená konstantou.

Studijní materiály

• Skripta Martina Mareše – skvělý studijní materiál v češtině, který pokrývá naprostou většinu témat probíraných na přednášce.
• Videonahrávky přednášek Martina Mareše z roku 2014/2015.

Domácí úkoly

Za úkoly lze získat plný počet bodů až do uvedeného deadline. Po tomto deadline jdou odevzdávat až do konce semestru nejvýše za polovinu bodů. Počet bodů za domácí úkol se odvíjí jak od zpracování, tak od kvality navrženého algoritmu.

Úkoly zatím posílejte e-mailem na adresu stinovlas+ads@kam.mff.cuni.cz a do předmětu uveďte název úlohy. Samotné řešení nechť je přiloženo ve formátu PDF a jeho součástí musí být i vaše jméno (ideálně někde v záhlaví). Nezapomeňte se podepsat celým jménem!

• matpower (6 bodů, do 6. 3.): Navrhněte algoritmus na mocnění matic $2\times 2$ a zapište jej v pseudokódu. Dokažte, že je algoritmus korektní a konečný a určete a dokažte jeho časovou složitost.
  Vstup: Matice $M=\begin{pmatrix}m_{1,1} & m_{2,1} \\ m_{1,2} & m_{2,2}\end{pmatrix}$ a $n\in \mathbb N\qquad$ Výstup: Matice $M^n$
• eggsalad (6 bodů, do 13. 3.): Máme mrakodrap s $n$ patry a $k$ vajíček. Víme, že pro všechna patra nižší než nějaké $p$ se vajíčko z nich hozené nerozbije a naopak, vajíčko hozené z patra $p$ či vyššího se vždy rozbije. Navrhněte postup, jak zjistit $p$ na asymptoticky co nejmenší počet pokusů pro obecné $n$ a $k$.
  Nápověda: Na cvičení jsme si ukázali, že pro jedno vajíčko potřebujeme $O(n)$ pokusů a pro dvě nám jich stačí $O(\sqrt n)$. Máme-li alespoň $\log n$ vajíček, stačí nám $O(\log n)$ pokusů (binárním vyhledáváním). Zajímavou otázkou je tedy, jak se to má pro $2 < k < \log n$.
• smalldiff (6 bodů, do 13. 3.): Navrhněte co nejrychlejší algoritmus, který pro danou posloupnost $n$ čísel a číslo $k$ nalezne co nejdelší úsek posloupnosti takový, že rozdíl libovolných dvou prvků úseku je nanejvýš $k$. Algoritmus zapište v pseudokódu, dokažte že je korektní a konečný a dokažte jeho časovou složitost.
  Příklad: Pro posloupnost $0,1,3,2,2,3,1,0,-1,1$ a $k=2$ je správná odpověď $6$.
• ramswitch (6 bodů, do 22. 3.): Vymyslete, jak na RAMu prohodit obsah dvou paměťových buněk, aniž byste použili jakoukoliv jinou paměťovou buňku a napište program pro RAM, který prohodí paměťové buňky [0] a [1]. Nezapomeňte, že registry jsou také paměťové buňky.
• recursion (6 bodů, do 3. 4.): Vyřešte rekurenci $T(n) = \sqrt n\cdot T(\sqrt n) + \Theta(n),\ T(1) = 1$. Pokud nezvládnete výsledek určit přesně, pokuste se jej alespoň co nejlépe odhadnout zdola i shora.
• ghostlady (6 bodů, do 22. 4.): Ve čtverečkové síti máte zakreslenou mapu hradu. Každý čtvereček je buď volný, nebo je zcela zaplněn zdí. Po hradu se pohybuje bílá paní, která začíná svou cestu ve čtverečku $X$ a chce se dostat co nejkratší cestou do čtverečku $Y$. Chodit může pouze vodorovně nebo svisle, nikoliv diagonálně. Bílá paní navíc umí procházet zdmi, ale takové procházení zdí není nic příjemného a proto se mu snaží vyhýbat. Najděte proto cestu z bodu $X$ do bod $Y$ takovou, že 1) prochází co nejméněkrát zdí, 2) je při daném počtu průchodů zdí co nejkratší. Každé vstoupení na čtvereček se zdí se počítá jako jeden průchod zdí (takže pokud mám zeď tlustou 3 čtverečky, počítá se jako 3 průchody zdí).
  
  Upřesnění: Jedná se o jednu úlohu, ne o dvě. Chceme najít nejlepší cestu. Cesta $P$ je lepší, než cesta $Q$ právě tehdy, když $P$ prochází zdí nejvýše tolikrát, kolikrát $Q$ a zároveň, pokud cesta $P$ prochází stejným počtem zdí, jako $Q$, tak je $P$ kratší, než $Q$.
• breakleg (6 bodů, do 24. 4.): Máte grafem zadanou mapu zasněženého a zamrzlého města. U každé hrany je zaznamenána pravděpodobnost (číslo mezi 0 a 1), že si při jejím průchodů zlomíte nohu. Navrhněte algoritmus, který najde mezi dvěma zadanými vrcholy cestu s nejnižší pravděpodobností zlomení nohy.
• parentheses (6 Y [bonusových] bodů, do 28. 5.): Máme 2N závorek a chceme nad numi umět rychle provádět operace "otoč i-tou závorku" a "urči, zda je posloupnost správně uzávorkovaná". Navrhněte datovou strukturu založenou na intervalových stromech, která nám umožní co nejrychlejší odpovědi na zadané dotazy.

Požadavky na zápočet

V průběhu semestru budou zadávány domácí úkoly a to jak teoretické, tak praktické. Počty bodů se budou lišit podle obtížnosti. V průběhu semestru bude také zadáno několik krátkých přepadových písemek. Body za písemky a domácí úkoly se sčítají.

Dohromady budou zadány písemky a domácí úkoly za $X$ základních bodů a $Y$ bonusových bodů, kde $X \ge Y \ge 0$. Získané základní a bonusové body se sčítají.

V průběhu semestru bude několik checkpointů se stanoveným minimálním počtem bodů na projití. Kdo bude mít méně bodů, než je checkpointem vyžadováno, musí si povinně domluvit na další týden (ve výjimečných případech na přespříští týden) konzultaci.

Pro získání zápočtu je třeba získat alespoň ${2\over 3}X$ bodů a zúčastnit se všech povinných konzultací.

Pokud budou někomu chybět na konci semestru body, bude možné domluvit se na napsání zápočtového programu (implementace nějakého netriviálního algoritmu či datové struktury v nízkoúrovňovém programovacím jazyce) za až ${2\over 9}X$ bodů (podle náročnosti).

Např. pokud by bylo $X=99$, pak hranice pro získání zápočtu by byla 66 bodů a za zápočtový program by bylo možno dostat až 22 bodů.