Algoritmiek (Informatica en Economie),

voorjaar 2012

Het eerstejaarsvak Algoritmiek is verplicht voor alle studenten Informatica, Informatica en Economie, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 6 EC-punten op.

LET OP: Deze website is alleen bedoeld voor de eerstejaars studenten Informatica en Economie. Zij volgen het vak in Den Haag. De Leidse studenten (studenten Informatica, studenten met een dubbele propedeuse Wiskunde/Informatica) hebben een eigen website, die wordt bijgehouden door de docent van het vak in Leiden, dr. J. Kwisthout.

Het vak Algoritmiek in de studie Informatica en Economie is in principe hetzelfde als het vak Algoritmiek in de studie Informatica. De inhoud is gelijk en de tentamens worden hetzelfde. Alleen de docent, de werkcollege-assistent, de locatie, de collegetijden en de inleverdata voor de practicumopdrachten waren anders.

In het voorjaar van 2012 was de docent voor Informatica en Economie (net als vorig jaar) Rudy van Vliet. Als hij in gebouw Stichthage in Den Haag is, is zijn werkkamer 12.22, op de twaalfde verdieping. Zijn email-adres is rvvliet(at)liacs(dot)nl. Op de homepage van de docent kunt u zien of hij op zijn werk te bereiken is.
Assistentie bij de werkgroep en het practicum werd (eveneens: net als vorig jaar) verleend door student-assistent Jan van Rijn.

De colleges waren op donderdagen van 11.15 tot 13.00 uur. De bijbehorende werkcolleges vonden plaats op dezelfde dagen als de colleges, maar dan van 13.45 tot 15.30 uur. De eerste colleges waren op donderdag 9 februari 2012, de laatste op donderdag 24 mei 2012. Op de donderdagen 15 maart, 19 april en 17 mei 2012 waren er om diverse redenen geen colleges van dit vak.

Zowel hoorcollege als werkcollege was in principe in zaal Plein. Alleen op 1 maart 2012 was het college in zaal Archipel. En op vier donderdagen heeft het werkcollege plaatsgevonden in de computerzaal Paleistuin.

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 (en Economie)).

Inhoud van het vak

Algoritmiek gaat uiteraard over algoritmen. Er zijn enkele belangrijke, veel gebruikte oplossingsmethoden besproken, compleet met voorbeelden. Besproken zijn onder meer: 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), depth first search, breadth first search en heapsort.

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

Materiaal

In het studiejaar 2011/2012 is gebruik gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, third edition (Addison-Wesley, 2012). Of de internationale editie van hetzelfde boek.

Voor wie de tweede editie van het boek heeft aangeschaft, was er geen man overboord: voor zover van belang bij Algoritmiek zijn de verschillen tussen de twee edities niet zo heel groot. Hoofdstukken 4 en 5 zijn omgedraaid, en sommige paragrafen zijn naar een ander hoofdstuk verhuisd. Voor een compleet overzicht, zie de verwijslijst van de derde editie naar de tweede editie (versie van 23 februari 2012). De paragraaf over het berekenen van binomiaalcoefficienten met behulp van dynamisch programmeren is bij de overgang van de tweede editie naar de derde editie uit het boek verdwenen. Dit onderwerp behoorde echter nog wel tot de tentamenstof. U vindt hier een scan van de betreffende paragraaf.

De bij het college behorende sheets zijn ook via deze website beschikbaar.

Programma

Het programma van colleges en werkcolleges is hieronder te vinden. Voor elke week staat daarin welke onderwerpen aan de orde zijn gekomen, met de bijbehorende hoofdstukken uit het boek en de gebruikte sheets. Bovendien kan men hier de bij het werkcollege behandelde opgaven vinden.

PROGRAMMA 2011/2012

Datum	Onderwerp	Sheets	Boek	Werkcollege
9 februari	Introductie	sheets1, en kleine versie	1.1, 1.2, 1.4 (t/m graafrepresentaties)	opgaven1, presentatie Jan (met pseudocode) (versie van 23-02-2012)
16 februari	Grafen en bomen	sheets2, en kleine versie	1.4	opgaven2
23 februari	Toestand-actie-ruimte	sheets3, en kleine versie, Kannenprobleem (Die Hard)	sheets, 4.5 (subpar `Searching and Insertion in a BST' en `The Game of Nim') en 6.6 (subpar `Reduction to Graph Problems')	opgaven3, presentatie Jan (uit 2011)
1 maart	Complexiteit, brute force	sheets4, en kleine versie	2.1-3; 3 inl., 3.1-3	Programmeeropdracht 1
8 maart	Exhaustive search, backtracking	sheets5, en kleine versie	3.4, 3.5; sheets; 12 inl. 12.1	opgaven5, antwoorden5, presentatie Jan (met pseudo-code) (uit 2011, oude nummering opgaven)
15 maart	geen college	--	--	geen werkcollege
22 maart	Backtracking, verdeel en heers	sheets6, en kleine versie	12.1; 5 inl., 5.1, 5.2, 4 inl., 4.1	opgaven6, presentatie Jan (met pseudo-code) (uit 2011)
29 maart	Verdeel en heers	sheets7, en kleine versie	4.1, 4.4, 5.3-5.5	Programmeeropdracht 2
5 april	Rest decrease and conquer, dynamisch programmeren	sheets8, en kleine versie	sheets; 8 inl.	opgaven8, presentatie Jan (met pseudo-code) (uit 2011) (andere nummering opgaven)
12 april	Dynamisch programmeren	sheets9, en kleine versie	scan paragraaf 8.1 uit editie 2 van boek; sheets; 8.2, voorbeeld 2 in 8.1	opgaven9, presentatie Jan (met pseudo-code) (uit 2011)
26 april	Gretige algoritmen, Dijkstra	sheets10, en kleine versie	9 inl.; 9.3; sheets	opgaven10/11, presentatie Jan (geen uitwerkingen) (uit 2011), antwoorden opgaven 4 en 5
3 mei	Gretige algoritmen, Dijkstra, Branch & bound	sheets11, en kleine versie	9.3, sheets, 12.2	Programmeeropdracht 3
10 mei	Branch & bound; heapsort	sheets12, en kleine versie	12.2; 6.4	opgaven12, geen nette uitwerking
24 mei	Oefenen oud tentamen	Tentamen van augustus 2010	alle stof	Bespreken oud tentamen

De tentamenstof bestaat uit: alles wat we gedurende het semester behandeld hebben. Dat komt op het volgende neer:

De slides bij de hoor- en werkcolleges die je hierboven kunt vinden. Alleen slides 14 t/m 17 van hoorcollege 4 (over complexiteit-en-recursie) hoef je niet te kennen.
De hierboven vermelde delen uit de derde editie van het boek van Anany Levitin (heb je een tweede editie van het boek, kijk dan in de verwijslijst van de derde editie naar de tweede editie (versie van 23 februari 2012)).
De opgaven die bij het werkcollege zijn behandeld, en die je hierboven nog kunt vinden.
Alles wat bij hoor- en werkcollege en de programmeeropdrachten aan de orde is gekomen.
Uiteraard moet je behandelde ontwerptechnieken voor algoritmes ook op nieuwe problemen kunnen toepassen.

Opgaven

Tijdens werkcolleges zijn opgaven gemaakt, soms op papier en soms achter de computer. Deze opgaven zijn hierboven in de tabel opgenomen, maar zijn ook tijdens het werkcollege uitgedeeld.

Tweede Werkcollege

Tijdens het tweede werkcollege is er een practicumopdracht gedaan in de computerzaal Paleistuin. Het skeletprogramma staat hier. Volg de volgende stappen om te beginnen:

Pak het skeletprogramma uit (onder Linux kan dat bijvoorbeeld met "tar xvfz practicum2012.tgz").
Ga naar de directory "practicum2012" (onder Linux kan dat bijvoorbeeld met "cd practicum2012").
Bekijk de gewenste file "readmewindows.txt" of "readmelinux.txt" voor de preciese bedoeling en werking van het programma.

De opgaven staan hierboven in de tabel met het programma van colleges en werkcolleges. Bewerk "boom.cc" zoals aangegeven in de twaalf opgaven. In dit bestand kunnen vanaf regel 327 de functies gevonden worden die moeten worden aangepast.

De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen de file "readmewindows.txt" of "readmelinux.txt".

Programmeeropdrachten

Bij dit college moesten drie programmeeropdrachten (in C++) gemaakt worden, waarbij de nadruk lag op het toepassen van de op college besproken probleemoplossingsmethoden. De opdrachten moesten alle drie voldoende zijn (>=6). Programmeerwerk mocht in tweetallen worden gemaakt. De opdrachten dienden op de deadlines te worden ingeleverd. Anders ging er in principe per week te laat inleveren een punt van het cijfer af.

Studenten die vorig studiejaar alle drie programmeeropdrachten hadden afgerond hoefden het programmeerwerk dit jaar niet opnieuw te doen. Ouderejaars studenten die het practicum helemaal niet of slechts gedeeltelijk hebben gedaan, moesten contact opnemen met de docent: rvvliet(at)liacs(dot)nl. Deelresultaten blijven niet automatisch geldig.

Meer informatie, zoals over het schrijven van het verslag in LaTeX, is hier te vinden.

Voor vragen/hulp bij de programmeeropdrachten kun je terecht bij Jan van Rijn: janvanrijn(at)gmail(dot)com. (nieuw email-adres, want mail op het liacs-adres bleef soms hangen...)

Eventuele opmerkingen of tips bij de opdrachten zullen hier worden bekendgemaakt.

Cijfers programmeeropdrachten

Nadat de opdrachten waren nagekeken, zijn hier de cijfers bekend gemaakt (bijgewerkt tot en met 20 augustus 2012, alles is nu nagekeken).

Eindcijfer

Vanaf studiejaar 2009/2010 telt het programmeerwerk, net als bij Programmeermethoden, mee voor het eindcijfer. Het eindcijfer wordt voor twee derde bepaald door het tentamencijfer, en voor een derde door het programmeerwerk. Zowel programmeerwerk als tentamen moeten daarbij voldoende zijn.

Tentamen

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Het tentamen is geweest op dinsdag 12 juni 2012. U kunt het hier nog bekijken. Dit tentamen is nagekeken. De uitwerking van de docent (8 pagina's, genummerd 1 t/m 9) is ook beschikbaar. Het nagekeken werk is beschikbaar voor de studenten.
Op de voorafgaande donderdag, 7 juni 2012, was er een `vragenuur'. Hierbij konden vragen gesteld worden over de tentamenstof, die tijdens het leren naar boven waren gekomen.
Het hertentamen is geweest op dinsdag 31 juli 2012. U kunt het hier nog bekijken. Ook dit tentamen is nagekeken. Het nagekeken werk is beschikbaar voor de studenten.

U vindt alle cijfers, inclusief de eindcijfers, hier. Wie het tentamen wel haalt, maar het programmeerwerk niet heeft afgerond, krijgt (nog) geen eindcijfer.

De tentamens van 2010 en 2011 zijn hieronder te vinden, alsmede uitwerkingen van de mei/juni-tentamens.

Tentamen van juni 2010, met uitgebreide uitwerking en bijbehorende toestandactieruimte,
Tentamen van augustus 2010.
Tentamen van mei 2011, met uitgebreide uitwerking en bijbehorende toestandactieruimte en state space tree,
Tentamen van augustus 2011.

Vragen en/of opmerkingen kunnen worden gestuurd naar: rvvliet(at)liacs.nl.

Laatste wijziging: 10 maart 2016 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/algoritmiek_vj2012/

Zie de website van Algoritmiek 2010/2011 voor het toenmalige programma en bijbehorende behandelde stof en opgaven.