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 306/308. Assistentie bij de werkgroep en het practicum wordt verleend door Iris Hupkens (ihupkens@liacs.nl) en Erik Massop (emassop@liacs.nl). Het eerste college is op vrijdag 8 februari 2012; het eerste werkcollege is op donderdag 14 februari.

Indeling werkgroepen. Op donderdagmiddagen zullen er -in elk geval in de eerste paar weken- twee werkgroepen Algoritmiek zijn. Groep 1 zit in zaal 412; groep 2 in zaal B2. De verdeling over de werkgroepen is als volgt: studenten waarvan de achternaam eindigt op A t/m M zitten zoveel mogelijk in groep 1; studenten van wie de achternaam op N t/m Z eindigt zitten in groep 2. Tijdens de werkcolleges in de computerzalen zitten alle studenten bij elkaar.

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.

Nieuws / mededelingen



20-02-2013 - er is een uitwerking van opgaven 7,8 en 9 van werkcollege 1 beschikbaar.

21-02-2013 - de eerste programmeeropdracht is nu te downloaden. Begin er op tijd aan te werken! In week 10 zal het werkcollege aan deze opdracht gewijd zijn. Dat betekent echter niet dat je dan pas hoeft te beginnen.

25-02-2013 - het beloofde hulpprogramma voor het genereren van random grafen is inmiddels ook beschikbaar (zie hieronder)

28-02-2013 - een voorbeelduitwerking van de te schrijven functies uit het bomenpracticum staat inmiddels ook online

01-03-2013 - bij programmeeropdracht 1 (zie hieronder) is nu ook een voorbeeld geplaatst van hoe een toestand-actie-ruimte er voor het bekeken spel moet uitzien

15-03-2013 - er zijn vier testgevallen beschikbaar bij de eerste programmeeropdracht. Een eerder gemaakt foutje is daarin hersteld.

15-03-2013 - de tweede programmeeropdracht (backtracking) staat online. Deze moet op 19 april worden ingeleverd. Donderdag 4 april zal het werkcollege aan deze opdracht gewijd zijn.

16-03-2013 - de eerste programmeeropdracht moet maandag 18 maart worden ingeleverd; als het later wordt levert dit per week een punt aftrek op. Het is dus zeer verstandig om, als je vragen hebt over het te schrijven programma, deze in de komende week te stellen aan de werkgroepassistenten of de docent. Het is namelijk wel de bedoeling dat een werkend programma wordt ingeleverd.

16-03-2013 - zoals al eerder op college verteld zijn er geen standaard vragenuren bij de programmeeropdrachten (zoals het geval was bij Programmeermethoden), tenzij er speciaal om een vragenuur verzocht wordt. Wel is er bij elke programmeeropdracht een werkcollege waarin onder begeleiding aan de opdracht gewerkt wordt.

18-03-2013 - op verzoek wordt de deadline voor programmeeropdracht 1 verschoven naar vrijdag 22 maart. Bij problemen: stel vragen en vraag hulp (per e-mail of persoonlijk) aan de werkgroepleiders of de docent.

10-04-2013 - Om je backtrackingprogramma (programmeeropdracht 2) te testen: voor n=8 zijn er 128 goede standen; voor n=14 zijn dat er 3118664.

16-04-2013 - De eerste programmeeropdracht is grotendeels nagekeken. De cijfers zijn hier te vinden. Er moeten nog enkele opdrachten nagekeken worden. De cijfers daarvan worden een deze dagen toegevoegd aan bovenstaande lijst. Overigens zal binnenkort nog een kopieercontrole plaatsvinden op de ingeleverde opdrachten. De cijfers zijn dus onder voorbehoud.

16-04-2013 - Op woensdag 17 april is er een extra vragenuur voor de tweede programmeeropdracht. Dit vragenuur vindt plaats vanaf 15.30 uur in zaal 306/308, aansluitend op het werkcollege Databases. Erik Massop (assistent bij Algoritmiek) zal aanwezig zijn om te helpen bij problemen en vragen.

16-04-2013 - Omdat veel studenten bij de tweede opdracht voor het algemene geval van n+k dames (en k pionnen) gaan, twee willekeurige testvoorbeelden. Als k=3 en n=10: 528 standen; Als k=5 en n=12: 7.032 standen.

24-04-2013 - De derde programmeeropdracht staat inmiddels online. De uiterste inleverdatum is op vrijdag 17 mei 2013.

25-04-2013 - De kopieercontrole heeft vorige week plaatsgevonden, en de cijfers voor opdracht 1 zijn nu definitief. Degenen die moeten aanvullen wordt aangeraden zo snel mogelijk contact op te nemen met de nakijker, om te bespreken wat er nog moet verbeterd. Als het aanvullen meer dan een dag werkt lijkt te worden, neem dan even contact op met mij (de docent) om te bespreken wanneer je je aanvulling inlevert.

02-05-2013 - Inmiddels staat er een voorbeeldinvoer met bijbehorend antwoord online behorend bij programmeeropdracht 3. Zie hieronder, bij de programmeeropdrachten. Tevens is daar een hulpprogramma te vinden voor het genereren van random invoer.

07-05-2013 - Woensdagmiddag 15 mei zal er een extra vragenuur zijn over de derde programmeeropdracht o.l.v. Iris Hupkens. Dit vragenuur zal plaatsvinden in computerzaal 306/308, en begint om 15.30 uur.

13-05-2013 - Wellicht mosterd na de maaltijd, maar toch .... In opdracht drie kun je het aandelenpakket middels een bitstring weergeven, waarbij bit 1 betekent dat je het betreffende aandeel in bezit hebt en 0 dat dit niet het geval is. Zo'n bitstring correspondeert met een geheel getal en omgekeerd. Om nu uit een geheel getal de achterhalen welke bits op 1 staan kun je herhaald door twee delen, maar je kunt ook gebruik maken van bepaalde bitstring-operaties. Een voorbeeld vind je hier.

16-05-2013 - De tweede programmeeropdracht is nagekeken. De cijfers zijn hier te vinden. Nagekeken werken zijn af te halen bij de docent.

17-05-2013 - Voor het tentamen is er een vragenuur. Dit staat gepland op maandg 10 juni 2013, om 11.00 uur. Mocht je al eerder vragen hebben, stuur dan gerust een mail of kom langs. In dat laatste geval is het verstandig een afspraak te maken.

05-06-2013 - Er is nu ook een uitwerking van de opgaven van werkcollege 5 beschikbaar, en antwoorden van opgaven 4 en 5 van werkcollege 10.

06-06-2013 - De derde programmeeropdracht is grotendeels nagekeken. De cijfers zijn hier te vinden. Er moeten nog enkele opdrachten nagekeken worden. De cijfers daarvan worden een deze dagen toegevoegd aan bovenstaande lijst. Het nagekeken werk is af te halen bij de docent in kamer 151.

01-07-2013 - Het tentamen is nog niet helemaal nagekeken. Ik verwacht dat dit woensdag/donderdag a.s. wel het geval zal zijn. De tentamenuitslagen zullen dan meteen op deze site worden gepost. Nog een paar dagen geduld dus (sorry).

04-07-2013 - Het tentamen is nu wel nagekeken. De behaalde tentamencijfers kun je hier vinden. De eindcijfers moeten nog berekend worden en zullen als het goed is morgen ook hier op de site komen. Het is verstandig om langs te komen om je tentamen in te zien en/of een kopie van je nagekeken werk mee naar huis te nemen. Dit is vooral zinvol indien je het tentamen deze keer niet gehaald hebt en dit in augustus wilt herkansen.

05-07-2013 - De eindcijfers zijn berekend en kunnen hier gevonden worden. Er komt nog een uitwerking van het juni-tentamen op de site te staan.

15-07-2013 - De uitwerking (handgeschreven) is inmiddels beschikbaar, en is te vinden onder het kopje Tentamen.

18-07-2013 - De komende drie weken ben ik afwezig. Voor vragen over het vak, of voor een kopie van je nagekeken tentamen, kun je bij de docent die Algoritmiek in Den Haag verzorgt terecht. Op maandag 5 augustus a.s. zal hij (= Rudy van Vliet) in elk geval vanaf een uur of 11 beschikbaar zijn voor vragen in kamer 124 (Snellius). Ook op woensdagochtend 7 augustus kun je nog bij hem langs. Via zijn homepage kun je zien of hij ook op andere dagen/tijden aanwezig is.

19-08-2013 - Het hertentamen is nagekeken. De behaalde tentamencijfers kun je hier vinden. De eindcijfers moeten nog berekend worden en zullen zeer binnenkort ook hier op de site komen.

30-08-2013 - De eindcijfers zijn berekend en staan hier.

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 Introductie sheets1 1.1, 1.2, 1.4 (t/m graafrepresentaties) 14 februari opgaven1
15 februari Grafen en bomen sheets2 1.4 vanaf graafrepresentaties 21 februari opgaven2
22 februari Toestand-actie-ruimte sheets3 6.6 (alleen Reduction to Graph Problems 28 februari opgaven3
1 maart Complexiteit, Brute force, Exhaustive search sheets4 2.1-3, 2.6-7 (lezen), 3 inleiding, 3.1-3 7 maart Eerste programmeeropdracht
8 maart Exhaustive search, Backtracking sheets5 3.4, 12 inleiding, 12.1 14 maart opgaven5
15 maart Backtracking, Begin verdeel en heers sheets6 12.1, 5 inleiding, 4 inleiding 21 maart opgaven6
22 maart Verdeel en heers sheets7 4.1, 4.4, 5.2-5 4 april Tweede programmeeropdracht
29 maart Geen college: Goede Vrijdag --- --- geen werkcollege op 28/3; wel op 4 april ---
5 april Restant decrease and conquer, Dynamisch programmeren sheets8 Sheets, 8 inleiding 11 april opgaven8
12 april Dynamisch programmeren sheets9 Sheets, 8.1, 8.2, scan binomiaalcoefficienten 18 april opgaven9
19 april Restant DP, Gretige algoritmen sheets10 Sheets, 9 inleiding + 9.3 25 april opgaven10
26 april Restant gretig, Branch & bound sheets11 9.3, 12.2, sheets 2 mei Derde programmeeropdracht
3 mei Restant Branch & bound, Heap(sort) sheets12 12.2, 6.4 16 mei opgaven12
17 mei Oud tentamen: augustus 2010, 2011 zie onder --- --- ---

De tentamenstof bestaat uit: alles wat we gedurende het semester behandelen. Dat komt op het volgende neer:

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

 Tijdens het tweede werkcollege zal er een practicumopdracht worden gedaan in de computerzaal 306-308. Het skeletprogramma zoals dat moet worden gebruikt staat hier. Hieronder staat de opdracht. Volg de volgende stappen om te beginnen: De opgaven staan hierboven in de tabel met het programma van colleges en werkcolleges. Bewerk "boom.cc" zoals aangegeven in de twaalf opgaven. In dit bestand kunnen vanaf regel 350 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".

Voorbeeld uitwerkingen zijn hier te vinden. Als alles goed is, dan moet de test bij onderdeel 1 (menu-optie 1) een uitvoer hebben die sterk hierop lijkt. De uitvoer bij onderdeel 2 (menu-optie 2) moet hierop lijken. Binnenkort zullen de uitwerkingen van het bomenpracticum op deze plek worden geplaatst.

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.

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. Voor minorstudenten geldt een iets aangepaste regel.

Tentamen

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