Algoritmiek 2010

Werkcolleges en Practica

Algemene Informatie

Op deze pagina staat informatie over de bij het vak Algoritmiek horende werkgroep, practicum en de programmeeropgaven. Mocht u vragen of opmerkingen hierover of over deze site hebben, dan wordt u verzocht contact op te nemen met de practicumbegeleider Tijn Witsenburg.
Het vak Algoritmiek wordt gegeven door Jeannette de Graaf en heeft ook een eigen website. De pagina van vorig jaar staat nog online op deze plek.

Tweede Werkcollege

Tijdens het tweede werkcollege zal er een practicumopdracht worden gedaan in de computerzalen. 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".
  • Bekijk de file "readme.txt" voor de preciese werking van het programma en de te gebruiken commando's.

    • De opgaven staan hier. Bewerk "boom.cc" om de opgaven in het practicum te verwerken. In dit bestand kunnen vanaf regel 300 de functies gevonden worden die moeten worden aangepast.

    De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie hiervoor de file "readme.txt".

    De uitwerkingen zijn hier te vinden. Als alles goed is, dan moet het script behorende bij het eerste deel een uitvoer hebben die sterk hierop lijkt. De uitvoer van het script voor het tweede deel moet hierop lijken.

    Practicum Algemeen

    Het practicum bestaat uit drie opgaven. Zodra deze bekend zijn, zullen ze onder andere hieronder te vinden zijn. Voor alledrie de opgaven dient een voldoende gehaald te worden om een cijfer voor het vak Algoritmiek te kunnen krijgen. Voor de opgaves dient zowel de code als ook een verslag te worden ingeleverd. Zorgt dat op beide duidelijk staat vermeld wie de makers zijn.

    Opgaven die op tijd zijn ingeleverd, worden ook snel nagekeken. Eventuele onvolkomenheden kunnen dan nog makkelijk worden aangepast. Het wordt derhalve sterk geadviseerd om alles op tijd in te leveren, zeker omdat er voor elke week die een opgave te laat wordt ingeleverd een punt wordt afgetrokken.
    De makkelijkste manier om een opgave op tijd in te leveren is door op tijd te beginnen met het maken ervan. Als je ervoor zorgt dat je het electronische gedeelte een week voor de deadline klaar hebt, heb je nog een week de tijd voor het verslag en enige uitloopruimte mocht het programmeren tegenvallen.

    Electronische Versie

    Inleveren van de code kan door deze te e-mailen naar dit adres. Denk bij het inleveren en programmeren aan de volgende zaken:

  • als je meerdere files inlevert, pak deze dan in middels 'tar'.
  • zorg dat je code duidelijk en begrijpelijk is door goed commentaar en begrijpelijke naamgeving.
  • code die niet compileert of een segmentation fault geeft bij uitvoer van de gegeven invoerfiles, wordt niet nagekeken.

    • Verslag

    Naast de code dient ook een verslag te worden ingeleverd. Deze kan worden ingeleverd in de 'Algoritmiek'-doos in de postkamer (kamer 156). Het verslag dient in LaTeX te worden gemaakt. Speciaal hiervoor is een LaTeX-bestand gemaakt dat jullie kunnen gebruiken als basis voor het verslag. Dit bestand en alle hulpbestanden zijn hier te vinden. Uitpakken kan met tar zvfx verslag_template.tgz. Wijzig de tekst in paper.tex en compileer naar een pdf-file met behulp van het commando make. Het resultaat van het basisprogramma is hier te vinden.

    Verdere tips met betrekking tot het verslag zijn:

  • Zorg dat het verslag netjes is en vermijd spel-, typ- en grammaticafouten.
  • Kijk eventueel bij LaTeX for Complete Novices of een handige LaTeX naslag-site.

    • Cijfers

    Zodra de opgaven zijn nagekeken, zullen hier de cijfers worden bekend gemaakt. Studenten die in een eerdere jaargang al (een deel van) het practicum voldoende hebben afgerond en dit graag voor dit jaar mee willen laten tellen, kunnen een verzoek hiertoe indienen per e-mail.

    De eindcijfers van het practicum (voor zover bekend) zijn:

    Naamcijfer Naamcijfer
    Antal5,5 Joris7,2
    Arjan7,1 Josse8,7
    Chris7,2 Mark7,1
    Duncan8,9 Matthijs9,3
    Erik7,0 Peter5,6
    Floris C.7,7 Pieter9,3
    Floris K.9,4 Sidar5,6
    Jan9,4 Thierry7,8
    Jan-Paul7,1 Tyron7,8
    Jasmin7,6 Xander5,5
    Johan8,7

    Let op! Het betreft hier de eindcijfers van het PRACTICUM en niet het algehele eindcijfer van het vak.

    Practicum Opgave 1

    De opgave is inmiddels bekend en kan hier gevonden worden. De deadline is vrijdag 12 maart. Dat klinkt misschien nog ver weg, maar vergis je niet. De eerste opgave is niet heel moeilijk, maar waarschijnlijk wel behoorlijk wat werk. Zorg dus dat je nu al begint, zodat je op het eind niet in de problemen komt. Nog niet alles dat je moet weten voor het maken van deze opgave is al behandeld in de colleges, maar dit zal uiteraard spoedig wel het geval zijn. Onderstaand schema is een goede leidraad voor het op tijd afkrijgen van de opdracht.

  • week 7 - class dawson, bord afdrukken, gebruiker zet, randomzet, check winst/verlies
  • week 8 - recursieve functie voor brute force gedeelte, toestand/actie-diagrammen
  • week 9 - functie voor best lijkende zet voor hele grote n
  • week 10 - verslag en volledig afmaken opdracht

    • Het is mogelijk om gebruik te maken van het feit dat slaan verplicht is en dat dit dus tot een voorspelbare vervolgstand, enkele zetten verderop, zal leiden. Dit kan het berekenen van de winnende zet aanzienlijk versnellen. Dit geldt zeker als je hierbij een extra datastructuur introduceert die de belangrijke elementen van het bord aanzienlijk simpeler opslaat. Je mag dat soort slimme trucs gebruiken, mits je rekening houdt met het volgende:

  • Het spel moet gewoon gespeeld kunnen worden.
  • Op elk moment van het spel moet de beste zet berekend kunnen worden.
  • Het berekenen van de beste zet moet hoe dan ook recursief gebeuren.
  • Alles wat je zelf toevoegt aan het programma moet in het verslag duidelijk uitgelegd worden.

    • LET OP: onder het kopje Practicum staat nieuwe informatie over het verslag.

    De cijfers voor opdracht 1 zijn bekend:

    Naam/Namencijfer Naam/Namencijfer
    Arjan en Dennis6,0 Joris en Chris8,5
    Jasmin en Niels6,5 Mark en Jan-Paul5,5
    Peter en Sidar4,0V Erik7,0
    Pieter en Matthijs8,5 Jan en Floris K.9,5
    Floris C.8,0 Joost en Sander5,0V
    Johan en Josse8,8 Tyron en Thierry9,0
    Xander en Antal3,0V Michiel9,3
    Leroy en David4,5A Duncan8,5

    Van cijfers waar een 'A' achter staat, dient de opdracht nog te worden aangevuld.
    Van cijfers waar een 'V' achter staat, is de opdracht (inmiddels) voldoende en hoeft deze dus niet te worden aangevuld.

    Practicum Opgave 2

    Zodra de opgave is inmiddels bekend en hier te vinden. De deadline is vrijdag 16 april. Let op de volgende zaken:

  • Als je te laat inlevert, gaat er 1 punt per week dat je te laat bent van je cijfer af.
  • Inleveren betekent het inleveren van de electronische versie van je programma, het papieren verslag en een uitdraai van de listing.
  • Het programma moet compileerbaar zijn op Linux. Als het programma uit meerdere bestanden bestaat, moet een makefile worden meegeleverd.
  • Het verslag moet duidelijk een verslag zijn. Zie hiervoor ook bij Practicum onder het kopje 'verslag'.
  • Voor deze opdracht is het handig om twee arrays te gebruiken met hierin voor alle acht zetten wat de horizontale en verticale verschuiving is. In dat geval kan je namelijk steeds met een handige for-lus alle richtingen uitzoeken.

    • De opgaves zijn nagekeken en hieronder staan de cijfers:
    Naam/Namencijfer Naam/Namencijfer
    Jasmin en Niels7,8 Mark en Jan-Paul8,5
    Peter en Sidar7,0 Erik 6,5
    Pieter en Matthijs9,3 Jan en Floris K.9,8
    Floris C.8,5 Joost en Sander8,5
    Johan en Josse8,0 Tyron en Thierry7,0
    Xander en Antal5,8 Duncan9,3
    Leroy en David7,5 Arjan8,0
    Joris en Chris5,0V

    Van cijfers waar een 'A' achter staat, dient de opdracht nog te worden aangevuld.
    Van cijfers waar een 'V' achter staat, is de opdracht (inmiddels) voldoende en hoeft deze dus niet te worden aangevuld.

    Practicum Opgave 3

    De opgaves zijn nagekeken en hieronder staan de cijfers:
    Naam/Namencijfer Naam/Namencijfer
    Jasmin8,5 Mark en Jan-Paul7,3
    Peter en Sidar5,8 Erik7,5
    Pieter en Matthijs10,0 Jan en Floris K.9,0
    Floris C.6,5 Joost en Sander---H
    Johan en Josse9,3 Tyron en Thierry7,5
    Xander en Antal7,8 Duncan9,0
    Leroy en David 5,0A Arjan7,3
    Joris en Chris8,0

    Van cijfers waar een 'A' achter staat, dient de opdracht nog te worden aangevuld.
    Van cijfers waar een 'V' achter staat, is de opdracht (inmiddels) voldoende en hoeft deze dus niet (meer) te worden aangevuld.
    Van cijfers waar een 'H' achter staat moet de opdracht worden herkanst.