Algoritmiek (Leiden),

voorjaar 2017

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

LET OP: Deze website is alleen bedoeld voor de eerstejaars studenten Informatica, Informatica en Biologie en studenten die een dubbele propedeuse Wiskunde/Informatica doen. Zij volgen het vak in Leiden. De Haagse studenten (studenten Informatica en Economie) hebben een eigen website.

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

In het voorjaar van 2017 is de docent Rudy van Vliet. In het Snellius in Leiden is zijn kamer 140. Zijn email-adres is rvvliet(at)liacs(dot)nl.
Assistentie bij de werkgroep: Sebastiaan Brand.
Extra assistentie bij het practicum: Hanjo Boekhout (hanjo(dot)boekhout(at)gmail(dot)com), David Nieuwenhuizen, Ruben van der Waal.

De colleges zijn op vrijdagen 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 vrijdag 3 februari 2017, de laatste op vrijdag 19 mei 2017. Op de vrijdagen 17 maart, 14 april en 5 mei 2017 zijn er om diverse redenen geen colleges van dit vak.

Zowel hoorcollege als werkcollege is in principe in collegezaal B2 in het Snellius. Alleen op vier donderdagen vindt het werkcollege plaats in de computerzalen.

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

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

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

Doelstelling

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

Materiaal

In het studiejaar 2016/2017 wordt evenals in de voorgaande jaren gebruik gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, third edition (Pearson, 2012). Of de internationale editie van hetzelfde boek (ISBN: 978-0-273-76411-3).

De bij het college behorende slides komen ook via deze website beschikbaar.

Programma

Het programma van colleges en werkcolleges is hieronder nog na te kijken. Voor elke week wordt vermeld welke onderwerpen aan de orde zijn gekomen, met de bijbehorende hoofdstukken uit het boek en de gebruikte slides. Op de laatste pagina van de slides staat overigens doorgaans ook welke stof uit het boek bij het betreffende college hoort. Ten slotte vind je hieronder de bij het werkcollege behandelde opgaven, met (soms) antwoorden.

Datum	Onderwerp	Slides	Boek	Werkcollege
3 februari	Introductie	slides1	1.1, 1.2, 1.4 (t/m graafrepresentaties)	opgaven1, antwoorden opgaven 7-9,
10 februari	Grafen en bomen	slides2	1.4, 4.5 (subpar `Searching and Insertion in a BST')	opgaven2
17 februari	Toestand-actie-ruimte	slides3, Kannenprobleem (Die Hard)	slides, 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
24 februari	Complexiteit, brute force	slides4	2.1-3; 3 inl., 3.1-3	Programmeeropdracht 1
3 maart	Exhaustive search	slides5	3.4, 3.5; slides	opgaven5, antwoorden5
10 maart	Backtracking	slides6	12 inl., 12.1, 5 inl, 5.1	opgaven6, antwoorden opgaven 1-6 werkcollege 6, antwoord opgave 7
24 maart	Verdeel en heers	slides7	4 inl., 4.1, 4.4, 5.2-5.5	opgaven7, enkele antwoorden
31 maart	Rest decrease and conquer, dynamisch programmeren	slides8	slides; 4.5 (inl + Binary Search Tree), 8 inl.	Programmeeropdracht 2
7 april	Dynamisch programmeren	slides9	slides; 8.2, voorbeeld 2 in 8.1	opgaven9, antwoorden opgaven 3, 4, 5ac (presentatie Jan van Rijn uit 2011, met afwijkende nummering)
21 april	Gretige algoritmen, algoritme van Dijksta	slides10	sheets, 9 inl., 9.2 t/m blz. 353, 9.3	opgaven10, antwoorden van opgaven 4-6
28 april	Algoritme van Dijkstra, heapsort	slides11	slides, 9.3, 6.4	Programmeeropdracht 3
12 mei	Branch & bound	sheets12	12.2	opgaven12
19 mei	oud tentamen oefenen	tentamen van juli 2016		--

Tentamenstof

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. (wordt in loop van semester opgebouwd).
De hierboven vermelde delen uit de derde editie van het boek van Anany Levitin. (wordt in loop van semester opgebouwd).
De opgaven die bij het werkcollege zijn behandeld, en die je hierboven nog kunt vinden (wordt in loop van semester opgebouwd).
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, meestal op papier, 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 in het Snellius. 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 bomenpracticum2017.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. 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 over te laat, niet voldoende en plagiaat...

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.

Alle opdrachten zijn nagekeken, en ook de herkansingen. U vindt de cijfers in het overzicht van alle cijfers.

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

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 (>=5.5) zijn.

Wie het tentamen niet haalt, krijgt het (onvoldoende) tentamencijfer als eindcijfer. Wie het tentamen wel haalt, maar de programmeeropdrachten niet (allemaal) heeft afgerond, krijgt nog geen eindcijfer. In dit laatste geval blijft het voldoende tentamencijfer staan totdat het programmeerwerk is afgerond.

Tentamens

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Er zijn twee tentamens geweest:
Eerste tentamen: dinsdag 6 juni 2017, 14.00-17.00 uur.
Hertentamen: maandag 10 juli 2017, 14.00-17.00. in zalen 407/409 en 312 in het Snellius.
Beide tentamens zijn nagekeken. U vindt de resulterende tentamencijfers, inclusief eindcijfers, in het overzicht van alle cijfers. Je kunt je tentamen inzien bij de docent, op kamer 140 van het Snellius.
Beide tentamens zijn nog terug te vinden in het lijstje met oude tentamens onderaan deze pagina. Van het eerste tentamen staat er ook een uitwerking.

Vragenuur

Op donderdag 1 juni 2017 was er vanaf 13.45 uur een vragenuur voor het tentamen, in zaal B02 van het Snellius, samen met de Haagse studenten. Daarbij kon je dan die vragen stellen die opgekomen waren bij het leren voor het tentamen.

Oude tentamens

Tentamen van 10 juli 2017.
Tentamen van 6 juni 2017, met de handgeschreven uitwerking van de docent.
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.

Het vak Algoritmiek wordt al vele jaren gegeven. De vorige keer was in het voorjaar van 2016. De website van die keer vindt u hier. U vindt daar ook nog meer oude tentamens.

Vragen en/of opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 12 september 2017 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/voorjaar2017/leiden/