omhoog naar college.

Materiaal Datastructuren

Beschikbaar materiaal: (1) Diktaat (aka Handout), (2) Slides, (3) Oude tentamens, (4) Opgenomen colleges (vorig jaar), (5) het Boek, en (6) eventueel Video uit 2020.

Diktaat

Huidige versies lecture notes 2.12'24 (Enkele opgaven uitgewerkt) of kleine kantlijn 3.12'24.

(Bedankt voor de ingestuurde correcties. Dank aan alle vragenstellers op college voor de suggesties!)

Schema 2024

week	datum	onderwerp	slides	opnames
1	4.9	0. Introductie. 0. Welkom!	Intro
		1. Basic data structures. Abstracte datastructuren ADT, Standard template library STL, bomen.	Ch.1	weblecture
2	11.9	2. Tree traversal. Recursief, Euler, stapel, link-inversie, draden. Draden in het volgende college. Linkomkering vervalt.	Ch.2	weblecture (2023)
3	18.9	3. BST: Binaire zoekbomen. Als ADT Set, deletion, augmented trees, statistieken.	Ch.3	(2023)
4	25.9	4. Gebalanceerde zoekbomen. AVL-boom, rotaties, toevoegen (en verwijderen) splay trees(zelf-organiserend).	Ch.4	(2023)
5	2.10	5. Priority queue. ADT priority queue, binary heap, leftist heap.	Ch.5 ☒	(2023)
-	9.10	docent afwezig werkcollege gaat door! BW0.39	—
6	16.10	6. B-bomen. B-bomen, rood-zwart bomen.	Ch.6	(2023)
-	23.10	toetsweek!	—
7	30.10	Restjes. Augmented. Double ended PQ's. Splay trees. Rood-zwart.
8	6.11	7. Grafen. Representatie, DFS, BFS; MST: Kruskal, Prim; Union-Find; Kortste paden: Dijkstra, ...	Ch.7	(2023)
9	13.11	Floyd-Warshall. 8. Hash-tabellen. Perfect hashen; Open adressering; Chained hashing, hash-functies.	Ch.8	(2023)
10	20.11	9. Data-compressie. Huffman; Ziv-Lempel-Welch.	Ch.9 *	(2023)
11	27.11	10. Patroonherkenning. Knuth-Morris-Pratt, Failure links.	Ch.10 *	(2023)
-	4.12	oud tentamen maken Gorlaeus DM 1.09 (jan 2019, zie beneden, zonder uitwerking) deelname heeft alleen nut als je in ieder geval even goed naar dat tentamen gekeken hebt.	—	—
-	11.12	oud tentamen maken Gorlaeus BW 0.07 (jan 2022, zie beneden) alleen toegang na bestudering van het tentamen	—	—

Alle-slides-tot-nu-toe staan als dat-present-24-all.pdf in de directory.

Oude tentamens

Met "index" op onderwerpen: om te gebruiken als je gericht wilt oefenen.

apr 2024 (abstract/augmented/splay; AVL; heap,heapsort; lineair hashen)
jan 2024 (wandelen zonder/met draden; rood-zwart; heap,heapsort; KMP)
jan 2023 met uitwerking (tekst) (wandelen met draden; rood-zwart; priority queues; Huffman)
mrt 2022 (Diversen, AVL, heap, ZLW) Uitwerking AVL-som.
jan 2022 met uitwerking (Scan. Bedankt D.) (boomwandelen; leftist tree; topologische ordening; KMP)
mrt 2021 met bespreking (boomwandelen; B-boom; binary heap; hashen)
jan 2021 met uitwerking (scan. Bedankt.) (wandelen met draden; AVL; leftist; KMP)
jan 2020 met uitwerking (gebruik&efficientie; draden; binary heap; Floyd-Warshall; KMP)
jan 2019 (abstract, draden, AVL, union-find & Kruskal, ZLW) Jonathan bedankt!
mrt 2018 (abstract, B-boom, leftist, Floyd, hashen)
jan 2018 met uitwerking (bzb&Morris, AVL, interval heap, Huffman, Floyd) Stijn bedankt!
mrt 2017 met tips (abstract/priority queue, bedrade bomen, AVL, Floyd-Warshall, hashen, Huffman)
jan 2017 met tips 6) ZLW (abstract, boomwandel, leftist, rood-zwart, kortste paden, ZLW)
mrt 2016 met uitwerking (bzb, B-boom, topologisch sorteren, KMP)
jan 2016 met uitwerking (abstract, AVL, topologisch sorteren, Huffman)
mrt 2015 met uitwerking (abstract, rood-zwart, hashen, Knuth-Morris-Pratt).
jan 2015 met uitwerking (abstract, symmetrisch, AVL, hashen)

Video (oud)

De gelinkte opnames zijn van een aantal jaar terug, opgenomen op zolder, van tijdens de eerste corona-sluiting. Die zijn wat korter en dus meer to the point. Wellicht verouderd.

1.1. Abstract Data Types 1.2. C++ 1.3. Bomen

2.1. Recursief 2.2. Met stapel 2.3. Zonder

3.1. Als ADT Set 3.2. Statistieken

4.1. AVL-boom, definitie 4.2. toevoegen (en verwijderen) 4.3. splay trees (zelf-organiserend)

5.1. ADT priority queue 5.2. binary heap 5.3. leftist heap

6.1. B-bomen 6.2. rood-zwart bomen

7.1. Representatie, DFS, BFS 7.2. MST: Kruskal, Prim; Union-Find 7.3. Kortste paden: Dijkstra, Floyd-Warshall

8.1. Introductie, perfect hashen 8.2. Open adressering 8.3. Chained hashing, hash-functies

9.1. Introductie, vergelijking 9.2. Huffman 9.3. Ziv-Lempel-Welch

10.1. Knuth-Morris-Pratt en Aho-Corasick 10.2. failure links

Ik stel geen expliciete vragen over de preciese definities in C++. Dat is onderdeel van het practicum.

Demo

Data Structure Visualizations, via David Galles, University of San Francisco.