Algoritmen en Datastructuren II

• Prof. Dr. Wolfgang De Meuter

• in Dutch (Bachelor Level)

De studenten dienen voldoende vaardigheid in de programmeertaal Scheme te hebben (Structuur van Computerprogramma’s 1) en dienen een goede kennis te hebben over basisalgoritmen en -datastructuren (Algoritmen en Datastructuren 1).

Het thema van het vak is “circulariteit in datastructuren” en het effect hiervan op algoritmiek. De nummering van de hoofdstukken loopt verder na Algoritmen en Datastructuren 1.

• Hoofdstuk 12 Het union-find probleem, up-tree implementatie, path-compressie, geamortisseerde analyse (boekhoudersmethode, potentiaalmethode, aggregatiemethode).

• Hoofdstuk 13 Grafen: definities en voorstelling in het geheugen.

• Hoofdstuk 14 Graaftraversals: Depth-first traversal, Breadth-first traversal, Edge-labeling (tree-edges, back-edges, down-edges, cross-edges), Karakterisatie van DFT en BFT.

• Hoofdstuk 15 Ongerichte grafen: Eenvoudige algoritmen, samenhangendheid, boogsamenhangendheid, biconnectiviteit (algoritme van Hopcroft&Tarjan), Minimale spanningsbossen (Prim-Jarnik, Kruskal, Boruvka).

• Hoofdstuk 16 Manueel Geheugenbeheer: Freelists, Best-fitt algoritme, Handles, buddy allocators (exponential buddy allocators, Fibonacci buddy allocators).

• Hoofdstuk 17 Automatisch Geheugenbeheer: Stop-and-copy for pairs, stop-and-copy for vectors, Mark and Sweep for pairs, Mark and Sweep for vectors, Deutsch-Shorr-Waite algorithm for pairs and vectors.

Voor de hoofdstukken 12 tot en met 15 bestaat geschreven cursustekst. Transparanten evenals de code van alle besproken systemen worden ter beschikking gesteld aan de studenten. Tijdens de les zal er voor elk hoofdstuk naar afzonderlijke literatuur verwezen worden uit volgende referentiewerken:

• Introduction to Algorithms van Cormen, Leiserson, Rivest en Stein, MIT Press, 2nd edition.
• Database System Implementation van Garcia-Molina , Ullman en Widom, Prentice Hall.
• Garbage Collection: Algorithms for Automatic Dynamic Memory Management van Jones en Lins, Wiley.

Het examen bestaat uit een schriftelijk en een modeling gedeelte. Tijdens het schriftelijke gedeelte wordt de student beoordeeld op het praktische luik: het toepassen van de kennis in concrete situaties en het bouwen van variaties op de geziene algoritmen en datastructuren. Het mondelinge gedeelte beoogt een toetsing van de theoretische kennis van de student.