Datastructuren

Najaar 2017, Universiteit Leiden

Docent

Dr. C.P.T. (Stijn) de Gouw

Opdrachten insturen, assistentie: data.structuren.2017@gmail.com

Privacy gevoelige vragen (vervang AT door @): sdg AT ou.nl

Boek

Aanbevolen (niet verplicht): Adam Drozdek, Data Structures and Algorithms in C++, 4th / International Edition. ISBN13: 9781133613053

Achtergrondinformatie: Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ [International ed of 4th revised edition], 2013

Nieuws

Het tentamen Datastructuren van 3 januari is nagekeken en de cijfers daarvan zijn beschikbaar. Omwille van privacy redenen staan de cijfers op een beveiligde Blackboard pagina (en enkel de persoonlijke cijfers zijn zichtbaar).

Merk op dat dit niet het eindcijfer is voor het vak: daarvoor moet het prakticum eerst worden afgerond. Zoals bekend wordt voor iedere prakticumopdracht met beoordeling "Goed" een half punt bonus op het eindcijfer toegekend. Zodra het prakticum is afgerond en het eindcijfer voor het gehele vak bekend is, wordt het eindresultaat in Usis ingevoerd.

Het is mogelijk de tentamens in te zien bij dr. Marcello Bonsangue (kamer 157a).

Practicumopdrachten

  1. Opdracht 1 (Deadline 19-10-2017, 23:59): beschrijving en hulpbestanden (update: deadline 1 dag verlengd)
  2. Opdracht 2 (Deadline deel 1: 09-11-2017, 23:59. Deadline deel 2: 30-11-2017, 23:59. ): beschrijving (update: deadlines 1 dag verlengd)
  3. Opdracht 3 (Deadline deel 1: 05-01-2018, 23:59. Deadline deel 2: 26-01-2018, 23:59): Beschrijving. Constructies op eindige automaten: Intersect.pdf en Non-determinism.pdf. C++ Broncode hulpbestanden (UPDATE 13 december: er zat een kleine bug in main.cpp die in deze nieuwe versie van de hulpbestanden is verbeterd, en de print functies zijn aangepast. Verder kunt u de methode contains in tree.h negeren).

Slides werkcollege intro

Deadlines herkansing:

  • Opdracht 2: 19-01-2018, 23:59.
  • Opdracht 3: 23-02-2018, 23:59.

Extra werkcollege op donderdag 11-01-2018, 11:00 - 12:45. Oorspronkelijk stond dit extra werkcollege op vrijdag 12 januari, maar er is dan al een tentamen ingepland. Op 11 januari zijn er geen andere geroosterde activiteiten voor 2e jaars I&E, I&B en Informatica. Vragen die je nog hebt na dit werkcollege kunnen per mail gestuurd worden.

Rooster en slides

  1. Hoorcollege slides. Behandelde onderwerpen: Intro en definitie ADTs, datastructuren in vogelvlucht: bomen, lijsten, queues. C++: templates, STL, inheritance. Werkcollege intro.
  2. Hoorcollege slides. Behandelde onderwerpen: bomen formele definities, boomwandelingen: recursief, met stack, met inorde-threads en Morris.
  3. Hoorcollege slides. Behandelde onderwerpen: binaire zoekbomen (bzb's). Bzb's bouwen: knopen toevoegen/verwijderen. Bzb use cases: waarde zoeken, min/max zoeken, sorteren, zoek k-e element. Efficientie bzb: interne & externe padlengte, best/average/worst case bzb.
  4. Hoorcollege slides. Bzb: tellen elementen in interval, Set ADT. Bomen balanceren: rotaties, DSW algoritme, AVL-bomen, splay-trees.
  5. Hoorcollege slides. Priority Queue (PQ) implementaties: binaire heap, leftist trees. Double-ended PQ's: dual-structure, interval heap.
  6. Hoorcollege slides. B-bomen, rood-zwart bomen. Grafen: representatie, depth-first search.
  7. Hoorcollege slides. Grafen: articulation points, breadth-first search, cykels, ADT Union Find, minimal spanning Trees (Prim, Kruskal), Dijkstra shortest path
  8. Hoorcollege slides. Grafen: Floyd-Warshall shortest path, topologisch sorteren. Hashing: perfect hashen, open adresseren: lineair, kwadratisch.
  9. Hoorcollege slides, extra voorbeeld LZW compressie. Vervolg hashen: dubbel hashen, chaining, performance met grafiek. Compressie: Huffman (compressie + decompressie), LZW (compressie).
  10. Hoorcollege slides, voorbeeld failure Links Knuth-Morris-Pratt. Compressie: LZW (decompressie). Pattern matching: Knuth-Morris-Pratt.
  11. Hoorcollege slides. College over practicumopdracht 3, deel 1.
  12. Hoorcollege slides. College over practicumopdracht 3, deel 2.
  13. 20 december: geen college.

11-01-2018, 11:00 - 12:45 extra werkcollege (zie boven)


Tentamenstof

Alles in het dictaat over onderwerpen die in het bovenstaande rooster staan is tentamenstof. Het boek is geen tentamenstof maar kan wel handig zijn bij het voorbereiden voor het tentamen. Onderwerpen wel in het dictaat staan, maar overgeslagen zijn volgens bovenstaand schema zijn geen tentamenstof, zoals Compression: Burrows-Wheeler en Pattern Matching: Aho-Corasick.

Zie ook oude tentamens.

Beoordeling

Om het vak te halen moet aan de volgende criteria worden voldaan:

  • Het tentamencijfer moet minstens 5.5 zijn
  • Alle drie de practicumopdrachten moeten voldoende of goed zijn (1 herkansing per opdracht, herkansingen krijgen geen "goed").

Het eindcijfer is het tentamencijfer, plus 0.5 punt bonus voor iedere practicumopdracht die als "goed" is beoordeeld (met een 10 als maximum eindcijfer). Voor opdracht 2 en opdracht 3 kan "goed" worden gehaald, het maximum bij opdracht 1 is "voldoende".

Deelresultaten behaald in het verleden tellen niet mee, tenzij je daar expliciete afspraken over hebt gemaakt met de vorige docent(en). Die afspraken zullen, na controle bij de betreffende docent, worden gerespecteerd.

Vorige edities

o.a. oude tentamens: http://liacs.leidenuniv.nl/~hoogeboomhj/dat/