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.M. 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 mogelijk de inleverdata voor de practicumopdrachten
worden anders.
In het voorjaar van 2011 is de docent voor Informatica en Economie
Rudy van Vliet.
De colleges zijn in het algemeen op donderdagen van 11.15 tot 13.00 uur.
LET OP:
De laatste twee colleges zijn op dezelfde tijd, maar dan op
de dinsdagen 3 en 10 mei 2011.
De bijbehorende werkcolleges vinden plaats op dezelfde dagen als de colleges,
maar dan van 13.45 tot 15.30 uur. Inderdaad, de laatste twee werkcolleges
zijn dus op de dinsdagen 3 en 10 mei 2011.
Het eerste college is op donderdag 3 februari 2011.
In de week van 25 - 29 april 2011 zijn er geen colleges van dit vak.
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) en heapsort.
Voor globale informatie over het vak in studiejaar 2010-2011
wordt men verwezen naar de
algemene
webpagina.
De bij het college behorende sheets zijn ook via deze website beschikbaar.
Meestal zullen de sheets al voor het college op deze webpagina
verschijnen: er kunnen daarin dan nog kleine veranderingen
worden aangebracht, afhankelijk van hoe ver we op college komen.
Na afloop van het college wordt de definitieve versie van de sheets hieronder
geplaatst.
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.
De slides bij de hoor- en werkcolleges die je hierboven kunt vinden.
Alleen slides 14 en 17 van hoorcollege 4 (over complexiteit-en-recursie)
hoef je niet te kennen.
De hierboven vermelde delen uit 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 kunnen via deze
website worden verkregen, maar zullen ook tijdens (werk)college worden
uitgedeeld.
Tweede Werkcollege
Tijdens het tweede werkcollege zal er een practicumopdracht worden gedaan
in de computerzaal Paleistuin.
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 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.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: jvrijn(at)liacs.nl.
Cijfers programmeeropdrachten
Zodra de opdrachten zijn nagekeken, zullen
hier
de cijfers worden bekend gemaakt
(bijgewerkt tot en met 16 juni 2011).
Programmeerwedstrijd op dinsdag 26 april
Op dinsdagmiddag 26 april 2011 is er een programmeerwedstrijd
georganiseerd in het Snellius. Dit was een verplichte activiteit
voor eerstejaars studenten Informatica, maar ook anderen mochten
eraan deelnemen. Studenten Informatica en Economie konden hierbij
bonuspunten verdienen voor het vak Algoritmiek. Concreet:
Het programma voor de programmeerwedstrijd was als volgt:
13:45 verzamelen in zaal 174
14:00 - 16:30 wedstrijd in computerzaal 302-304 (vier opgaven, en teams
van maximaal twee personen)
17:00 uitslag / prijsuitreiking in zaal 174.
Voor elke opgave waarvoor een goede oplossing werd ingeleverd konden
de betreffende studenten 1 punt bonus voor een van de drie
programmeeropdrachten krijgen. Het was mogelijk om hiermee een onvoldoende
voor een opdracht op te werken naar een voldoende. Omdat er drie
programmeeropdrachten zijn, en de programmeeropdrachten samen voor
een derde meetellen in het eindcijfer van het vak, betekent zo'n
bonus een verhoging van het eindcijfer met (maximaal) een negende punt.
Met vier opgaven tijdens de wedstrijd bedraagt de maximale bonus
voor het eindcijfer dus vier-negende punt.
Voor meer informatie over de regels van de wedstrijd, kijk
hier.
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
Het tentamen heeft plaatsgevonden op dinsdag 31 mei 2011.
De opgaven van dit tentamen en een nette uitwerking vindt u nog verderop.
Het hertentamen heeft plaatsgevonden op dinsdag 2 augustus 2011,
in het Snellius in Leiden.
De opgaven van dit hertentamen vindt u nog verderop.
Beide tentamens zijn nagekeken!
U vindt de cijfers
hier,
inclusief eindcijfers.
Wie het tentamen wel gehaald heeft, maar het programmeerwerk niet
heeft afgerond, krijgt (nog) geen eindcijfer.
Het nagekeken werk is beschikbaar voor de studenten.
De tentamens van 2010 en 2011 zijn hieronder te vinden, alsmede
uitwerkingen van de mei/juni-tentamens.
In het studiejaar 2010/2011 wordt, evenals in
voorgaande jaren, gebruik 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.