De module Analyse van Algoritmen (officiële naam: Datastructuren
en Algoritmen 2) is onderdeel van de minor
Software Engineering binnen de opleiding Informatica aan de
Hogeschool Leiden. Deze pagina bevat enige practische informatie
over de module.
Docent
Naam: Rudy van Vliet
telefoon: 071-527 5775
email: rvvliet@liacs.nl
Boek
Bij deze module maken we gebruik van het boek
Algorithmics, the Spirit of Computing, third edition,
van David Harel en Yishai Feldman. Het ISBnummer is
0-321-11784-0. Te verkrijgen bij de betere boekhandel.
Lesrooster + behandelde stof
In het collegejaar 2007-2008 is er gedurende zeven weken twee
keer per week anderhalf uur les gegeven. Meestal op maandag en
donderdag, van 11:00 tot 12:30, maar er was een uitzondering.
Het was een combinatie van
(hoofdzakelijk) hoorcollege en (aanvullend) opgaven maken.
Hieronder staat het lesrooster, zoals dat is gevolgd.
Bij alle lessen is na afloop ook de behandelde stof vermeld.
Maandag 19 november 2007, 11:00-12:30, F174
Behandelde stof: herhaling recursieve functies (Hanoi); grafen en bomen;
treesort (veelal uit Hst 2 van boek).
Verder: voorwaarts zoeken (DFS) en zijwaarts zoeken (BFS);
markeren bezochte knopen in grafen (begin Hst 4);
ontsnappen uit vijandelijk gebied
(n.a.v. een programmeeropgave) en bloksorteren als extra voorbeelden BFS
(n.a.v. programmeeropgave Booksort).
Opgave 4.2a-b.
Donderdag 22 november 2007, 11:00-12:30, C202
Behandelde stof:
gebruik van stapel
bij recursieve aanroepen;
verdeel en heers (uit Hst 4);
dubbel werk bij recursieve functies;
dynamisch programmeren
als alternatief: Fibonacci getallen, rijtjes corresponderende haakjes;
Beiers bierfestijn
(n.a.v. programmeeropgave The Bavarian Beer Party);
kortste afstand in gerichte acyclische graaf (uit Hst 4).
Maandag 26 november 2007, 11:00-12:30, F174
Behandelde stof:
extra opgave
kortste pad met dynamisch programmeren met behulp van
topologisch sorteren;
kansrekening met dobbelsteen en munt;
flipperkast (n.a.v. programmeeropgave Pachinko)
recursief en met dynamisch programmeren;
uitputtend zoeken; binair zoeken; interpolatie zoeken
(begin Hst 4). Huiswerk: implementeer Pachinko.
Vrijdag 30 november 2007, 13:00-14:30, F176
Behandelde stof:
maximale afstand in convexe veelhoek; gretig algoritme (Prim)
en een nog gretiger algoritme (Kruskal)
voor minimale opspannende boom;
de heap (toevoegen, veranderen
en verwijderen van elementen; priority
queue en heapsort als toepassingen).
Verwezen naar opgave 2a van tentamen 29 januari 2007. Huiswerk: Opgave 4.14.
Maandag 3 december 2007, 11:00-12:30, C202
Behandelde stof:
Knapzakprobleem gretig en uitputtend (n.a.v. opgave 4.14, of eigenlijk
4.15b).
Fouten in programma's: voorbeelden uit de praktijk;
syntax-fouten en logische fouten;
zoeken woord `money'; testen geeft geen
zekerheid; oneindige lussen; partiële en totale correctheid;
beweringen/invarianten, convergenten; omkeren van een string (begin Hst 5).
Correctheid algoritme uit opgave 1a van tentamen 15 februari 2007. Huiswerk: Opgave 1b en 1c van genoemd tentamen.
Maandag 10 december 2007, 11:00-12:30, D251
Behandelde stof: Opgave 5.15ii;
beperkingen computer bij bewijs correctheid;
vier-kleurenprobleem als illustratie belang correct programma
(vervolg Hst 5).
Constante factor tijdswinst bij slimme implementatie algoritmes
(begin Hst 6);
voorbeelden logaritmische, polynomiale, exponentiële en
superexponentiële functies. Huiswerk: opgave 6.2.
Donderdag 13 december 2007, 11:00-12:30, B123
Behandelde stof:
Constante factoren tellen niet echt bij complexiteit algoritmes;
grote-O-notatie; orde verschil bij verschillende algoritmes;
complexiteit geneste lussen (met voorbeeld sorteeralgoritme
van 6 december 2007) (vervolg HSt 6); listig optellen. Opgave 6.6.
Maandag 17 december 2007, 11:00-12:30, D144
Behandelde stof:
complexiteit recursieve algoritmes voor VindMinMax en Hanoi (met
inductie); analyse treesort, mergesort, quicksort, slechtste-geval vs
gemiddelde-geval (vervolg HSt 6).
Verwezen naar opgave over
complexiteit heapsort.
Maandag 7 januari 2008, 11:00-12:30, B115
Behandelde stof:
Herhaling bewijs met inductie (zie 17 december);
complexiteit algoritmes voor convex omhulsel (eind Hst 6);
recursieve oplossing Hanoi is optimaal (begin Hst 7).
Ad-hoc opgave over algoritme van KMP;
gewezen op
oude tentamenopgave over algoritme van KMP.
En passant behandelde opgave: 7.1a-b.
Donderdag 10 januari 2008, 11:00-12:30, B115
Behandelde stof:
beslissingsproblemen; handelsreizigersprobleem (TSP);
Hamilton pad probleem; landkaart-3-kleurings probleem;
graaf-k-kleurings probleem; polynomiale controle; P, NP, NPC
(NP-volledige problemen);
als één NP-volledig probleem polynomiaal
is, dan is P=NP; beslissingsprobleem vs optimaliseringsprobleem
(vervolg Hst 7).
En passant behandelde opgave: 7.9.
Maandag 14 januari 2008, 11:00-12:30, B117
Behandelde stof: complexiteit uitdrukken in
grootte van de invoer,
b.v. niet-priem en Hanoi;
stopprobleem is niet beslisbaar (zonder bewijs, Hst 8);
wanneer is foutkans acceptabel? deterministische en probabilistische
algoritmen voor priemtest/samengesteldheid, met grote en kleine foutkans
(uit Hst 11)
Maandag 21 januari 2008, 11:00-12:30, B117 (vragenuur, zie beneden)
Donderdag 24 januari 2008, 11:00-12:30, B117 (vervallen)
Tentamenstof
De tentamenstof is de stof die tijdens de lessen is behandeld (zie hierboven).
Ze bestond dus uit stof uit het boek en door de docent
toegevoegd materiaal. De stof uit het boek besloeg
de volgende bladzijden:
uit hoofdstuk 11: 297-298 bovenaan; 301-306 bovenaan
Zoek zelf even op in het boek welke opgaven bij deze bladzijden horen.
En vergeet natuurlijk niet de door de docent toegevoegde stof.
Dat was namelijk ook heel wat dit jaar.
Tentamens
De module wordt afgesloten met een schriftelijk tentamen en een
schriftelijk hertentamen. Het eerste tentamen (op dinsdag 22 januari
2008) is voorbij.
U kunt het hier nog eens nalezen.
De cijfers van dit tentamen zijn bekend. U vindt ze
hier.
Op speciaal verzoek heeft de docent zijn eigen uitwerking van dit
eerste tentamen ingescand. Het zijn zes pagina's. U vindt ze hieronder: pagina 1,
pagina 2,
pagina 3,
pagina 4,
pagina 5,
pagina 6.
Het hertentamen (op dinsdag 12 februari 2008) is ook voorbij.
U kunt het hier nog eens nalezen.
Omdat dit tentamen moeilijker was dan het eerste tentamen, zijn alle
scores met 25% opgehoogd.
De resulterende cijfers vindt u
hier.
