English students: Do not enroll the course Data Structures I in the winter semester since English version will be in the summer semester.
Datové struktury I
V zimním semestru 2024/25 vedu přednášku a cvičení k Datových strukturám I.Výuka
Přednáška se koná v každý čtvrtek od 15:40 v učebně S3 a moje cvičení jsou v úterý od 14:00 v S10 a v pátek od 9:00 v S8. Další cvičení vedou:- Pavel Veselý: středa, 9:00, S6
- Petr Chmel: pondělí, 9:00, S10 a pátek, 12:20, S1
Přednášky
- 3.10.: Úvod, amortizovaná složitost
- 10.10.: BB[alpha]-stromy, Splay stromy
- 17.10.: (a,b)-stromy
- 24.10.: Paměťová hierarchie
- 31.10.: LRU vs OPT strategie, úvod do hešování
- 7.11.: Výběr hešovací funkce
- 21.11.: Separované řetězce, další hešovací funkce
Zápočet
Zápočet bude udělen za vypracování domácích úkolů. Plánujeme 7 programovacích úkolů po 10 bodech a 3 experimentální po 15 bodech. K zápočtu je třeba získat 75 bodů. Zadaní a další podrobnosti najdete na následujících stránkách.- ReCodExu pro odevzdávání úkolů.
- Git k získávání materiálů k domácím úkolům.
- Pravidla a podmínky k získání zápočtu dle Martina Mareše
- Vzorové řešení experimentálního úkolu
Zkouška
Zkouška bude mít ústní formu s písemnou přípravou. Termíny a přihlašování jsou na SISu. Čas příchodu na zkoušku si zkontrolujte den před zkouškou, protože jej SIS mění podle aktuálního počtu přihlášených studentů. Každý student dostane náhodnou stránku z tohoto seznamu.Literatura
- M. Mareš: Lecture notes on data structures, 2019.
- M. Mareš, T. Valla: Průvodce labyrintem algoritmů, CZ.NIC, 2017.
- A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
- T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2009
- K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984
- D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman \& Hall/CRC, Computer and Information Series, 2005
- E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
- R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.
- M. Thorup: High Speed Hashing for Integers and Strings. Lecture notes, 2014.
- M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
Další zdroje
- Stránka Martina Mareše, kde najdete i videa jeho přednášek
- Stránka Michala Kouckého
- Stránka Petra Gregora: videa jeho přednášek jsou na stream UK
- Náplň cvičení a diskutované otázky budou podobné jako v loňském roce.
Vstupní předpoklady
- Znalost programovacího jazyka Python nebo C/C++ a vývojového prostředí vhodného k ladění programů v těchto jazycích
- Základní algoritmy a datové struktury
- Algoritmy a datové struktury 1
- Algoritmy a datové struktury 2 stačí vyhledávání textu
- Pravděpodobnost, stačí diskrétní, například
- Základní znalost fungování počítačů, například
Pokud trávíte hodně času hledáním chyb při ladění vlastních programů (a to nejenom v tomto předmětu), můžete v zimním semestru chodit na předmět Implementace datových struktur (NTIN106), jehož cílem je seznámit studenty s pokročilými technikami efektivní implementace datových struktur a algoritmů.