Cvičení z Algoritmů a datových struktur 1

Pondělí 10:40

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ívkaBonusDomácí úkolyCelkem
123456789101112
Don Knuth81311102012141512141420163163
Dvou-třetiňák5.58.757.56.7513.589.51089.59.513.5110110
OA12.2588116.5171212.51590102.25
Vladav16813111020121415103119
Kinaj12813119.520121415102.5114.5
Sorx813111020121415103103
Curly Bracket165.5131172012141571413.5132148
spidero1.25813111014.5121414.7512109.25110.5
pata Leonarda Bluma8812.5119201214158109.5117.5
KOON268131110201214124104130
Matezzzz13.5811111020121415614121134.5
Saudade0.2581367.52011141512122120.5120.75
Valkyrie0.5812.5116201214151214124.5125
Kimrli78131110201214151211126133
Hubacm5.56.2535.5418213.515613995.25100.75
PipJau1.5813111017.512131512111.5113
perla v moři8135.51212757.557.5
Moto Moto1810.510.5918.51214127.5102103
Mikiem4813111020121415121411140144
Flâneur5.54.5732020
Liak489108.75191213158102.75106.75
Nika888.57211.56.512.51569793101
Alka82.54.51412111511248484
Gagata7.53.51111
moonie2.55.570.54611415881414.597.5100
Mysak10811.510201463.573.5
Frodo213119.52012131511.5105107

Užitečné odkazy