Toegangseisen
Dit college is een vervolg op het college Algoritmiek. Daarom wordt begrip van de relevante stof uit dat vak aangenomen.
Beschrijving
Algoritmen en datastructuren vormen een onafscheidbaar stel. Enerzijds zijn goed ontworpen datastrcuturen essentieel om efficent algoritmische problemen op te lossen. Zo gebruiken we Adjacency lists en Priority queues om het algoritme van Dijkstra voor kortste paden op te lossen. Anderzijds worden bij niet-triviale datastructuren slimme algoritmes gebruikt om de structuur aan te passen wanneer er gegevens worden toegevoegd of verwijderd.
Bij het gebruik en implementatie maken we onderscheid tussen abstracte datastructuren en de concrete implementaties daarvan. De basis structuur Stack (of Stapel) met operaties Pop en Push kan bijvoorbeeld geimplementeerd worden ofwel met behulp van een array ofwel als gelinkte lijst.
In dit college zullen we de standaard datastructuren zoals stapels (stacks), rijen (queues), lijsten (lists), binaire en multiway bomen, priority queues, en grafen de revue laten passeren. Elk van deze gegevensstructuren kun je karakteriseren vanwege hun (interne) structuur en hun methoden (tests op, en wijzigen van, de opgeslagen gegevens). We schetsen mogelijke implementaties van de abstracte structuren, en bekijken de consequenties voor de efficientie van de operaties.
Onderwerpen: Basic data structures (ADT, lineaire lijsten: linked lists, stacks, queues, terminologie) Binary Trees & tree traversal, Binary search trees, Balanced trees (AVL, rotations), Priority queue (ADT, binary heap, leftist heap), Multiway Trees (B-tree, red-black tree), Graphs (en hun algoritmen), Hashing, Data compression (Huffman, ZLW), String matching (KMP), Randomized Algorithms.
Leerdoelen
Na afloop van dit vak kan de ijverige student:
diverse basis-structuren (lineaire lijsten en bomen) beschrijven en onderscheiden (structureel, ordening van sleutels) en is de onderliggende terminologie daarvan bekend
recursieve boomwandelingen definieren (voor pre-orde, in-orde en post-orde), deze kunnen uitvoeren op simpele voorbeelden, en kunnen aangeven welk toepassing elk van de drie ordeningen heeft
pseudo-code algoritmes geven voor iteratieve versies van diezelfde wandelingen met behulp van een stapel
onderscheid maken tussen abstracte datastructuren en hun implementaties, in het bijzonder kan de student
- een definitie geven van het begrip abstracte datastructuur
- de behandelde abstracte datastructuren (zoals stapel, lijst, set, priority queue, graaf) beschrijven met de bijbehorende operaties
- aangeven wanneer deze (abstracte) datastructuren gebruikt kunnen worden
- aangeven welke concrete implementaties passen bij elk van deze abstracte structuren
de behandelde implementaties (zoals binaire zoekboom, binaire heap, B-boom, ...) omschrijven, met hun eigen "interne" operaties
de werking van deze implementaties begrijpen en uitleggen, met relevante pseudocode, en toepassen en illustreren aan de hand van kleine voorbeelden
de (worstcase) complexiteit van de operaties van de diverse implementaties vergelijken en verklaren
daar waar verschillende implementaties van dezelfde ADT bestaan de relatieve voor- en nadelen aangeven
de behandelde algoritmen (op grafen, datacompressie, matching) omschrijven en uitleggen waar deze toepasbaar zijn
de werking van deze algoritmes begrijpen en uitleggen, en toepassen en illustreren aan de hand van kleine voorbeelden
Onderwijsvorm
Per week 2 uur hoorcollege en daarnaast 2 uur werkcollege, begeleid werken aan programmeeropdrachten.
Toetsing en weging
Schriftelijk tentamen, dat het eindcijfer bepaalt. Daarnaast moet aan drie verplichte programmeeropdrachten zijn voldaan om te kunnen slagen. De opdrachten worden gewaardeerd volgens Onvoldoende/Voldoende. De laatste twee opdrachten kunnen in uitzonderlijke gevallen met Goed worden gewaardeerd. Elke Goed geeft tevens een bonus van 0,5 op het tentamencijfer, mits dat voldoende is.
Literatuurlijst
Er is een uitgewerkt diktaat beschikbaar met de collegestof. Die stof is hoofdzakelijk gabaseerd op het boek van Adam Drozdek, Data Structures and Algorithms in C++, 4th/International Edition. Dit boek is niet verplicht, maar aanbevolen voor wie het dictaat te compact is.