Algoritmiek (Informatica en Economie),

voorjaar 2016

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, Jeannette 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 2016 is de docent voor Informatica en Economie (terug van weggeweest) Rudy van Vliet. Als hij in gebouw Stichthage in Den Haag is, is zijn werkkamer 12.58, op de twaalfde verdieping. In het Snellius in Leiden is zijn kamer 124. Zijn email-adres is rvvliet(at)liacs(dot)nl.
Assistentie bij de werkgroep en het practicum: Jeroen van den Heuvel, email: jeroenvandenheuvel(at)live(dot)nl

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 4 februari 2016, de laatste op donderdag 26 mei 2016. Op de donderdagen 10 maart, 21 april en 5 mei 2016 zijn er om diverse redenen geen colleges van dit vak.

Zowel hoorcollege als werkcollege is in principe in zaal Benoordenhout in gebouw Stichthage. Alleen op vier donderdagen vindt het werkcollege plaats in de computerzaal.

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. Het vak behandelt diverse algemene algoritmische methoden voor het oplossen van problemen, alsmede enkele bekende algoritmen zoals het algoritme van Dijkstra. Elke methode wordt geillustreerd aan de hand van bekende of minder bekende voorbeelden. Probleemoplossingsmethoden die worden behandeld zijn o.a.:

toestand-actie-ruimte/state space tree (als hulp bij het probleemoplossen),
brute force,
exhaustive search (waaronder depth first search en breadth first search),
verdeel en heers,
dynamisch programmeren,
gretige algoritmen,
backtracking
en branch-en-bound.

Verder wordt de sorteermethode heapsort behandeld, en komt het begrip tijdcomplexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken) zijdelings aan de orde.

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

Doelstelling

Het leren toepassen van diverse probleem oplossingsmethoden.
Het leren en bestuderen van enige concrete algoritmen.
Het ontwerpen van algoritmen.

Materiaal

In het studiejaar 2015/2016 wordt evenals in de voorgaande jaren 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 slides komen ook via deze website beschikbaar.

Programma

Het programma van colleges en werkcolleges 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. Bovendien kan men hier de bij het werkcollege behandelde opgaven vinden.

Datum	Onderwerp	Slides	Boek	Werkcollege
4 februari	Introductie	sheets1	1.1, 1.2, 1.4 (t/m graafrepresentaties)	opgaven1, antwoorden opgaven 7-9,
11 februari	Grafen en bomen	sheets2	1.4	opgaven2, zie beneden voor uitwerkingen en uitvoer
18 februari	Toestand-actie-ruimte	sheets3, Kannenprobleem (Die Hard)	sheets, 4.5 (subpar `Searching and Insertion in a BST'), 4.5 (subpar `The Game of Nim') en 6.6 (subpar `Reduction to Graph Problems')	opgaven3, antwoorden opgaven 1-3,5 (presentatie Jan van Rijn uit 2011), antwoord opgave 4, toestand-actie-ruimte bij opgave 4
25 februari	Complexiteit, brute force	sheets4	2.1-3; 3 inl., 3.1-3	Programmeeropdracht 1
3 maart	Exhaustive search, backtracking	sheets5	3.4, 3.5; sheets; 12 inl. 12.1	opgaven5, antwoorden5
17 maart	Backtracking, verdeel en heers	sheets6	12.1; 5 inl., 5.1, 5.2, 4 inl., 4.1	opgaven6, antwoord van opgave 2, antwoorden van opgaven 1 en 6, antwoord opgave 7 in sheets7, antwoord van opgave 8
24 maart	Verdeel en heers	sheets7	4.1, 4.4, 5.3-5.5	opgaven8, antwoorden opgaven 2a, 5, 6a, 9 (presentatie Jan van Rijn uit 2011, met afwijkende nummering),
31 maart	Rest decrease and conquer, dynamisch programmeren	sheets8	sheets; 8 inl.	Programmeeropdracht 2
7 april	Dynamisch programmeren	sheets9	scan paragraaf 8.1 uit editie 2 van boek; sheets; 8.2, voorbeeld 2 in 8.1	opgaven9, antwoorden opgaven 3, 4, 5ac (presentatie Jan van Rijn uit 2011, met afwijkende nummering),
14 april	Dynamisch programmeren, gretige algoritmen, Kortste pad met BFS	sheets10.1, sheets10.2	sheets, 9 inl.	opgaven10, antwoord opgave 4, antwoorden van opgaven 5-7
28 april	Gretige algoritmen, Algoritme van Dijkstra, Branch & Bound	sheets11	sheets, 9.2 t/m blz 353, 9.3, 12.2	Programmeeropdracht 3
12 mei	Branch & bound	sheets12	12.2	opgaven12
19 mei	heapsort	sheets13	6.4	opgaven12, antwoord van opgaven 5-7
26 mei	oud tentamen oefenen	tentamen van juli 2015		--

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

Tweede werkcollege

Tijdens het tweede werkcollege is er een practicumopdracht gedaan in de computerzalen op Stichthage. Daarvoor kon je gebruik maken van het volgende framework. Volg de volgende stappen om te beginnen:

Pak het framework uit (onder Linux kan dat bijvoorbeeld met "tar xvfz bomenpracticum2016.tar.gz").
Ga naar de directory "bomenpracticum" (onder Linux kan dat bijvoorbeeld met "cd bomenpracticum").
Bekijk het bestand "readmelinux.txt" voor de precieze 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.

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

Programmeeropdrachten

Bij het vak horen drie programmeeropdrachten in de programmeertaal C++, in elk waarvan een besproken oplossingsmethode toegepast moet worden om een gegeven probleem op te lossen.

De opdrachten moeten alle drie voldoende zijn (>=5.5). 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. Als plagiaat wordt geconstateerd, krijgen de betrokken teams geen cijfer voor de betreffende opdracht en dit collegejaar ook geen mogelijkheid om de opdracht alsnog te doen. Meer informatie hierover...

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.

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

Toetsing

Schriftelijk tentamen aan het eind van het semester. Het eindcijfer van het vak is een gewogen gemiddelde van de cijfers voor het tentamen (twee derde) en de programmeeropdrachten (samen een derde). Zowel tentamen als (alle) programmeeropdrachten moeten voldoende zijn.

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

Tentamens

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Er zijn twee tentamens geweest:
Eerste tentamen: dinsdag 7 juni 2016, 14:00-17:00 uur, in zaal Bezuidenhout in Stichthage.
Hertentamen: donderdag 7 juli 2016, 10:00-13:00, in zaal 407-409 in het Snellius. Beide tentamens zijn nagekeken. Voor de cijfers, inclusief eindcijfers, zie het overzicht met alle cijfers.
Je kunt je uitwerkingen, met opmerkingen van de docent, inzien op zijn kamer.
Beide tentamens zijn onderaan deze pagina terug te vinden. Van het eerste tentamen is er ook een handgeschreven uitwerking.

Vragenuur

Op donderdag 2 juni 2016 was er vanaf 11.15 uur een vragenuur voor het tentamen, in zaal Noordeinde. Daarbij kon je die vragen stellen die opgekomen waren bij het leren voor het tentamen.

Oude tentamens

Tentamen van juli 2016.
Tentamen van juni 2016, met de handgeschreven uitwerking van de docent.
Tentamen van juli 2015.
Tentamen van juni 2015 met een uitwerking.
Tentamen van juli 2014, met een uitwerking.
Tentamen van juni 2014, met een uitwerking.

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

Vragen en/of opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 26 augustus 2016 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/