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

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, geometrische algoritmen en aan cryptografische systemen gebaseerd op getaltheorie.


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
5 februari	Algemene technieken, binaire zoekbomen, diepte AVL bomen	hoofdstuk 12	opgaven
19 februari	Lineair programmeren: simplex methode	hoofdstuk 29	29.1:1-6; 29.3: 2,4,5,6
26 februari	Lineair programmeren: simplex methode	hoofdstuk 29	29.5:2,4,5,6,7
5 maart	RSA crypto: rekenen moludo, ggd berekenen	hoofdstuk 31	31.1:1,2,3,4,6; 31.2:1,2,4
12 maart	Fermat, RSA cryptosysteem, intro comp.geometrie	hoofdstuk 31	31.2:6,7,8,9; 31.7:1
19 maart	Computationele geometrie: snijpunten van lijnstukken, convex hulsel	hoofdstuk 33	33.2:1,3,4,5; 33.3:1,2,3
26 maart	Computationele geometrie: kleinste afstand tussen punten, overzicht	hoofdstuk 33	33.4:2,3,4,6

Tentamenstof:
Hoofdstuk 29 t/m pag 878 en pag 886 t/m 892
Hoofdstuk 31 t/m pag 938, pag 946 t/m 950, Theorem 31.31, pag 957 t/m 964
Hoofdstuk 33 t/m pag 1036 en pag 1039 t/m 1043

Opgaven:
Werkcollegeopgaven voor 7 februari 2013
Huiswerk voor 28 februari 2013
Huiswerk voor 14 maart 2013
Huiswerk voor 28 maart 2013
Tentamen van 12 april 2011
Tentamen van 28 juni 2011
Tentamen van 3 april 2012
Tentamen van 26 juni 2012

Laatste aanpassing: 20 maart 2013