Doel
Inzicht en gebruik van standaard datastructuren en bijbehorende algoritmen, verkrijgen van enig inzicht in efficientie verschillen, abstract leren denken: onderscheid gebruik en implementatie.
Beschrijving
Dit college is een vervolg op het college Algoritmiek. Dus het leren ontwerpen en begrijpen van algoritmen — op zijn minst de standaard algoritmen die tot het repertoire van elke computing expert behoren — zullen weer een belangrijke rol gaan spelen. Zoals bekend vormen het algoritme en de data die van belang zijn voor het algoritme een samenwerkend geheel. Bij data die van belang zijn voor het algoritme valt te denken aan input en output gegevens maar ook data die het algoritme bijhoudt voor zijn werking. Daarom zullen we ook ruim aandacht schenken aan het handig structureren en representeren van de data – vandaar de naam van het college. Er bestaan verschillende standaard datastructuren zoals lists, trees, arrays, sets, bags om er maar een paar te noemen. Elk van deze gegevensstructuren kun je karakteriseren vanwege hun structuur en hun access methods. De standaard datastructuren kunnen met een breed scala van algoritmen samenwerken. Er zijn natuurlijk ook datastructuren die toegesneden zijn op een beperkte klasse van algoritmen. Uiteraard zullen we de standaard datastructuren zoals stapels (stacks), rijen (queues), lijsten(lists), binaire en multiway bomen(binary en multiway trees), priority queues, grafen(graphs) de revue laten passeren. Onze aanpak van het ontwerp van datastructuren is via Abstract Data Types (hetgeen nauw aansluit bij OO-programmeren). Door gebruik te maken van ADT’s kunnen we het gebruik van de gegevensstructuur en de definitie van het gewenste gedrag ervan scheiden van de implementatie. Onderwerpen: Linked Lists, Stacks, Queues, Binary Trees, Multiway Trees, Graphs, Hashing, Data Compression, String Matching, Randomized Algorithms
Methode
hoorcollege, werkgroep, programmeeropdrachten
Examinering
Schriftelijk. Daarnaast moet aan verplichte programmeeropdrachten zijn voldaan.
Literatuur
Data Structures and Algorithms in C++, Adam Drozdek, Third Edition, Thomson Course Technology, isbn 0-534-49182-0