Algoritmiek (Informatica en Economie),

voorjaar 2013

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. de Graaf.

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 zijn anders.

In het voorjaar van 2013 is de docent voor Informatica en Economie (net als de afgelopen twee 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.
Assistentie bij de werkgroep en het practicum wordt (eveneens: net als de afgelopen twee jaar) verleend door Jan van Rijn.

De colleges zijn op donderdagen van 11.15 tot 13.00 uur. De bijbehorende werkcolleges vinden plaats op dezelfde dagen als de colleges, maar dan van 13.45 tot 15.30 uur. De eerste colleges zijn op donderdag 7 februari 2013, de laatste op donderdag 30 mei 2013. Op de donderdagen 21 en 28 maart, 25 april en 9 mei 2013 zijn er om diverse redenen geen colleges van dit vak.

Zowel hoorcollege als werkcollege is in principe in zaal Noordeinde. Alleen op vier donderdagen vindt het werkcollege plaats in de computerzaal Paleistuin. En op donderdag 18 april is (alleen) het hoorcollege in zaal Plein.

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 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), depth first search, breadth first search en heapsort.

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

Materiaal

In het studiejaar 2012/2013 wordt evenals in het voorgaande jaar 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 nog een tweede editie van het boek heeft, is 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 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 VOORJAAR 2013

Datum	Onderwerp	Sheets	Boek	Werkcollege
7 februari	Introductie	sheets1, en kleine versie	1.1, 1.2, 1.4 (t/m graafrepresentaties)	opgaven1, antwoorden opgaven 7, 8, 9, presentatie Jan (met pseudocode) (uit 2012)
14 februari	Toestand-actie-ruimte	sheets2, en kleine versie, Kannenprobleem (Die Hard)	sheets, 4.5 (subpar `The Game of Nim') en 6.6 (subpar `Reduction to Graph Problems')	opgaven2, presentatie Jan (uit 2011)
21 februari	Grafen en bomen	sheets3, en kleine versie	1.4	opgaven3
28 februari	Complexiteit, brute force	sheets4, en kleine versie	4.5 (subpar `Searching and Insertion in a BST'), 2.1-3; 3 inl., 3.1-3	Programmeeropdracht 1
7 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)
14 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)
21 maart	geen college	--	--	geen werkcollege
28 maart	geen college	--	--	geen werkcollege
4 april	Verdeel en heers	sheets7, en kleine versie	4.1, 4.4, 5.3-5.5	Programmeeropdracht 2
11 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)
18 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)
2 mei	Dynamisch programmeren, Gretige algoritmen, Dijkstra	sheets10, en kleine versie	9 inl.; 9.2 t/m blz. 353, 9.3; sheets	opgaven10/11, presentatie Jan (geen uitwerkingen) (uit 2011), antwoorden opgaven 4 en 5
16 mei	Gretige algoritmen, Dijkstra, Branch & bound	sheets11, en kleine versie	9.3, sheets, 12.2	Programmeeropdracht 3
23 mei	Branch & bound; heapsort	sheets12, en kleine versie	12.2; 6.4	opgaven12, geen nette uitwerking
30 mei	Oefenen oud tentamen	Tentamen van augustus 2011	alle stof	Bespreken oud tentamen

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

De hierboven gegeven slides bij de hoor- en werkcolleges. Alleen slides 18 t/m 21 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.
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 worden opgaven gemaakt, soms op papier en soms achter de computer. Deze opgaven worden hierboven in de tabel opgenomen, maar zullen ook tijdens het werkcollege worden uitgedeeld.

Derde Werkcollege

Tijdens het derde 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 practicum2013.tgz").
Ga naar de directory "practicum2013" (onder Linux kan dat bijvoorbeeld met "cd practicum2013").
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 350 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 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). Programmeerwerk mag in tweetallen worden gemaakt. De opdrachten dienen op (of voor) de deadlines te worden ingeleverd. Anders gaat er in principe per week te laat inleveren een punt van het cijfer af.

Studenten die vorig studiejaar alle drie programmeeropdrachten hebben afgerond hoeven het programmeerwerk dit jaar niet opnieuw te doen. Ouderejaars studenten die het practicum helemaal niet of slechts gedeeltelijk hebben gedaan, moeten 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.

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

Cijfers programmeeropdrachten

Zodra de opdrachten zijn nagekeken, zullen hier hier de cijfers worden bekend gemaakt (bijgewerkt tot 3 juli 2013).

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 eerste tentamen is geweest op dinsdag 11 juni 2013, 10.00-13.00 uur, in zaal Bezuidenhout in Den Haag. U vindt het nog hieronder in het overzicht met oude tentamens, met de uitwerking van de docent. Dit tentamen is nagekeken. De cijfers van het tentamen, inclusief eindcijfers, vindt u hier.
Op de voorafgaande donderdag, 6 juni 2013, was er een `vragenuur', in zaal Noordeinde, van 13.45 tot maximaal 15:30. Hierbij konden vragen gesteld worden over de tentamenstof, die tijdens het leren naar boven waren gekomen.
Het hertentamen is geweest op woensdag 7 augustus 2013, 14.00-17.00 uur. U vindt het nog hieronder in het overzicht met oude tentamens. Ook dit hertentamen is nagekeken. De cijfers van het hertentamen, inclusief eindcijfers, vindt u hier. U kunt uw eigen uitwerkingen (met opmerkingen van de docent) ophalen op zijn kamer in Leiden.

Wie het tentamen wel haalt, maar het programmeerwerk niet heeft afgerond, krijgt (nog) geen eindcijfer.

Oude tentamens

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

Tentamen van mei 2011, met uitgebreide uitwerking en bijbehorende toestandactieruimte en state space tree,
Tentamen van augustus 2011,
Tentamen van juni 2012, met handgeschreven uitwerking van de docent (8 pagina's, genummerd 1 t/m 9),
Tentamen van juli 2012,
Tentamen van juni 2013, met handgeschreven uitwerking van de docent,
Tentamen van augustus 2013.

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

Laatste wijziging: 3 augustus 2015 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/

Zie de website van Algoritmiek, voorjaar 2012 voor het toenmalige programma en bijbehorende behandelde stof en opgaven.