omhoog naar college.

Materiaal Datastructuren

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

Diktaat

Huidige versies lecture notes 12.11'24 (Enkele opgaven uitgewerkt) of kleine kantlijn 13.9'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)

Schema 2023

(Ik denk dat je voor de opgenomen colleges moet kunnen inloggen met ULCN. Helaas. Ik wijs veel naar de slides, en dat is nu net niet in beeld. Probleem: het beeld is af en toe kort zwart, dat heb ik doorgegeven aan de opnameleiding. Hinderlijk.)

week datum onderwerp slides opnames

- 30.11 oud tentamen maken
(jan 2017, zie beneden, gedeeltelijk uitgewerkt)
deelname heeft alleen nut als je in ieder geval even goed naar dat tentamen gekeken hebt. — —

- 7.12 college vervalt (!) — —

- 14.12 oud tentamen maken
(mrt 2023, in deze directory) — —

Alle-slides-tot-nu-toe staat als dat-present-23-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 (text) (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.