Cvičení z datových struktur 1 (NTIN066)

Jak získat zápočet

• K zisku zápočtu je nutné získat alespoň 90 bodů z domácích úkolů.
• Bude zadáno alespoň 12 úkolů, dohromady za alespoň 140 bodů.
• Je nutné dodržovat pravidla
• Přečtěte si pravidla velice pečlivě a zeptejte se cvičícího, pokud něco není jasné! Neznalost neomlouvá.

Průběh cvičení

• Cvičení budou probíhat prezenčně na Malé Straně, v učebně S7.
• Cvičení probíhají distančně přes Zoom. Přihlašovací údaje přišly mailem, pokud vám nedorazily, napište.
• V případě, že dojde k přechodu na distanční výuku (dej Ódin ať ne), budeme téměř jistě používat Zoom. Podrobnější instrukce přijdou e-mailem, pokud mě Ódin nevyslyší.
• Pro fyzickou účast na cvičeních je nutné doložit bezinfekčnost! Detaily na samostatné stránce
• Pokud se cítíte nemocní, nebo jste byli v kontaktu s někým pozitivním na covid, zůstaňte doma! To platí i pokud jste očkovaní a nemusíte do karantény, i s očkováním je netriviální riziko, že jste se nakazili.
• Přítomnost na cvičení není povinná, jen doporučená. Je dobré zavítat alespoň na první cvičení, kde se řeší technické detaily a pravidla (byť všechny důležité informace najdete zde, či skrze mail cvičícímu).
• Na cvičení se ukazuje řešení právě expirovaného domácího úkolu, vzorové řešení je pak k dispozici v ReCodExu.
• Hlavní částí cvičení jsou dotazy a spol. Typicky řešíme nejasnosti kolem věcí z přednášky a úkolů.
• Taktéž budou k dispozici příklady k procvičení látky z přednášky. Ty nijak neovlivňují to, zda získáte zápočet — snad jen tím, že by vám měly pomoct lépe pochopit látku.

Nebojte se ptát (v nejhoším případě se prostě nic nedozvíte :-)).

Cvičení

29. 9.: Nekoná se, ještě nebude přednáška.
6. 10. : Úvodní info, úvod do amortizace (i když tomu zatím amortizace neříkáme :-))
13. 10. : Úvod do splay stromů a další hrátky s amortizací.
20. 10. : Splay stromy podrobněji. Může se hodit vizualizace.
27. 10. : (a,b)-stromy. Cvičení je samostudium + konzultace skrz zoom, přihlašovací údaje byly poslány mailem, pokud nedorazily, napište.
3. 11. : ještě (a,b)-stromy.
10. 11. : Keše.
17. 11.: Nekoná se, máme svátek.
24. 11. : Hešování s úplně náhodnými funkcemi.
1. 12. : Univerzality a nezávislosti.
8. 12. : Pro veliký úspěch pokračujeme v hešování. Můžou se též hodit poznámky z léta a záznam k nim.
15. 12. : Suffixová pole a RMQ. K bloom filtrům z přednášky se můžou též hodit poznámky z léta a záznam k nim.
22. 12. : Užíváme si Vánoce. Cvičení není, jen zadáme nový úkol.
5. 1. : Resty z předvánoci a geometrie.

Domácí úkoly

• Obecné informace naleznete v pravidlech.
• Úkoly se odevzdávají přes ReCodEx (i experimentální).
• Prosím přidejte se do příslušné ReCodExové skupiny.
• Zpětná vazba k řešení bude též v ReCodExu. Může být užitečné nastavit si e-mailové notifikace.
• Materiály k úkolům (zdrojové kódy) naleznete v gitovém repozitáři.

Pár doporučení:

• Choďte na přednášku, nebo si alespoň odpovídající látku projděte ze zdrojů, obzvláště užitečná jsou skriptíčka Martina Mareše, která k tomuto předmětu vznikla. Nepředpokládáme, že nutně pochopíte hned všechno z přednášky, ale měli byste alespoň tušit, co se dělalo.
• Začněte včas. Noční programovací maratony sice mají své kouzlo, ale ve tři ráno vám cvičící dotazy opravdu nezodpoví a programování pod vlivem spánkového deficitu a litrů kofeinu se obvykle špatně podepíše na kvalitě a funkčnosti kódu.
• Pořádně si přečtete zadání a před samotným programováním si problém pořádně rozmyslete na papíře. Rozumíte tomu, jak daná datová struktura vlastně funguje? A co okrajové případy?
• Pište kód slušně. Cvičící si totiž váš kód přečte a za čuňárny vám může strhnout body (a naopak přidat, pokud bude vaše řešení obzvláště pěkné). A navíc vám to může ušetřit čas při chytání chyb. Při posuzování hezkosti svého kódu se můžete inspirovat dodanou šablonou. Mimochodem, není nutně pravda, že kvalita kódu roste s tím, jak je kód ukecaný.
• Testujte! Měníte v průběhu datovou strukturu? Což takhle přidat pár podmínek či assertů, které vám při testování zkontrolují invarianty? Rozpadá se vám halda pod rukama? Což takhle si jí nechat vykreslit třeba DOTem?
• Nepřehánějte to s optimalizacemi. Časové i paměťové limity by měly být přiměřeně štědré, takže dokud má vaše řešení správnou asymptotickou složitost a neděláte zvěrstva, mělo by projít. Ze zkušenosti je lepší mít hezky napsaný program, který tu a tam udělá nějakou drobnou zbytečnost, než super optimalizované špagety, které po sobě druhý den ani nepřečtete.

Když to nejde můžete zkusit:

• zeptat se cvičícího
• pozitivní přístup
• destruktivní přístup
• motlidbu k Ódinovi, bohu moudrosti
• jít radši kácet stromy

Jazykové okénko

Implementační úkoly je možno odevzdávat buď v Pythonu 3 nebo v C++17, přesnější parametry jako kompilátor C++ najdete v ReCodExu. Pokud neumíte C++ ale C ano, pak nezoufejte, stejně je velmi doporučeno psát v C++ jako by to bylo staré dobré C a drtivou většinu vlastností, které má C++ navíc můžete tedy ignorovat.

Pokud ani jeden z jazyků neumíte, níže jsou odkazy na některé tutoriály a jiné užitečné informace. A samozřejmě, cvičící a strýček Google jsou kamarádi.

Pokud si nejste jistí, který z jazyků použít, já osobně bych doporučil Python, neb se mi mnohem lépe čte a přijde mi celkově přívětivější a možná i trochu užitečnější. Každopádně ale můžu doporučit si vybrat ten z jazyků, kterým se vám čte a píše lépe.

Python

• Dokumetace a různé zdroje
• Seznam tutoriálů
• PyCharm: IDE pro Python (pokud vám nestačí textový editor)

C++

• Dokumetace a různé zdroje
• Jeden tutoriál a druhý tutoriál
• QtCreator: IDE pro C++ (některé linuxové distribuce ho mají jako balíček v repozitářích)