Datastructuren

Datastructures

Studiewijzer 2016/2017

Globale inhoud

Datastructuren spelen een centrale rol in de huidige informatica en helpen om toegang
tot gegevens zo efficiënt mogelijk te maken. Dit vak geeft een inleiding in de theorie
en het gebruik van standaard datastructuren. Hoe kun je gegevens opslaan zodat
operaties op die gegevens efficiënt kunnen worden uitgevoerd. Dit kan het zoeken
van een waarde zijn, het berekenen van een minimum, etc. Het hangt van het type
gegevens af en van de operaties, wat voor datastructuur het beste past. Om algoritmes
met bijbehorende datastructuren te kunnen vergelijken wordt ook de complexiteit van
algoritmen behandeld.

In deze cursus worden de praktische aspecten van datastructuren onderwezen met
behulp van de programmeertaal C. Daarom bevat de cursus ook een introductie pro-
grammeren in C. Behandeld worden typische C-concepten zoals pointers, arrays en
structs. Tevens wordt voor verschillende taalelementen de vergelijking getrokken met
Java.

Studiemateriaal

Syllabus

• http://science.raphael.poss.name/progc/

Overig

• Alleen voor Informatici: Materiaal voor het Practicum Academische Vaardigheden staat op de aparte Blackboard pagina genaamd 'Portfolio Academische Vaardigheden BSc Informatica 2015' en de website http://practicumav.nl/

Leerdoelen

• Het kunnen bepalen van de complexiteit van operaties op datastructuren en van algoritmen.
• Het kunnen kiezen van een geschikte datastructuur voor een te ontwerpen programma.
• Het kunnen vertalen van een probleem naar een algoritme met bijbehorende datastructuren.
• Het kunnen omzetten van een algoritme naar een computerprogramma.
• Het kunnen onderscheiden van een abstracte data type en een implementatie.
• Het implementeren van datastructuren in de taal C.
• Het onder de knie krijgen van de basisprogrammeerprincipes van de taal C.

Alleen voor Informatici:
• Het kunnen rapporteren van practicumresultaten in een kort verslag
 

Onderwijsvormen

• Hoorcollege
• Laptopcollege

• Hoorcolleges Datastructuren: De theorie van datastructuren en de complexiteit van de bijbehorende operaties
• Hoorcolleges C: Conceptuele beschrijvingen en praktische overwegingen voor programmeren in de taal C.
• Laptopcolleges: Het implementeren in C van een van de besproken datastructuren van die week aan de hand van een gegeven header file en het schrijven een bijbehorend algorithme / toepassing daarvan.

Alleen voor Informatici:

• Practicum Academische Vaardigheden: 1 à 2 uur per week plus zelfstudie

Verdeling leeractiviteiten

Academische vaardigheden

• De programmeervaardigheid wordt in dit vak verder geoefend en uitgebouwd.

Alleen voor de Informatici:
• Schriftelijke verslaglegging wordt verder geoefend.

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkgroepbijeenkomsten met opdrachten geldt een aanwezigheidsplicht. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan dit als gevolg hebben dat het onderdeel niet met een voldoende kan worden afgerond.
  

Aanvullende eisen voor dit vak:

Aanvullende eisen voor dit vak:

Aanwezigheid op de hoorcolleges wordt sterk aanbevolen. Aanwezigheid op de practica is verplicht in die zin dat er geen ondersteuning via e-mail geboden wordt.

Toetsing

Het eindcijfer voor de opdrachten is het gemiddelde van de 6 opgaven, waarbij elke opgave even zwaar weegt. Dit gemiddelde moet minimaal 5 zijn (≥ 5).
Aan het einde van het blok is er een schriftelijk tentamen, dat ook minimaal met een 5 dient te worden afgesloten.

Weging Informatica
Hieronder de weging voor de onderdelen van het eindcijfer voor de informatici. Hiervoor moet het PAV verslag voor opgave 6 ook met minimaal een 5 zijn afgerond.

Weging KI en Pre-master
Hieronder weging voor de onderdelen van het eindcijfer voor de KI-ers en pre-master studenten.

Inzage toetsing

De manier van inzage wordt via de digitale leeromgeving gecommuniceerd.

Opdrachten

Stacks: Infix2RPN

Linked Lists: Insertion Sort

Trees: Huffman Encoding

AVL Trees: Sets

Heaps: Priority Queue

Hash Functions: Bloomfilter

Onderstaande opdrachten komen aan bod in deze cursus:

•    Naam opdracht 1 : beschrijving 2
•    Naam opdracht 2 : beschrijving 1
•    ....

Fraude en plagiaat

Dit vak hanteert de algemene ‘Fraude- en plagiaatregeling’ van de UvA. Onder plagiaat of fraude wordt verstaan het overschrijven van het werk van een medestudent dan wel het kopiëren van wetenschappelijke bronnen (uit bijvoorbeeld boeken en tijdschriften en van het Internet) zonder daarbij de bron te vermelden. Uiteraard is plagiaat verboden. Hier wordt nauwkeurig op gecontroleerd en streng tegen opgetreden. Bij verdenking van plagiaat wordt de examencommissie van de opleiding ingeschakeld. Wanneer de examencommissie overtuigd is dat er plagiaat gepleegd is dan kan dit maximaal leiden tot een uitsluiting van al het onderwijs van de opleiding voor een heel kalenderjaar. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam.www.uva.nl/plagiaat

Weekplanning

Rooster

Contactinformatie

Coördinator

• T.F. Doolan MSc