Datastructuren voor informatici

Data Structures for Informatics

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

Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.

We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.

Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet. Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.uva.nl/plagiaat

Weekplanning

Contactinformatie

Coördinator

• T.F. Doolan MSc