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)
30. 3. Hrátky s Bubblesortem. Přihrádkové třídění v poli. Třídění s log n různými hodnotami. Stabilní slévání. Třídění řetězců.
6. 4. O složitosti třídění – co věta říká a co neříká. Komponenty souvislosti, testování bipartitnosti, porouchané autíčko.
13. 4. Dva roboti v bludišti. DFS a klasifikace vrcholů. Mosty v grafech. Jak najít kružnici v orientovaném grafu?

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.
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 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). (Pozor, číslo se nemusí vejít do jedné celočíselné proměnné.)
30. 3. lib10Posloupnost N prvků byla krásně setříděná. I šla okolo zlá Bugzilla, vytáhla K prvků a vsunula je jinam. Jak posloupnost co nejrychleji opravíte? (K neznáte, ale můžete předpokládat, že je malé, a složitosti vyjadřovat vzhledem k N a K.)
12k10/15Jsou dány rovnoramenné váhy a 12 kuliček, z nichž právě jedna je jiná než ostatní, nevíme však zda je lehčí nebo těžší. Na misku lze dát i více kuliček naráz. Navrhněte, jak na 3 vážení najít tuto jinou kuličku a zjistit, jestli je lehčí nebo těžší. Dokažte, že na 2 vážení to nejde. 5 bodů navíc: Kdybychom měli kuliček 13, ale slevili z požadavku zjistit, zda je odlišná kulička lehčí nebo těžší, stále stačí 3 vážení. Pro 14 ale ne. Dokažte.
6. 4. kkun7Na jedné šachovnici N×N žil byl kulhavý kůň. To je šachová figurka, která v sudém tahu táhne jako jezdec, v lichém jako král. Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?
dele9Mě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ý?
sink10Mějme graf, který vznikl orientací úplného grafu (tj. mezi každými dvěma vrcholy vede hrana buď jedním, anebo druhým směrem), reprezentovaný maticí sousednosti. Ukažte, jak zjistit, zda v grafu existuje výpusť, tj. vrchol, do kterého vedou hrany ze všech ostatních vrcholů. Zkuste dosáhnout časové složitosti O(počet vrcholů). Můžete předpokládat, že matici už máte načtenu v paměti.
13. 4. zpet6Na orientovaný graf jsme spustili DFS. Může se v grafu nacházet kružnice složená ze samých zpětných hran? A pokud by graf byl neorientovaný?
stack7Nabízí se svůdná myšlenka, že DFS získáme z BFS nahrazením fronty zásobníkem. Na čem tento postup selže?
paths10Je dán neorientovaný graf a dva jeho vrcholy. Spočítejte, kolik mezi nimi vede nejkratších cest.

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) psum(10) oadel(10) rec1(7) rec2(10) kabel(15) muls(8) lib(10) dele(9)100.5
Cryptidkrac(9) bube(10) sqrt(7) rec1(7)33
Kateřina Červinkovákrac(9) sqrt(7) ram(9) bube(10) kabel(15) psum(5) muls(8) oadel(10) 12k(10) rec1(7) rec2(10)100
Patrik Dokoupilsqrt(7) bube(10) krac(9) ram(9) rec1(7) oadel(10) muls(8) kabel(10) rec2(10) 12k(10)90
Kamila Herkovákrac(9) sqrt(7) bube(10) ram(9) mmul(10) psum(10) oadel(10) muls(8) kabel(10) klow(8) rec1(7) lib(10)108
Jan Horyna0
Lukáš Hruškasqrt(7) krac(1) ram(5) oadel(10) rec1(7) rec2(10) kabel(10) muls(8)58
Vít Kabelesqrt(7) krac(4.5) ram(9) rec1(7) rec2(5) oadel(10) psum(10) kabel(10) muls(8)70.5
Adam Králkrac(9) sqrt(7) kabel(15) rec1(7)38
Adrián Mačáksqrt(7) oadel(10) kabel(10) muls(8) rec1(7) rec2(10) ram(9)61
Filip Milichovskýsqrt(7) psum(10) 12k(15) rec1(7) rec2(10)49
The Quyet Nguyensqrt(7) ram(9) psum(10) rec1(7)33
Michal Pospěchkrac(7) sqrt(7) ram(9) oadel(10) psum(10) muls(8) kabel(15) rec1(7) rec2(10)83
Matej Radakrac(9) sqrt(7) oadel(10) rec1(7)33
Jiří Sejkorasqrt(7) krac(7) ram(9) bug(2) bube(2) psum(10) kabel(15) rec1(7)59
Aleksandra Shumilovasqrt(7) krac(9) bube(10) rec1(7) muls(8) rec2(10) 12k(15) lib(10) kabel(10) klow(8)94
Patril Smelíksqrt(7) rec1(7) rec2(10) kabel(10) oadel(10) muls(8)52
Jan Šáfrsqrt(7) krac(9)16
Daniel Šipošsqrt(7) krac(9) ram(9) oadel(10) psum(5) muls(8) rec1(7) rec2(10)65
Vulposqrt(7) krac(9) oadel(10) psum(7) rec1(7)40
Michaela Vystrčilovásqrt(5) krac(9) bube(10) ram(9) muls(8) psum(5) kabel(15) rec1(7) rec2(10) oadel(10)88
Ysqrt(0) krac(0) rec1(7) rec2(10) base(0) kabel(10)27
Zlatovláskasqrt(7) krac(9) bube(10) rec1(7) base(0) oadel(10) kabel(15) muls(8) klow(8)74
Stránku spravuje Martin Mareš