LET OP: Eerstejaars studenten Informatica en Economie volgen het vak in Den Haag. Deze website (www.liacs.nl/home/graaf/ALGO) is bedoeld voor de studenten die in Leiden het vak volgen. De Haagse studenten hebben een eigen website, die wordt bijgehouden door de docent van het vak in Den Haag, drs. R. van Vliet.
Assistentie bij de werkgroep en het practicum wordt verleend door Bas van Stein en Iris Hupkens.
De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 174. De bijbehorende werkcolleges vinden plaats op donderdagen van 13.45 uur tot 15.30 uur, in zaal 174 of een van de computerzalen (302/304). Het eerste college is op vrijdag 10 februari 2012; het eerste werkcollege is op donderdag 16 februari.
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).
Voor globale informatie over het vak in studiejaar 2011-2012 wordt men verwezen naar de algemene webpagina.
In het studiejaar 2011/2012 wordt 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.
De bij het college behorende sheets worden ook via deze website beschikbaar gesteld. 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 telkens de definitieve versie van de sheets hieronder geplaatst.
| Datum (vrijdag) | Onderwerp | Sheets | Boek | Werkcollege | 4 februari | Introductie | sheets1 | 1.1, 1.2, 1.4 (t/m graafrepresentaties) | geen | 11 februari | Grafen en bomen | sheets2 | 1.4 | opgaven1 | 18 februari | Toestand-actie-ruimte | sheets3 | sheets | opgaven2 | 25 februari | geen college | --- | --- | geen werkcollege | 4 maart | Complexiteit; brute force | sheets4 | 2.1-3, 3.1-3 | opgaven3 | 11 maart | Exhaustive search, backtracking | sheets5 | 3.4, 12.1 (dames), sheets | programmeeropdracht 1 | 18 maart | Backtracking, Verdeel en heers | sheets6 | 12.1, 4.1-2 | opgaven5 | 25 maart | Verdeel en heers | sheets7 | 4.3-6, 5.1, 5.5 | opgaven6 | 1 april | Rest decrease and conquer, dynamisch programmeren | sheets8 | sheets, inleiding H.8 | programmeeropdracht 2 | 8 april | Dynamisch programmeren | sheets9 | 8.1, sheets, 8.4 | opgaven8 | 15 april | Gretige algoritmen, Dijkstra | sheets10 | inleiding H.9, sheets, 9.3 | opgaven9 | 22 april | geen college (Goede Vrijdag) | --- | --- | programmeeropdracht 3 | 29 april | Dijkstra, branch and bound | sheets11 | 12.2 | opgaven11 | 6 mei | Heap, heapsort, branch and bound (rest) | sheets12 | 6.4, sheets | geen werkcollege | 13 mei | Bespreken oud tentamen | tentamen augustus 2010 | alle stof | opgaven12 |
|---|
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. Deelresultaten blijven niet automatisch geldig.
DE drie programmeeropdrachten voor studiejaar 2010/2011 zijn hieronder nog te vinden.
Er zijn enkele testgevallen beschikbaar, waarmee je
kunt controleren of je eigen programma goed werkt.
Voor de twee gevallen die je in je verslag moet analyseren (4 bij 4 en 2 bij 7)
moet je beredeneren/bewijzen wat het minimale aantal te plaatsen lopers is. Het
antwoord dat je programma geeft is geen bewijs. Je moet dus "met de hand"
laten zien dat 2 resp.3 lopers minimaal nodig zijn. Zie de opdracht voor hoe je
dat kunt doen.
De invoerfiles (zie de opgave) moeten in een standaardvorm staan i.v.m. het
testen van de werking. De roddels zijn genummerd 1 t/m n (net als de personen).
De file met gegevens over wie bij aanvang welke roddels kent bevat n rijen,
met in rij i de nummers van de roddels die persoon i kent, oplopend gesorteerd
en gescheiden door spaties. Na de laatste roddel staat ter afsluiting
een -1. Een mogelijke invoer in het juiste formaat is
deze. In dit voorbeeld kennen de
personen met een oneven nummer alleen hun eigen roddel,
en degenen met een even nummer behalve hun eigen roddel nog drie andere.
Overigens zal je programma hoogstwaarschijnlijk dit voorbeeld niet aankunnen,
omdat het te groot is. Merk op dat in principe in elke stap (1/2)n(n-1)
verschillende gesprekken mogelijk zijn, en dat er bij optie 1 2n-4 stappen nodig
kunnen zijn om een oplossing te vinden. Weliswaar hoeft niet alles bekeken te
worden vanwege de backtracking, maar het geeft wel aan waarom zelfs klein
lijkende gevallen in de praktijk te lang duren.
Voor variant 2 heeft de invoerfile een soortgelijke vorm. Deze bevat dan voor
elke persoon i de nummers van degenen met wie i beslist niet mag bellen,
werderom gescheiden door spaties en afgesloten met een -1. Merk op dat als i
niet met j wil/mag/kan bellen, j ook niet met i kan bellen.
Inmiddels zijn er enige
testvoorbeelden
beschikbaar.
Natuurlijk moet je bij je programmacode en verslag zes andere voorbeeldinvoeren inleveren!
Er zijn enkele
testresultaten
beschikbaar, waarmee je kunt controleren of je eigen programma goed werkt.
In de testfile staat alleen het maximale aantal schapen vermeld waarmee de herder
in de hoofdstad aankomt, en niet hoeveel hij er bij elke brug achterlaat. Dit omdat die aantallen
niet uniek bepaald zijn, en dus afhangen van het geschreven programma.
Uiteraard zul je tien andere instanties moeten opnemen in
je verslag,
De tentamens van 2010 en 2011 zijn hieronder te vinden, alsmede uitwerkingen van de mei/juni-tentamens.
Vragen en/of opmerkingen kunnen worden gestuurd naar: graaf@liacs.nl.
19 januari 2012 - http://www.liacs.nl/home/graaf/ALGO/