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.) – Dynamické programování, zadán DÚ11
- 12. cvičení (24. 5.) – Rozděl a panuj, rekurence a Kuchařková věta, zadán větší DÚ12
- 13. cvičení (31. 5.) – Rozděl a panuj, QuickSort, QuickSelect, nebyl zadán úkol
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 | 11 | 12 | ∑ | |||
| Don Knuth | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 12 | 14 | 14 | 20 | 163 | 163 | |
| Dvou-třetiňák | 5.5 | 8.75 | 7.5 | 6.75 | 13.5 | 8 | 9.5 | 10 | 8 | 9.5 | 9.5 | 13.5 | 110 | 110 | |
| OA | 12.25 | 8 | 8 | 11 | 6.5 | 17 | 12 | 12.5 | 15 | 90 | 102.25 | ||||
| Vladav | 16 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 103 | 119 | ||||
| Kinaj | 12 | 8 | 13 | 11 | 9.5 | 20 | 12 | 14 | 15 | 102.5 | 114.5 | ||||
| Sorx | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 103 | 103 | |||||
| Curly Bracket | 16 | 5.5 | 13 | 11 | 7 | 20 | 12 | 14 | 15 | 7 | 14 | 13.5 | 132 | 148 | |
| spidero | 1.25 | 8 | 13 | 11 | 10 | 14.5 | 12 | 14 | 14.75 | 12 | 109.25 | 110.5 | |||
| pata Leonarda Bluma | 8 | 8 | 12.5 | 11 | 9 | 20 | 12 | 14 | 15 | 8 | 109.5 | 117.5 | |||
| KOON | 26 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 12 | 4 | 104 | 130 | |||
| Matezzzz | 13.5 | 8 | 11 | 11 | 10 | 20 | 12 | 14 | 15 | 6 | 14 | 121 | 134.5 | ||
| Saudade | 0.25 | 8 | 13 | 6 | 7.5 | 20 | 11 | 14 | 15 | 12 | 12 | 2 | 120.5 | 120.75 | |
| Valkyrie | 0.5 | 8 | 12.5 | 11 | 6 | 20 | 12 | 14 | 15 | 12 | 14 | 124.5 | 125 | ||
| Kimrli | 7 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 12 | 11 | 126 | 133 | ||
| Hubacm | 3 | 6.25 | 3 | 5.5 | 4 | 18 | 2 | 13.5 | 15 | 6 | 13 | 9 | 95.25 | 98.25 | |
| PipJau | 1.5 | 8 | 13 | 11 | 10 | 17.5 | 12 | 13 | 15 | 12 | 111.5 | 113 | |||
| perla v moři | 8 | 13 | 5.5 | 12 | 38.5 | 38.5 | |||||||||
| Moto Moto | 1 | 8 | 10.5 | 10.5 | 9 | 18.5 | 12 | 14 | 12 | 94.5 | 95.5 | ||||
| Mikiem | 4 | 8 | 13 | 11 | 10 | 20 | 12 | 14 | 15 | 12 | 14 | 11 | 140 | 144 | |
| Flâneur | 5.5 | 4.5 | 7 | 3 | 20 | 20 | |||||||||
| Liak | 4 | 8 | 9 | 10 | 8.75 | 19 | 12 | 13 | 15 | 8 | 102.75 | 106.75 | |||
| Nika | 8 | 8.5 | 7 | 2 | 11.5 | 6.5 | 12.5 | 15 | 6 | 9 | 86 | 86 | |||
| Alka | 8 | 2.5 | 4.5 | 14 | 12 | 11 | 15 | 1 | 68 | 68 | |||||
| Gagata | 7.5 | 3.5 | 11 | 11 | |||||||||||
| moonie | 2.5 | 5.5 | 7 | 0.5 | 4 | 6 | 1 | 14 | 7 | 4 | 2 | 8 | 59 | 61.5 | |
| Mysak | 10 | 8 | 11.5 | 10 | 20 | 14 | 63.5 | 73.5 | |||||||
| Frodo | 2 | 13 | 11 | 9.5 | 20 | 12 | 13 | 15 | 11.5 | 105 | 107 | ||||
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í ;)