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 versie lecture notes 26.11'23 (Experimenteel: kleine kantlijn 22.1'24)

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

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
1 7.9 0. Introductie.
0. Welkom! 		Intro
1. Basic data structures.
Abstracte datastructuren ADT, Standard template library STL, bomen. 		Ch.1 (mislukt)
2 14.9 2. Tree traversal.
Recursief, Euler, stapel, link-inversie, draden. 		Ch.2 weblecture
3 21.9 3. BST: Binaire zoekbomen.
Als ADT Set, deletion, augmented trees, statistieken. 		Ch.3 weblecture
4 28.9 4. Gebalanceerde zoekbomen.
AVL-boom, rotaties, toevoegen (en verwijderen) splay trees(zelf-organiserend). 		Ch.4 weblecture
5 5.10 5. Priority queue.
ADT priority queue, binary heap, leftist heap. 		Ch.5 weblecture
- 12.10 docent afwezig —
6 19.10 6. B-bomen.
B-bomen, rood-zwart bomen. 		Ch.6 weblecture
- 26.10 toetsweek! —
7 2.11 7. Grafen.
Representatie, DFS, BFS; MST: Kruskal, Prim; Union-Find; Kortste paden: Dijkstra, ... 		Ch.7 weblecture
8 9.11 Floyd-Warshall.
8. Hash-tabellen.
Perfect hashen; Open adressering; Chained hashing, hash-functies. 		Ch.8 weblecture
9 16.11 9. Data-compressie.
Huffman; Ziv-Lempel-Welch. 		Ch.9 * weblecture
10 23.11 10. Patroonherkenning.
Knuth-Morris-Pratt, Failure links. 		Ch.10
*		 weblecture
- 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.

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.