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.)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ívkaBonusDomácí úkolyCelkem
12345678910
Don Knuth8131110201214151214129129
Dvou-třetiňák5.58.757.56.7513.589.51069.569.5
OA7.588116.5171212.5159097.5
Vladav1181311102012148899
Kinaj9813119.520121487.596.5
Sorx813111020121415103103
Curly Bracket85.51311720121482.590.5
spidero1.25813111014.5121414.7512109.25110.5
pata Leonarda Bluma4.75812.511920121486.591.25
KOON19813111020121488107
Matezzzz1181111102012148697
Saudade0.2581367.520111479.579.75
Valkyrie0.5812.511620121483.584
Kimrli281311102012148890
Hubacm36.2535.5418213.552.2555.25
PipJau1.5813111017.5121384.586
perla v moři8135.526.526.5
Moto Moto0.75810.510.5918.512977.578.25
Mikiem2.75813111020121412100102.75
Flâneur5.54.5732020
Liak189108.7519121379.7580.75
Nika88.57211.56.543.543.5
Alka82.54.5141211156767
Gagata7.53.51111
moonie2.55.570.54612426.5
Mysak7811.51029.536.5
Frodo213119.5201265.567.5

Užitečné odkazy