Cvičení z Algoritmů a Datových Struktur I

V LS 2016/2017 vedu jedno cvičení k přednášce Ondřeje Čepka z Algoritmů a datových struktur I. Cvičení je primárně určené pro posluchače bioinformatiky, ale po domluvě se tam mohou přihlašovat i studenti jiných oborů.

Cvičení se koná ve čtvrtek od 15:40 v S10.

Co jsme dělali

datum téma
23. 2. Rekurzivní hádanky a Euklidův algoritmus.
2. 3. Pokusy o definici algoritmu a časové složitosti. Programování na RAMu. Jak zneužívat velká čísla.
9. 3. O datových strukturách a jejich rozhraní. Různé varianty hešování.
16. 3. Rozděl a panuj: Mergesort a násobení čísel.
23. 3. Rozděl a panuj: Počítání inverzí, odvození Kuchařkové věty. Rekurence nejen kuchařkové:
  • T(n) = 2T(n/2) + Θ(n2)
  • T(n) = 2T(n/3) + Θ(n)
  • T(n) = T(n/2) + Θ(1)
  • T(n) = T(n/2) + T(n/3) + Θ(n)
  • T(n) = 2T(n) + Θ(n log n)
  • T(n) = n1/2 T(n1/2) + Θ(n)

Domácí úkoly

Na cvičeních budu zadávat různě obtížné domácí úkoly, měli byste za ně získat celkem 100 bodů. Po dvou týdnech od zadání úkolu na cvičení povím nápovědu, od té doby můžete za úkol získat jen poloviční počet bodů.

DatumKódBodůZadání
23. 2. krac9Přirozenému číslu budeme říkat kráčmerné, pokud ho jde zapsat ve tvaru 3i5j7k pro nějaká přirozená i, j, k. Vymyslete algoritmus, který co nejefektivněji najde prvních N kráčmerných čísel.
sqrt7Jak spočítat celočíselnou druhou odmocninu? Tím pro dané x myslíme přirozené číslo y takové, že y2≤ x < (y+1)2. Dejte si pozor, abyste správně zaokrouhlovali.
bug0Ke konci semestru vydáváme knížku o ADS. Budu rád, když se na ni podíváte a upozorníte na všechny chyby, na které narazíte. Za každou novou faktickou chybu dostanete 1 bod.
2. 3. ram9Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti.
bube10Jaká je průměrná časová složitost bublinkového třídění? Přesněji: pokud dostaneme na vstupu náhodnou permutaci čísel 1 až n, jaká bude střední hodnota doby výpočtu? Předpokládáme, že algoritmus se zastaví, jakmile během jednoho průchodu nic neprohodí.
mmul10Podnikneme pokus s RAMem s konstantní cenou instrukce a neomezeným rozsahem čísel. Vymyslete algoritmus, který dostane dvě matice N×N, nezáporných čísel a v čase O(N2) je vynásobí.
9. 3. oadel10Uvažujme následující variantu hešování s otevřenou adresací: v každé buňce tabulky si pamatujeme prvek a počet následujících prvků se stejnou hodnotou hešovací funkce. Navrhněte algoritmy pro operace Find, Insert a Delete. Kvůli zmatkům v zadání zustává otevřené ještě týden.
psum10Je dána posloupnost celých čísel a číslo X. Existují nějaké dva (ne nutně různé) prvky posloupnosti, jejichž součet je přesně X? Pokuste se najít algoritmus pracující co nejrychleji (a) v průměru, (b) v nejhorším případě.
16. 3. muls8Odvoďte prostorovou složitost rekurzivního algoritmu na násobení čísel z cvičení.
kabel10/15Mějme dlouhý kabel, z jehož obou konců vystupuje po n drátech. Každý drát na levém konci je propojen s právě jedním na konci druhém a my chceme zjistit, který s kterým. K tomu můžeme používat následující operace: (1) přivést napětí na daný drát na levém konci, (2) odpojit napětí z daného drátu na levém konci, (3) změřit napětí na daném drátu na pravém konci. Navrhněte algoritmus, který pomocí těchto operací zjistí, co je s čím propojeno. Snažte se počet operací minimalizovat. 5 bodů navíc: Nalezněte neadaptivní řešení předchozího cvičení, tedy takové, v němž položené dotazy nezávisí na výsledcích předchozích dotazů.
klow8Dokažte, že v úloze o kabelu dvou cvičeních je potřeba Ω(n log n) dotazů. Pokud nevíte, jak na to, dokažte to alespoň pro neadaptivní algoritmy.
23. 3. rec17Vyřešte rekurenci T(n) = 3T(n/2) + 1, T(1) = 1.
rec210Vyřešte rekurenci T(n) = T(n/3) + T(n/7) + n, T(1) = 1.
base12Máme n-ciferné číslo v soustavě o základu A a chceme ho převést do soustavy o základu B. Prozradíme, že existuje efektivnější řešení než v Θ(n2).

Pokud je úkolem sestrojit algoritmus, nezapomeňte stanovit jeho časovou a paměťovou složitost.

Úkoly prosím posílejte na mj+ads@ucw.cz jako obyčejný text nebo PDF.

Výsledky

Pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, dejte mi vědět.

JménoPříkladyBodů
Květa Brázdilovákrac(9) sqrt(3.5) ram(9)21.5
Cryptidkrac(9) bube(10) sqrt(7)26
Kateřina Červinkovákrac(9) sqrt(7) ram(9) bube(10)35
Patrik Dokoupilsqrt(7) bube(10) krac(9) ram(9)35
Kamila Herkovákrac(9) sqrt(7) bube(10) ram(9) mmul(10) psum(10)55
Jan Horyna0
Lukáš Hruškasqrt(7) krac(1) ram(5)13
Vít Kabelesqrt(7) krac(4.5)11.5
Adam Králkrac(9) sqrt(7)16
Adrián Mačáksqrt(7)7
Filip Milichovskýsqrt(7) psum(10)17
The Quyet Nguyensqrt(7) ram(9) psum(10)26
Michal Pospěchkrac(7) sqrt(7)14
Matej Radakrac(9) sqrt(7)16
Jiří Sejkorasqrt(7) krac(7) ram(9) bug(1) bube(2)26
Alexandra Shumilovasqrt(7) krac(9) bube(10)26
Patril Smelíksqrt(7)7
Jan Šáfrsqrt(7) krac(9)16
Daniel Šipošsqrt(7) krac(9) ram(9)25
Vulposqrt(7) krac(9)16
Michaela Vystrčilovásqrt(5) krac(9) bube(10) ram(9)33
Ysqrt(0) krac(0)0
Zlatovláskasqrt(7) krac(9) bube(10)26
Stránku spravuje Martin Mareš