omhoog naar college.

Materiaal Datastructuren

Beschikbaar materiaal: (1) Slides+Video, (2) Diktaat (aka Lecture Notes), (3) Oude tentamens.

Status 2021: Aan de lecture notes zal ik af en toe wat verbeteren. (Input welkom.) (Dank aan alle vragenstellers voor de suggesties.) Video opnamen zijn van vorig jaar.

Diktaat

Huidige versie lecture notes · 27.11'21 (Ch10. Uitleg Aho-Corasick.) 16.11'21 (Ch9. Plaatje voorbeeld ZLW.) 08.11'21 (Example 4.6. Extra boom waarin na toevoegen meerdere nivo's uit balans.) 03.11'21 (Ch.5 voorbeeld deleteMin interval heap toegevoegd.) (Typo's) 29.10'21 (Ch.7 uitleg, plaatjes.) 21.10'21 (Ch.5 proloog over key-value ordening toegevoegd, inclusief plaatjes bij slides.) (Pairing Heap ☒) · 13.10'21 (diagram heapsort uit slides in dictaat overgenomen) · 12.10'21 (Ch.5 makeheap complexity uitgeschreven) · 30.9'21 (Ch.4 plaatjes uit slides ook naar notes) (voorbeelden deletion by merging/copying) · 28.9'21 (update postorder traversal with stack)
Originele versie bij begin semester lecture notes 13.9'20.

Schema 2021

De gelinkte opnames zouden door iedereen ook zonder account bekeken moeten kunnen worden.
De originale set slides heeft rare 'witte' bladzijdes. Ik voeg de slides opnieuw toe, met ook wat overige wijzigingen tov de filmpjes (uit 2020). Dat doe ik bijvoorbeeld als er nieuwe/verbeterde plaatjes zijn.
week datum college (video) slides (2021)
0 8.9 0. Introductie.
0. Welkom! wordt vernieuwd.
Intro 8.9'21
1 15.9 1. Basic data structures.
1.1. Abstract Data Types 1.2. C++ 1.3. Bomen
Ch.1
2 22.9 2. Tree traversal.
2.1. Recursief 2.2. Met stapel 2.3. Zonder
Ch.2
3 29.9 3. BST: Binaire zoekbomen.
3.1. Als ADT Set 3.2. Statistieken
Ch.3
- 6.10 docent afwezig
4 13.10 4. Gebalanceerde zoekbomen.
4.1. AVL-boom, definitie 4.2. toevoegen (en verwijderen) 4.3. splay trees (zelf-organiserend)
Ch.4
5 20.10 5. Priority queue.
5.1. ADT priority queue 5.2. binary heap 5.3. leftist heap
Ch.5
- 27.10 toetsweek
6 3.11 6. B-bomen.
6.1. B-bomen 6.2. rood-zwart bomen
Ch.6
7 10.11 7. Grafen.
7.1. Representatie, DFS, BFS 7.2. MST: Kruskal, Prim; Union-Find 7.3. Kortste paden: Dijkstra, Floyd-Warshall
Ch.7
8 17.11 8. Hash-tabellen.
8.1. Introductie, perfect hashen 8.2. Open adressering 8.3. Chained hashing, hash-functies
Ch.8
9 24.11 9. Data-compressie.
9.1. Introductie, vergelijking methodes 9.2. Huffman 9.3. Ziv-Lempel-Welch
Ch.9 *
10 1.12 10. Patroonherkenning.
10.1. Knuth-Morris-Pratt en Aho-Corasick 10.2. failure links
Ch.10 *
- 8.12 oud tentamen maken
(januari 2020, zie beneden, met uitwerking)
deelname heeft alleen nut als je in ieder geval even goed naar dat tentamen gekeken hebt.
- 15.12 oud tentamen maken
(maart 2021, zie beneden, zonder uitwerking)

Oude tentamens

En de oertijd, met nog wat zelfwerkzaamheid.

Inhoud, aan de hand van het Aanbevolen Boek (2014)

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.