|
|
|
|
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.
Het skeletprogramma staat hier. Volg de
volgende stappen om te beginnen.
- Gebruik "tar -xzvf practicum.tgz" om het skeletprogramma uit
te pakken.
- Type "cd practicum".
- Type "make" om het practicum te compileren.
- Type "sh test.sh | less" om het practicum te draaien.
- Gebruik de 'up' en 'down' pijltjestoetsen om te
scrollen en 'q' om te stoppen.
De opgaven staan hier. Bewerk
"boom.cc" om de opgaven in het practicum te verwerken. In dit bestand
staat duidelijk aangegeven van waar tot waar aanpassingen gemaakt dienen te
worden.
Voor het 2e gedeelte van het practicum moet:
gebruikt worden.
De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Let er wel op
dat de bomen niet hoger mogen zijn dan 6 en dat de invoer een geldige
preordewandeling van een boom moet zijn. Het getal '0' is
gereserveerd voor het aangeven van een NULL pointer.
De preordestring "a00" geeft dus een boom met 'a' als wortel
en geen kinderen. De string "a0b00" geeft een boom met 'a'
als wortel en 'b' als rechterkind.
De uitwerkingen zijn hier te vinden, als
alles goed is, dan moet het programma een uitvoer hebben die sterk hierop lijkt. De uitvoer van het testprogramma
voor de zoekbomen moet hierop lijken.
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.
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.
Cijfers opgave 1:
| Naam | Cijfer |
| Blankevoort / Zomervrucht | 9 |
| de Bruijn | 7.5 |
| van den Broek | 9 |
| Dal | 7.5 |
| Everts | 7.5 |
| Feenstra | 7 |
| Heisterkamp / de Ruiter | - |
| Keizer / Vietor | 9 |
| Kortsmit / Rijk | 10 |
| ter Laak | 7.5 |
| Lo | * |
| van Luik | v |
| Nieuwenhuijsen | * |
| Mus | v |
| van Nieuwenburg | 8.5 |
| Rot / van der Weiden | v |
* : Nog niet volledig ingeleverd.
- : Onvoldoende en moet nog aanvullende werkzaamheden verrichten.
v : Goedgekeurd.
Hier staat een werkende implementatie, deze is
gebruikt bij het nakijken.
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.
En hier een tabel met invoer en mogelijke uitvoer voor optie 2 van het
programma.
Cijfers opgave 2:
| Naam | Cijfer |
| Blankevoort | 8 |
| de Bruijn | 9 |
| van den Broek / Lo | 9 |
| Dal | 8.5 |
| Everts | 7 |
| Feenstra | 9 |
| Heisterkamp / de Ruiter | * |
| Keizer / Vietor | 8.5 |
| Kortsmit / Rijk | 9.5 |
| ter Laak | 9 |
| van Luik | v |
| Mus | 6 |
| van Nieuwenburg | 9 |
| Rot / van der Weiden | 7 |
| Zomervrucht | 9.5 |
* : Nog niet volledig ingeleverd.
- : Onvoldoende en moet nog aanvullende werkzaamheden verrichten.
v : Goedgekeurd.
En voor de aardigheid een tabel met wat scores voor
dit invoerbestand
(/usr/bin/time -f %U ./executable < invoer).
| Naam | Tijd (in seconden) |
| ter Laak | 0.00 |
| van den Broek / Lo | 0.11 |
| Zomervrucht | 0.12 |
| Keizer / Vietor | 0.20 |
| de Bruijn | 0.23 |
| Mus | 0.39 |
| Kortsmit / Rijk | 1.83 |
| Blankevoort | 4.18 |
| Dal | 32.10 |
| van Nieuwenburg | 45.56 |
| Feenstra | 55.95 |
| Rot / van der Weiden | 513.49 |
| Everts | & |
| Heisterkamp / de Ruiter | * |
| van Luik | & |
* : Nog niet volledig ingeleverd.
- : Geen werkend programma.
& : Erg lang.
Hier staat een werkende implementatie, deze is
gebruikt bij het nakijken.
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).
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.
Cijfers opgave 3:
| Naam | Cijfer |
| Blankevoort | v |
| de Bruijn | * |
| van den Broek / Lo | 9 |
| Dal | 9.5 |
| Everts | 9 |
| Feenstra | 9 |
| Heisterkamp / de Ruiter | * |
| Keizer / Vietor | 7.5 |
| Kortsmit / Rijk | 9 |
| ter Laak | 9 |
| van Luik | 9.5 |
| Mus | 8.5 |
| van Nieuwenburg | 8.5 |
| Rot / van der Weiden | - |
| Zomervrucht | 10 |
* : Nog niet volledig ingeleverd.
- : Onvoldoende en moet nog aanvullende werkzaamheden verrichten.
v : Goedgekeurd.
Hier staat een werkende implementatie, deze is
gebruikt bij het nakijken.
|
|
