Algoritmiek 2012/2013

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2013 verzorgd door Jeannette de Graaf. Het vak is verplicht voor alle studenten Informatica, Informatica en Economie, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 6 EC op.

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.

De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 412. De bijbehorende werkcolleges vinden plaats op donderdagen van 13.45 uur tot 15.30 uur, in zaal 412 en (waarschijnlijk) B02, of in computerzaal 302/304 of 306/308. Het eerste college is op vrijdag 8 februari 2012; het eerste werkcollege is op donderdag 14 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). In het vak Complexiteit (vierde semester) gaan we dieper in op de vraag hoe moeilijk bepaalde problemen zijn, hoe je dat onderzoekt, en hoe je daarmee omgaat.

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, greedy 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 2012-2013 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2012/2013 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.
Tot en met studiejaar 2010/2011 werd de second edition van het boek gebruikt. Deze verschilt niet vreselijk veel van de nieuwe editie: er is wat geschoven in de volgorde van sommige behandelde methoden, en de opgaven zijn volgens de schrijver van het boek uitgebreid. De tweede editie van het boek is inhoudelijk dus ook te gebruiken, maar let op voor andere hoofdstuknummering en andere opgavenummering. Voor een compleet overzicht, zie de verwijslijst van de derde editie naar de tweede editie. De paragraaf over het berekenen van binomiaalcoefficienten met behulp van dynamisch programmeren is bij de overgang van de tweede editie naar de derde editie uit het boek verdwenen. Een scan hiervan is hier te vinden.
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 (en of er fouten in gevonden worden). Na afloop van het college wordt telkens de definitieve versie van de sheets hieronder geplaatst.

Programma

Het programma van colleges en werkcolleges zal hieronder worden 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. (Let dus op als je de tweede editie van het boek gebruikt. De verwijzingen zijn in principe naar de derde editie.)

Datum (HC) Onderwerp Sheets Boek Datum (WC) Werkcollege
8 februari --- --- --- 14 februari ---

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 2011/2012

 Tijdens het tweede werkcollege zal er een practicumopdracht worden gedaan in de computerzaal 306-308. Het skeletprogramma zoals dat vorig studiejaar (2011/2012) werd gebruikt staat hier. Hieronder de opdracht (versie 2011/2012). Volg de volgende stappen om te beginnen: De opgaven staan hierboven in de tabel (afgelopen studiejaar dus) met het programma van colleges en werkcolleges. Bewerk "boom.cc" zoals aangegeven in de twaalf opgaven. In dit bestand kunnen vanaf regel 327 de functies gevonden worden die moeten worden aangepast.

De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen de file "readmewindows.txt" of "readmelinux.txt".

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. In de week voorafgaand aan de deadline is het werkcollege in de computerzaal; je kunt dan aan de opdrachten werken en de werkcollegebegeleiders zijn aanwezig om vragen te beantwoorden. De opdrachten dienen (stipt!) op de deadlines te worden ingeleverd. Anders gaat er per week (of gedeelte daarvan) te laat inleveren een punt 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 om een individuele regeling te treffen. Deelresultaten blijven niet automatisch geldig.

Hieronder staan nog de opdrachten die in 2011/2012 gemaakt zijn.

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 de werkcollegebegeleiders. Eventuele opmerkingen of tips bij de opdrachten zullen hier worden bekendgemaakt.

Eindcijfer

Het programmeerwerk telt, 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 vindt plaats op dinsdag 11 juni 2013, 10.00-13.00 uur. De zalen zullen t.z.t. bekend worden gemaakt. Het hertentamen is op woensdag 7 augustus 2013, 14.00-17.00 uur.

Enkele tentamens van 2010, 2011 en 2012 zijn hieronder te vinden, alsmede uitwerkingen daarvan.


Vragen en/of opmerkingen kunnen worden gestuurd naar: graaf@liacs.nl.

Laatste wijziging 7 december 2012 - http://www.liacs.nl/~graaf/ALGO/