Algoritmiek 2008/2009

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2009 verzorgd door Jeannette de Graaf. Het vak is verplicht voor alle studenten Informatica en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 7 EC-punten op. Assistentie bij de werkgroep en het practicum wordt verleend door Ramon van Dam en Tijn Witsenburg.

De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 174. De bijbehorende werkcolleges vinden plaats op donderdagen van 9.00 uur tot 10.45 uur, in zaal 174 of een van de computerzalen. Het eerste college is op vrijdag 6 februari 2009; het eerste werkcollege is op donderdag 12 februari.

Voorkennis voor dit vak is het college Programmeermethoden. Het college dat op Algoritmiek aansluit heet Datastructuren; dit wordt gegeven in het najaar (derde semester van de studie Informatica).

Inhoud van het vak

Algoritmiek gaat uiteraard over algoritmen. Er zullen enkele belangrijke, veel gebruikte oplossingsmethoden worden besproken, compleet met voorbeelden. Besproken worden in elk geval: brute force, exhaustive search, backtracking, verdeel en heers, dynamisch programmeren, gretige algoritmen en branch and bound. Verder onder meer ook toestand-actie-ruimtes (als hulp bij het probleeemoplossen), een beetje complexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken) en heapsort.

Voor globale informatie over het vak in studiejaar 2008-2009 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2008/2009 wordt, evenals in voorgaande jaren, gebruik worden gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, second edition (Addison-Wesley, 2007). Of de internationale editie van hetzelfde boek.

De bij het college behorende sheets zijn ook via deze website beschikbaar. Na elk college zullen de bijbehorende sheets hier geplaatst worden.

Programma

Het programma voor het college wordt hieronder bijgehouden. Voor elke week staat daarin welke onderwerpen aan de orde zijn gekomen met de bijbehorende hoofdstukken uit het boek en de gebruikte sheets. De datum stelt de vrijdag van de betreffende week voor. Bovendien kan men hier de bij het werkcollege behandelde opgaven vinden.

PROGRAMMA 2008/2009

Werkcollege

Datum (vrijdag)	Onderwerp	Sheets	Boek
6 februari	Introductie	sheets1	1.1, 1.2, 1.4 (t/m graafrepresentaties)	geen
13 februari	Grafen, bomen, toestand-actie-ruimte	sheets2	1.4 (grafen,bomen) + sheets	opgaven1
20 februari	Toestand-actie-ruimte, complexiteit	sheets3	sheets + 2.1	opgaven2
27 februari	Complexiteit, brute force, exhaustive search	sheets4	2.2-4, 3.1-3	opgaven3
6 maart	Exhaustive search, backtracking	sheets5	3.4 + sheets + 12.1 (deels)	programmeeropdracht 1 (302/304)
13 maart	Backtracking, Verdeel en heers	sheets6	12.1 + 4.1-2	opgaven5
20 maart	Verdeel en heers	sheets7	4.3-4, 4.5 (deels), 4.6 (deels), 5.1, 5.5	programmeeropdracht 1 (302/304)
3 april	Decrease and conquer, dynamisch programmeren	sheets8	sheets, intro H8	opgaven7
10 april	Goede vrijdag: geen college	...	...	programmeeropdracht 2 (302/304)
17 april	College uitgevallen	...	...	programmeeropdracht 2 (302/304)
24 april	Dynamisch programmeren, gretige algoritmen	sheets9 + sheets10	sheets, 8.1, 8.4, intro H9	opgaven10
1 mei	Algoritme van Dijkstra + branch & bound	sheets11	9.3 + 12.2 (deels)	geen werkcollege
8 mei	Branch & bound, heap(sort)	sheets12	12.2 (rest) + 6.4	opgaven11
15 mei	Oude tentamenopgaven	...	...	do: programmeeropdracht 3 (302/304); vr: opgaven (174): opgaven13

Opgaven

Tijdens werkcolleges worden opgaven gemaakt, soms op papier en soms achter de computer. Deze opgaven kunnen via deze website worden verkregen, maar zullen ook tijdens (werk)college worden uitgedeeld. Zie voor informatie over het tweede werkcollege (binaire bomen en binaire zoekbomen) ook de Algoritmiek webpagina van Tijn Witsenburg. Van de opgaven van het werkcollege van 12 maart 2009 is een uitwerking beschikbaar.

Programmeeropdrachten

Bij dit college moeten drie programmeeropdrachten (in C++) gemaakt worden, waarbij de nadruk ligt op het toepassen van de op college besproken probleemoplossingsmethoden. De opdrachten moeten alle drie voldoende zijn (>=6). Het eindcijfer voor het vak is het behaalde tentamencijfer, mits de programmeeropdrachten voldoende zijn beoordeeld. In tegenstelling tot bij Programmeermethoden telt het cijfer voor het programmeerwerk dus niet mee voor het eindcijfer. Programmeerwerk mag in tweetallen worden gemaakt. De opdrachten dienen op de deadlines te worden ingeleverd. Anders gaat er in principe per week te laat inleveren een punt af.

Programmeeropdracht 1 (brute force). Uiterste inleverdatum: vrijdag 20 maart.
De eerste programmeeropgave is inmiddels nagekeken. Zie de webpagina van Tijn Witsenburg.
Voor de duidelijkheid: de in de opdracht gesuggereerde representatie van een (tussen)stand bij het spel Bynum game middels een boolean array, is wel de gemakkelijkste en voor-de-handliggendste, maar zeker niet de efficientste. Het is dan ook zeker niet verplicht die representatie te gebruiken. Je kunt een stand bijvoorbeeld ook op een of andere manier als collectie rechthoeken bijhouden. Hierdoor vermijd je de opslag van standen die eigenlijk hetzelfde zijn.

Programmeeropdracht 2 (backtracking). Uiterste inleverdatum: vrijdag 17 april.
Zie de webpagina van Tijn Witsenburg voor de resultaten.
Bij de puntentelling (werking) is ook rekening gehouden met de handigheid/efficientie van de gebruikte methode.

Programmeeropdracht 3 (dynamisch programmeren). Uiterste inleverdatum: vrijdag 15 mei.
Enige tips bij deze opdracht zijn alhier te vinden.

Tentamen

Het tentamen heeft plaatsgevonden op dinsdag 2 juni 2009, 10.00-13.00 uur.
De resultaten zijn inmiddels bekend en alhier te vinden. De nagekeken tentamens zijn bij de docent af te halen (kamer 151).

Het hertentamen is gehouden op dinsdag 4 augustus 2008, 10.00-13.00 uur.
Mededeling: het augustus-tentamen is inmiddels nagekeken. De resultaten staan alhier.

De tentamens van 2007, 2008 en 2009 zijn hieronder te vinden, alsmede uitwerkingen van de juni-tentamens.

Tentamen van juni 2007. Een zeer uitgebreide uitwerking, bedoeld om een en ander nog eens uit te leggen, is eveneens beschikbaar. Er wordt overigens niet verwacht dat je zelf zo veel opschrijft bij het tentamen, maar je moet je antwoorden wel duidelijk toelichten (maar dan dus wat korter).

Tentamen van augustus 2007, met uitwerking van opgave 3

Tentamen van juni 2008, met uitgebreide uitwerking en bijbehorende toestandactieruimte

Tentamen van augustus 2008.

Tentamen van juni 2009, met uitgebreide uitwerking en bijbehorende toestandactieruimte

Tentamen van augustus 2009.

Vragen en/of opmerkingen kunnen worden gestuurd naar: graaf@liacs.nl.

25 september 2009 - http://www.liacs.nl/home/graaf/ALGO/