Informatie over de cursus Analyse van Algoritmen (IBC013), voorjaar 2014

Docent (hoorcollege): Prof Dr Hans Zantema, Huygensgebouw 02.528 (alleen op dinsdag), tel 040-2472749 (behalve op dinsdag), email: h.zantema@tue.nl

Docent (werkcollege): Dr Josef Urban, Huygensgebouw 02.528, tel 024-3652631, email: josef.urban@gmail.com

Beschrijving:
In het vak "Algoritmen en Datastructuren" zijn diverse algoritmen aan de orde gekomen, met een nadruk op implementatie aspecten. Hoe je formele afschattingen van efficientie kunt formuleren en bewijzen is bij "Complexiteit" behandeld. In dit vak "Analyse van Algoritmen" komen beide invalshoeken samen: we zullen allerlei algoritmen bekijken en daarvan eigenschappen zoals de efficientie analyseren. In het bijzonder zal aandacht gegeven worden aan lineair programmeren en geometrische algoritmen. Het vak wordt afgesloten met een presentatie over NP-compleetheid: van een serie problemen waarvoor alleen exponentiele algoritmen bekend zijn wordt aangetoond dat ze equivalent aan elkaar zijn.


Literatuur:
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009
Dit is hetzelfde boek dat ook bij beide voorkennisvakken wordt gebruikt.


Colleges en onderwerpen:

datum	onderwerp	boek	opgaven
4 februari	Algemene technieken, binaire zoekbomen, diepte AVL bomen	hoofdstuk 12	opgaven
11 februari	Lineair programmeren: simplex methode	hoofdstuk 29	29.1:1-6; 29.3: 2,4,5,6
18 februari	Lineair programmeren: simplex methode	hoofdstuk 29	29.5:2,4,5,6,7
25 februari	Computationele geometrie: snijpunten van lijnstukken, convex hulsel	hoofdstuk 33	33.2:1,3,4,5; 33.3:1,2,3
11 maart	Computationele geometrie: kleinste afstand tussen punten, P en NP	hoofdstuk 33	33.4:2,3,4,6
18 maart	NP-compleetheid	hoofdstuk 34	34.3:2,3,7; 34.4: 5,6; 34,5: 2,3
25 maart	NP-compleetheid, overzicht	hoofdstuk 34

Tentamen
Het tentamen is een schriftelijk tentamen waarbij het boek en/of eigen materiaal niet gebruikt mag worden (gesloten boek tentamen). Daarnaast zijn er huiswerkopgaven die op de werkcolleges van 20 februari, 13 maart en 27 maart ingeleverd kunnen worden. Deze worden nagekeken en met commentaar teruggegeven; bij goed resultaat kan dit maximaal een punt extra opleveren voor het tentamen.
De tentamenstof:
Hoofdstuk 29 t/m pag 878 en pag 886 t/m 892
Hoofdstuk 33 t/m pag 1036 en pag 1039 t/m 1043
Hoofdstuk 34 t/m pag 1091

Opgaven:
Werkcollegeopgaven voor 6 februari 2014
Huiswerkopgaven in te leveren op 20 februari 2014
Huiswerkopgaven in te leveren op 13 maart 2014
Huiswerkopgaven in te leveren op 27 maart 2014
Tentamen van april 2011
Tentamen van juni 2011
Tentamen van april 2012
Tentamen van juni 2012
Tentamen van april 2013
Tentamen van juli 2013
Tentamen van april 2014, met uitwerking

Laatste aanpassing: 2 april 2014