Algoritmiek 2008

Op deze pagina staat wat informatie over de werkgroep Algoritmiek, het practicum en de programmeeropgaven. Als er iets mist of onduidelijk is, laat het mij weten. Zie ook de pagina voor het vak zelf. De pagina van het jaar 2007 is ook nog beschikbaar.

Practicum

Zie 2007 voor het practicum.

Programmeeropgave 1

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 28 maart.

Werkcolleges: Aangezien dit een redelijk uigebreide opgave is, verdient het aanbeveling om het een en ander gestructureerd aan te pakken. Daarom zullen we in het eerste werkcollege de nadruk leggen op de volgende punten:

  • Het inlezen van een graaf en het implementeren van een geschikte klasse.
  • Het omzetten van een bord naar een graaf.
  • Het schrijven van debug-functies die een representatie van de graaf en een labeling afdrukken.
  • Het implementeren van een klasse voor de opslag van de bereikbare toestanden.
  • Het inlezen van een labeling (nodig voor het 2e gedeelte van de opdracht).
  • Het invoeren van een zet en het spelen van het spel tot de gebruiker wil stoppen.

Hier onder staat een tabel met invoer en mogelijke uitvoer.

Invoer Uitvoer
2x2(1) 2x2(1)
2x2(2) 2x2(2)
2x2(3) 2x2(3)
2x3 2x3
3x3-1(1) 3x3-1(1)
3x3-1(2) 3x3-1(2)
3x3 3x3

Bij de eerste 4 tests wordt de lijst met bereikbare toestanden ook afgedrukt, dit is alleen ter controle. Het is niet nodig om dit zelf te doen.

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken.

Programmeeropgave 2

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 25 april.

Werkcolleges: Het bestandsformaat is als volgt:

  • Regel 1: Het aantal bellers (n).
  • Regel 2: De optie (1 of 2).
  • Regel 3 - (n + 3)'': Voor optie 1: ''n regels met per regel:
    • Het aantal roddels dat deze beller kent.
    • De lijst met roddels.
  • Regel 3 - (n + 3)'': Voor optie 2: ''n regels met per regel:
    • Het aantal mensen waar deze beller een hekel aan heeft.
    • De lijst met mensen waar deze beller een hekel aan heeft.

Neem aan dat bij optie 2 de hekel wederzijds is. De invoer zal dus symmetrisch zijn; als op de regel corresponderend met beller x'' een ''y staat, dan staat op de regel corresponderend met beller y'' ook een ''x.

Nu volgt een tabel met invoer en mogelijke uitvoer voor optie 1 van het programma.

Invoer Uitvoer
4(1) 4(1)
4(2) 4(2)
4(3) 4(3)
5(1) 5(1)
5(2) 5(2)

En hier een tabel met invoer en mogelijke uitvoer voor optie 2 van het programma.

Invoer Uitvoer
4(1) 4(1)
4(2) 4(2)
5(1) 5(1)
5(2) 5(2)
7 7

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken.

Programmeeropgave 3

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 19 mei.

Werkcolleges: We geven nu een tabel met mogelijke invoer en mogelijke uitvoer, de opbouw van het invoerbestand is als volgt:

  • Regel 1: De optie (0 of 1):
    • 0: Gebruik de bottum up zoekmethode.
    • 1: Gebruik de top down zoekmethode.
  • Regel 2: Het aantal testgevallen n.
  • Regel i + 3'': Strings van testgeval ''i (0 ≤ i < n).
Bottom up Top down
Invoer Uitvoer Invoer Uitvoer
invoer 1.1 uitvoer 1.1 invoer 1.2 uitvoer 1.2
invoer 2.1 uitvoer 2.1 invoer 2.2 uitvoer 2.2
invoer 3.1 uitvoer 3.1 invoer 3.2 uitvoer 3.2
invoer 4.1 uitvoer 4.1 invoer 4.2 uitvoer 4.2

Let er op dat bij de uitvoer de lengte van de langste gemeenschappelijke deelrij wel vast staat, maar dat de langste gemeenschappelijke deelrij zelf nagenoeg nooit uniek is.

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken.