Algoritmy a datové struktury 1 – cvičení

Cvičil Martin Koreček k přednášce Martina Mareše.

Letní semestr 2022/23, středa 14:00, učebna N3.

Podmínky pro získání zápočtu

Na každém cviku zpravidla zadám jeden domácí úkol. Čas na vypracování bude 14 dní. Občas můžu zadat bonusový úkol.

Na zápočet je třeba získat alespoň dvě třetiny počtu bodů ze standardních úloh (bonusové se počítají jen do vašeho skóre).

Co jsme dělali

15. 2.: Opakování \(\mathcal{O}\) notace, programování na RAMu. Úlohy (PDF)

22. 2.: Dokončení úloh z minulého týdne. Prohledávání grafů. Úlohy (PDF)

1. 3.: DFS, klasifikace hran, mosty a artikulace. Úlohy (PDF)

8. 3.: Topologická indukce, komponenty silné souvislosti, Dijkstra. Úlohy (PDF)

15. 3.: Pokračování Dijkstry, Bellman-Ford. Úlohy (PDF)

Pro zajímavost: někdejší matfyzáci vytvořili pěkná videa o technikách A* a Meet in the Middle. Obě techniky jsou podrobněji popsány také v Průvodci (od 2. vydání).

IDA* bohužel v Průvodci nenajdete, ale můžete si o něm přečíst např. na Wikipedii.

22. 3.: Minimální kostry. Úlohy (PDF)

29. 3.: Binární vyhledávací stromy. Úlohy (PDF)

5. 4.: Vyvažované stromy. Úlohy (PDF)

12. 4.: Intervalové dotazy, trie, hešování. Úlohy (PDF)

Fun fact: v čichovém ústrojí much bylo objeveno něco velmi podobného Bloomovu filtru, sloužícího k detekci dosud neznámých zápachů.

19. 4.: Cvičení nebylo.

26. 4.: Rozděl a panuj. Úlohy (PDF)

3. 5.: Různé úlohy (nenavazujeme na přednášku). Úlohy (PDF)

10. 5.: Cvičení nebylo (Rektorský den).

17. 5.: QuickSelect, LinearSelect. Úlohy (PDF)

Domácí úkoly

Odevzdávejte buď na papíře před začátkem cvičení, nebo v TXT/PDF na e-mail mk-hw@seznam.cz.

Cílem úkolů není, abyste napsali program v nějakém programovacím jazyce (s výjimkou první úlohy), proto neodevzdávejte zdrojové kódy. Jak řešení má vypadat dost dobře vystihují pravidla řešení teoretických úloh Korespondenčního semináře z programování.

• DÚ 1: Naprogramujte na RAMu libovolný třídící algoritmus pracující v čase \(\mathcal{O}(n \log n)\): V buňkách [1] až [n] bude posloupnost celých čísel a po zastavení programu chceme, aby byla setříděná. (10 bodů) Deadline: 1. 3.
  Budete-li odevzdávat e-mailem, nejvhodnější asi bude jednoduchý texťák.
  Quicksort, co bere za pivot vždy první buňku taky uznám (řekněme, že posloupnost je na začátku náhodně zpermutovaná).
  Může se hodit simulátor RAMu od Radka Huška. Jeho syntaxe se neshoduje s tou z přednášky, ale budu ji uznávat.
• Bonusový úkol 1: Uvažme RAM s neomezenou kapacitou buněk a s počítáním aritmetických operací v konstantním čase. Vymyslete, jak v tomto modelu násobit čtvercové matice \(n\times n\) v čase \(\mathcal{O}(n^2)\). (10 bodů) Deadline: 1. 3.
• DÚ 2: Řekneme, že (neorientovaný) graf je \(d\)-degenerovaný, pokud existuje pořadí odtrhávání vrcholů takové, že každý odtrhávaný vrchol má aktuální stupeň maximálně \(d\). Pro zadaný graf \(G\) najděte nejmenší \(d\) takové, že \(G\) je \(d\)-degenerovaný (jde to v lineárním čase, za pomalejší řešení dostanete část bodů). (10 bodů) Deadline: 8. 3.
• DÚ 3: Mějme zadána dvě bludiště, tj. čtverečkové sítě tvaru \(r\times s\), kde některé čtverečky představují „zdi“. V každém bludišti se na některém políčku nachází robot a oba roboti reagují na ovladač, kterým můžeme dávat povely pro posun o políčko nahoru, dolů, doleva a doprava. Na každý povel reagují oba roboti. Pokud má robot v udaném směru zeď, zůstane na místě (ale nezastaví tím druhého robota). Ve chvíli, kdy se robot dostane ven z bludiště (pohybem mimo krajní políčko), zastaví se a pozdější povely ignoruje. Vymyslete algoritmus, který najde nejkratší posloupnost povelů, která dostane oba roboty ven z bludiště. Časovou a paměťovou složitost vztahujte k rozměrům bludišť (tj. \(r\) a \(s\)). (10 bodů) Deadline: 15. 3.
• DÚ 4: Jak najít nejdelší cestu v orientovaném acyklickém grafu, když je dáno ohodnocení hran udávající jejich délku? (10 bodů) Deadline: 22. 3.
• DÚ 5: Silnice v mapě máme ohodnocené dvěma nezápornými čísly: délkou a mýtem (poplatkem za projetí). Jak najít nejlevnější z nejkratších cest mezi dvěma zadanými místy? (10 bodů) Deadline: 29. 3.
• DÚ 6: Posíláme po síti velké množství obrázků a chceme, aby to netrvalo dlouho. Každý obrázek má \(B\) bytů a můžeme ho buď poslat samostatně nezávisle na ostatních, nebo jako zakódovaný rozdíl oproti jinému, již přenesenému snímku. Rozdíly mezi snímky už máme předpočítané, takže pro \(i\)-tý a \(j\)-tý obrázek můžeme v konstantním čase najít \(D_{ij}\), velikost rozdílu mezi nimi v bytech.
  Navrhněte algoritmus, který najde pořadí a způsob (celý obrázek vs. diff s již odeslaným obrázkem) odesílání obrázků, abychom celkem odeslali co nejméně bytů dat. O hodnotách \(D_{ij}\) víme jen, že \(D_{ij} = D_{ji}~\forall i, j\). Hodnoty \(D_{ij}\) a \(D_{jk}\) nic neříkají o \(D_{ik}\). (10 bodů) Deadline: 5. 4.
• DÚ 7: Upravte BVS strom tak, aby dokázal odpovídat na dotaz, kolik uložených klíčů má hodnotu v zadaném rozsahu \([a, b]\). Chceme, aby všechny operace (včetně této) měly složitost \(\mathcal{O}(h)\), kde \(h\) je hloubka stromu. (10 bodů) Deadline: 12. 4.
• DÚ 8: Použijte vyhledávací stromy k návrhu datové struktury, která postupně dostává celá čísla a po každém novém číslu vrátí medián z posledních \(k\) hodnot. Tato operace, tj. vložení nového čísla a vrácení aktuálního mediánu, by měla trvat \(\mathcal{O}(\log k)\). Konstanta \(k\) je zadána před inicializací struktury. (10 bodů) Deadline: 19. 4.
• DÚ 9: Viděli jsme, jak hešovací tabulku postupně zvětšovat tak, že \(n\) operací stojí čas \(\mathcal{O}(n)\). Co když chceme taky zaručit, že když zrovna máme uložených \(k\) prvků, tabulka zabere jen \(\mathcal{O}(k)\) paměti? Navrhněte, jak toto zaručit postupným zmenšováním tabulky když počet prvků klesne pod nějakou úroveň. Posloupnost \(x\) insertů a \(y\) deletů v libovolném pořadí by měla zabrat čas \(\mathcal{O}(x+y)\). (10 bodů) Deadline: 26. 4.
• DÚ 10: Zlepší se časová efektivita binárního vyhledávání, pokud interval nebudeme půlit, ale dělit na třetiny? Snadno se rozmyslí, že asymptotická složitost zůstane \(\Theta(\log n)\), ale jak je to s konstantami? Spočtěte, jak efektivní takové "ternární″ vyhledávání je oproti binárnímu. (10 bodů) Deadline: 10. 5.
• Bonusový úkol 2: Aerolinka "Eastward″ létá pouze na východ. Města, mezi kterými létá, se dají jednoznačně seřadit od nejzápadnějšího po nejvýchodnější na \(m_1,\ldots,m_n\). Chceme, aby bylo možné z každého města \(m_i\) doletět do libovolného východnějšího města \(m_j\) \((i < j)\). Aby to šlo bez přestupu, potřebovali by Eastward provozovat \(\Omega(n^2)\) spojů. Můžeme taky mít spoje jen mezi městy \(m_i\) a \(m_{i+1}\), pak ale někteří pasážéři budou muset přestupovat \(\Omega(n)\)-krát, než se dostanou do cíle.
  Navrhněte proto \(\mathcal{O}(n \log n)\) spojů mířících pouze na východ, které zajistí, že žádný cestující nebude muset přestoupit víc než jednou. Eastward operuje na placaté Zeměploše, takže z města \(m_n\) se nedá dostat do města \(m_1\) letem na východ. (10 bodů) Deadline: 10. 5.
• Bonusový úkol 3.: V Praze je náledí a nefunguje MHD. Plán města máme zadán neorientovaným grafem a každé ulici máme přiřazenou pravděpodobnost (číslo mezi \(0\) a \(1\)), že tu uklouzneme. Vymyslete algoritmus, který najde cestu mezi dvěma křižovatkami minimalizující pravděpodobnost úrazu. (10 bodů) Deadline: 17. 5.
• Bonusový úkol 4.: Kamarád nám posílá zprávy bez mezer. Máme slovník českých slov nahraný v trii. Jak pro zprávu bez mezer zjistit, kolika validním zprávám s mezerami odpovídá? A jak navíc vypsat některou takovou zprávu o minimálním počtu slov? (10 bodů) Deadline: 31. 5.
• Bonusový úkol 5.: Najděte algoritmus na získání inverzu (dolní) trojúhelníkové matice \(n \times n\) v čase \(o(n^3)\). Můžete předpokládat, že \(n\) je mocninou dvojky.
  Tato úloha vyžaduje přípravu navíc. Hodí se znát Strassenův algoritmus na rychlé násobení matic. V Průvodci je algoritmus popsán v kapitole 10.5. (10 bodů) Deadline: 31. 5.

Bodové výsledky: Tabulka bodů

Užitečné odkazy

Stránka přednášky.

Knížka Průvodce labyrintem algoritmů, která pokrývá (nejen) celý sylabus předmětu.

Archiv úloh Korespondenčního semináře z programování.

Soutěžní programování: Codeforces, Spoj, HackerRank, CodeChef.

Zábavné kódící úlohy: Project Euler.