Datastructuren

Website:

website met extra informatie

Vakcode:

INFODS

Studiepunten:

7.5 ECTS

Periode:

periode 4 (week 17 t/m 27, dwz 23-4-2012 t/m 6-7-2012; herkansing week 34)

Timeslot:

Deelnemers:

tot nu toe 200 inschrijvingen

Rooster:

Let op: m.i.v. het collegejaar 2008/2009 is het rooster te vinden in Osiris

Docenten:

Dit is een oud rooster!

vorm	groep	tijd	week	zaal	docent
college		ma 13.15-15.00	17-21	AARD-GROOT	Hans Bodlaender
		ma 13.15-15.00	23-26	AARD-GROOT
		wo 11.00-12.45	25-26	BBL-075
		do 9.00-10.45	17-19	AARD-GROOT
			21	AARD-GROOT
			23-26	AARD-GROOT
werkcollege					Sander van der Hurk Marijke Bodlaender Mihai Polak Guido Passage Tigran Gasparian
	groep 1	di 13.15-15.00	17-21	BBL-079	Merel Rietbergen
		di 13.15-15.00	23-26	BBL-079
		do 11.00-12.45	17-19	BBL-061
			21	BBL-061
			23-26	BBL-061
	groep 2	di 13.15-15.00	17-21	BBL-061	Steven Woudenberg
		di 13.15-15.00	23-26	BBL-061
		do 11.00-12.45	17-19	MIN-202
			21	MIN-202
			23-26	MIN-202
	groep 3	di 13.15-15.00	17-21	BBL-205	Bart Jansen
		di 13.15-15.00	23-26	BBL-205
		do 11.00-12.45	17-19	BBL-075
			17-19	BBL-077
			18-19	BBL-077
			21	BBL-075
				BBL-077
				BBL-077
			23-26	BBL-075
				BBL-077
				BBL-077
	groep 4	di 13.15-15.00	17	BBL-077
			18	BBL-023
			19	BBL-106 CLZ
			20-21	BBL-077
			23-26	BBL-077
		do 11.00-12.45	17-21	BBL-071
			23-24	BBL-071
			25	BBL-001
			26	BBL-071
	groep 5	di 13.15-15.00	17-21	BBL-075
		di 13.15-15.00	23-26	BBL-075
		do 11.00-12.45	17	BBL-005
			17	BBL-106 CLZ
			18	BBL-007
			19	BBL-065
			20-21	BBL-007
			23	BBL-007
			24	BBL-065
			25	BBL-106 CLZ

Tentamen:

week: 23	wo 5-6-2013	13.15-15.15 uur	zaal: EDUC-ALFA
week: 27	vr 5-7-2013	17.00-20.00 uur	zaal: EDUC-GAMMA
week: 33	vr 16-8-2013	13.30-16.30 uur	zaal: EDUC-ALFA	aanvullende toets

Inhoud:

Alvorens men een computerprogramma kan schrijven om een probleem op te lossen, moet een aanpak (een reeks stappen) bedacht worden die het programma kan volgen om het probleem op te lossen. Zo'n reeks stappen wordt een algoritme genoemd. In dit vak worden algoritmen besproken voor het sorteren van en het zoeken in een verzameling gegevens. Zoekalgoritmen spelen een speciale rol, want ze hangen af van de manier waarop de gegevens zijn opgeslagen. Een methode voor gegevensopslag wordt een datastructuur genoemd. In het college worden diverse datastructuren behandeld.

Voor veel problemen zijn er wezenlijk verschillende algoritmen of datastructuren te bedenken. In Datastructuren leer je ook hoe je de looptijd van algoritmen (en het geheugengebruik van datastructuren) kunt inschatten zonder dat daar een implementatie voor nodig is.

Een aantal van de onderwerpen die behandeld worden zijn: sorteren (quicksort, heap sort, bucket sort, ...); hash tabellen; zoekbomen; rood-zwart-bomen, skiplists, ...

Daarnaast zullen een aantal onderwerpen uit de wiskunde worden behandeld. Deze zijn nodig voor de analyse van de algoritmen en datastructuren.

Literatuur:

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Third Edition, MIT Press / McGraw-Hill Book Company, 2009.

De vorige editie kan ook gebruikt worden voor alle onderwerpen op red-black trees na: daar is de tekst gewijzigd. Als je de tweede editie gebruikt, gebruik dan een kopie van het hoofdstuk over red-black trees.

Eventueel zal over een enkel onderwerp nog materiaal op de website van het vak verschijnen.

Werkvorm:

Hoor- en werkcollege; programmeerpracticum. Ook is er een programmeerwedstrijd.

Toetsvorm:

Twee deeltentamens; en acht programmeeropgaven. (De eerste opgave is alleen om het systeem uit te proberen.)

Inspanningsverplichting voor aanvullende toets:

Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.

wijzigen?