Cvičení z Algoritmů a datových struktur 1
V letním semestru 2020/2021 vedu cvičení pro bioinformatiky z předmětu Algoritmy a datové struktury 1 [NTIN060] k přednáškám Martina Mareše každé pondělí od 10:40 (v N6 dá-li situace, jinak online).
Počítejte s možností, že se cvičení při lepší situaci může přepnout do prezenční formy!
Na cvičení budeme používat Zoom, odkaz dostanete emailem na adresu, kterou máte nastavenou v SISu týden před začátkem semestru. Pokud odkaz nemáte, napište mi email!
Máte-li nějaký dotaz, či chcete-li si domluvit konzultaci, napište mi prosím email na adresu jiribenes+ads@kam.mff.cuni.cz.
Podmínky zápočtu
Na cvičení půjde získat body z domácích úkolů a za aktivitu. Celkem bude možné získat určitě alespoň 160 bodů, přičemž k zápočtu je potřeba alespoň 100 bodů.
Domácí úkoly
Na konci každého cvičení budou zadány domácí úkoly, celkem za alespoň 160 bodů (ale ne o moc víc). Každý úkol lze řešit dva týdny od cvičení, na kterém byl úkol zadán. Pokud úkol odevzdáte brzy a bude v něm něco špatně, vrátím vám jej na opravu.
Domácí úkoly můžete řešit společně s ostatními účastníky cvičení (dokonce to doporučuji), ale řešení musíte zformulovat a sepsat každý zvlášť.
Nezapomeňte pečlivě zdůvodnit všechny kroky, je to důležitější než správný výsledek. Věty a tvrzení z přednášek či cvičení můžete použít bez důkazu, jen vždy uveďte, co používáte! Více tipů jak řešit a sepisovat úkoly má Vašek Končický zde.
Řešení domácích úkolů mi posílejte emailem na adresu jiribenes+ads@kam.mff.cuni.cz. Preferuji řešení ve formátu PDF, či jako text v těle emailu. Pokud budete posílat ručně psané poznámky, zajistěte prosím, aby byly v dostatečné kvalitě (použijte například aplikaci Notebloc, či aplikaci Tiny Scanner, obojí je pro Android i pro iOS) a aby byly v jednom PDF souboru.
K prvnímu úkolu mi napište i přezdívku (zapsatelnou Unicodem), abych mohl na stránce zveřejnit počet získaných bodů.
Vzorové řešení úkolu v LaTeXu (nově nyní i s hezkým pseudokódem) najdete zde zazipované. Upravit jej můžete například na stránce Overleaf (vyžaduje bezplatnou registraci) – stačí zvolit vpravo nahoře New Project, poté Upload Project a vybrat zazipované vzorové řešení. Alternativně můžete vyzkoušet službu hackmd.io, ve které se dá psát normální Markdown s občasnými kusy LaTeXových vzorců.
Bonusové body
Za aktivitu a bonusové úkoly půjdou získat bonusové body, které se přičítají k bodům z úkolů.
Co se dělalo na cvičení
- 1. cvičení (1. 3.) – Úvodní informace, motivační příklady, zadán DÚ1
- 2. cvičení (8. 3.) – Asymptotická notace, RAM, zadán DÚ2
- 3. cvičení (15. 3.) – Pokračování RAMu, absurdita jednoduchého cenového modelu, zadán DÚ3
- 4. cvičení (22. 3.) – Prohledávání do hloubky, klasifikace hran, zadán DÚ4
- 5. cvičení (29. 3.) – Hledání artikulací, prohledávání do šířky, zadán větší DÚ5
- Dne 5. 4. cvičení odpadlo (Velikonoční pondělí), nebyl zadán úkol
- 6. cvičení (12. 4.) – Relaxační algoritmy, hledání nejkratších cest, zadán DÚ6
- 7. cvičení (19. 4.) – Minimální kostry, zadán DÚ7
- 8. cvičení (26. 4.) – Binární vyhledávací stromy, zadán DÚ8
- 9. cvičení (3. 5.) – AVL stromy, (a, b)-stromy, intervalové dotazy, zadán DÚ9
- 10. cvičení (10. 5.) – Trie, amortizace, hashování, zadán DÚ10
- 11. cvičení (17. 5.) – Plán: Rozděl a panuj, Kuchařková věta, bude zadán DÚ11
Tabulka s body
Pokud nejste v tabulce, nemám vaši přezdívku.| Přezdívka | Bonus | Domácí úkoly | Celkem | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ∑ | |||
| Don Knuth | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 12 | 14 | 129 | 129 | |
| Dvou-třetiňák | 5.5 | 8.75 | 7.5 | 6.75 | 13.5 | 8 | 9.5 | 10 | 69.5 | 69.5 | |||
| OA | 7.5 | 8 | 8 | 11 | 6.5 | 17 | 12 | 12.5 | 15 | 90 | 97.5 | ||
| Vladav | 11 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 88 | 99 | |||
| Kinaj | 9 | 8 | 13 | 11 | 9.5 | 20 | 12 | 14 | 87.5 | 96.5 | |||
| Sorx | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 103 | 103 | |||
| Curly Bracket | 8 | 5.5 | 13 | 11 | 7 | 20 | 12 | 14 | 82.5 | 90.5 | |||
| spidero | 1.25 | 8 | 13 | 11 | 10 | 14.5 | 12 | 14 | 14.75 | 12 | 109.25 | 110.5 | |
| pata Leonarda Bluma | 4.75 | 8 | 12.5 | 11 | 9 | 20 | 12 | 14 | 86.5 | 91.25 | |||
| KOON | 19 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 88 | 107 | |||
| Matezzzz | 11 | 8 | 11 | 11 | 10 | 20 | 12 | 14 | 86 | 97 | |||
| Saudade | 0.25 | 8 | 13 | 6 | 7.5 | 20 | 11 | 14 | 79.5 | 79.75 | |||
| Valkyrie | 0.5 | 8 | 12.5 | 11 | 6 | 20 | 12 | 14 | 83.5 | 84 | |||
| Kimrli | 2 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 88 | 90 | |||
| Hubacm | 3 | 6.25 | 3 | 5.5 | 4 | 18 | 2 | 13.5 | 52.25 | 55.25 | |||
| PipJau | 1.5 | 8 | 13 | 11 | 10 | 17.5 | 12 | 13 | 84.5 | 86 | |||
| perla v moři | 8 | 13 | 5.5 | 26.5 | 26.5 | ||||||||
| Moto Moto | 0.75 | 8 | 10.5 | 10.5 | 9 | 18.5 | 12 | 9 | 77.5 | 78.25 | |||
| Mikiem | 2.75 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 12 | 100 | 102.75 | ||
| Flâneur | 5.5 | 4.5 | 7 | 3 | 20 | 20 | |||||||
| Liak | 1 | 8 | 9 | 10 | 8.75 | 19 | 12 | 13 | 79.75 | 80.75 | |||
| Nika | 8 | 8.5 | 7 | 2 | 11.5 | 6.5 | 43.5 | 43.5 | |||||
| Alka | 8 | 2.5 | 4.5 | 14 | 12 | 11 | 15 | 67 | 67 | ||||
| Gagata | 7.5 | 3.5 | 11 | 11 | |||||||||
| moonie | 2.5 | 5.5 | 7 | 0.5 | 4 | 6 | 1 | 24 | 26.5 | ||||
| Mysak | 7 | 8 | 11.5 | 10 | 29.5 | 36.5 | |||||||
| Frodo | 2 | 13 | 11 | 9.5 | 20 | 12 | 65.5 | 67.5 | |||||
Užitečné odkazy
- Předmět pro zvídavé studenty 1. ročníku: IPS
- Kombinatorický seminář je referativní seminář z kombinatoriky a příbuzných oborů, kde si můžete vyzkoušet přečíst a poreferovat aktuální vědecký výzkum
- Kniha Průvodce labyrintem algoritmů bohatě popisuje látku probíranou na ADS 1 a ADS 2
- Staré videozáznamy přednášek – vyžaduje přihlášení (login jako do SISu)
- Kuchařky Korespondenčního semináře z programování obsahují méně formální popisy algoritmů a datových struktur
- Kniha Competitive Programmer’s Handbook je hezký úvod do technik používaných při soutěžním programování. Má hodně obrázků, hezké popisy algoritmů a funkční kód v jazyce C++.
- Pokud se chcete procvičit v řešení algoritmických problémů, podívejte se na archiv soutěže Kasiopea nebo na archiv Korespondenčního semináře z programování
- Jak nastavit Zoom Virtual Background, abyste vypadali cool při cvičení ;)