Algoritmiek 2011/2012

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2012 (in principe eenmalig) verzorgd door Johan Kwisthout. 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/kwisthou/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.

Assistentie bij de werkgroep en het practicum wordt verleend door Bas van Stein en Iris Hupkens.

De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 174. De bijbehorende werkcolleges vinden plaats op donderdagen van 13.45 uur tot 15.30 uur, in zaal 174 of in computerzaal 306/308. Het eerste college is op vrijdag 10 februari 2012; het eerste werkcollege is op donderdag 16 februari. Er zijn wat uitzonderingen in verband met b.v. feestdagen; zie het schema hieronder.

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 daar mee om gaat.

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

Materiaal

In het studiejaar 2011/2012 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 vorig jaar 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

(6-8-2012) Ook de hertentamens zijn nu nagekeken: zie de cijfers. Ik stuur de uitwerkingen binnenkort per post naar mevr. De Graaf zodat je desgewenst met haar een afspraak kunt maken voor de inzage. Je vindt hier het tentamen en je kunt hier de modeluitwerking bekijken.

(4-7-2012) Hier vind je de standaard-uitwerking van het tentamen, om je indien nodig voor te bereiden op het hertentamen of om nog eens te kijken wat de verwachte antwoorden waren. Het tentamen zelf vind je hier.

(21-6-2012) De cijfers van het tentamen zijn bekend en de eindcijfers zijn berekend. Het tentamen is in het algemeen goed gemaakt: van de 42 tentamens waren er 4 onvoldoende. Het gemiddelde cijfer was een 6.9, de mediaan (het middelste cijfer als je ze sorteert) 6.8. In de lijst met eindcijfers (op een half cijfer afgerond, behalve tussen 5 en 6) staat soms ONV. Dat kan betekenen dat a) je nog geen tentamen hebt gemaakt, b) je tentamen onvoldoende was, c) niet alle huiswerkopdrachten zijn ingeleverd of voldoende waren, of d) dat je in 2010 of eerder huiswerk hebt gemaakt wat voldoende is beoordeeld en toestemming had van de docent in 2011 dat deze cijfers meegenomen konden worden. Om van deze ONV af te komen: a/b) maak het tentamen (voldoende) bij de herkansing, c/d) neem contact op met mij en mevr. De Graaf om een regeling te treffen. Ik zal voor het inzien van de tentamens iets met haar afspreken. Het tentamen en de modeluitwerking komen binnenkort beschikbaar via de website.

Als je hiermee het vak hebt afgerond: een prettige vakantie en veel succes in het tweede jaar! Moet je er nog even tegenaan: zet er nog even de schouders onder en zorg dat je voor het einde van het studiejaar alsnog het vak hebt gehaald (en natuurlijk ook een prettige vakantie)!

(12-6-2012) Alle nagekomen uitwerkingen en uitwerkingen waarbij iets ontbrak wat is aangevuld zijn beoordeeld; zie de aangepaste cijferlijsten.

(8-6-2012) De cijfers voor de derde opdracht staan online! Let op: 'ONV' betekent onvoltooid: hier ontbreekt nog iets (verslag of code): neem contact op! 'VOLGT' betekent: uitwerking is later ingeleverd en nog niet nagekeken, volgt binnenkort (in de komende week).

(30-5-2012) Het tentamen is op 12 juni, 10.00-13.00, in zaal B01 en B02.

(21-5-2012) Er zijn nog wat nagekomen resultaten online gezet.

(11-5-2012) De cijfers staan online!

(2-5-2012) De laatste loodjes: op vrijdag 4 mei behandelen we nog wat restanten van Branch & Bound en de Transform & Conquer methode (in het bijzonder: Heapsort). Op vrijdag 11 mei geef ik een overzicht van de verschillende algoritmische technieken om een probleem aan te pakken, bekijken we Minimaal Opspannende Bomen (9.1 en 9.2) als toepassing van de Greedy methode (geen tentamenstof!) en is er ruimte om vragen te stellen of bepaalde zaken nog eens te behandelen. Mail mij t.z.t. met jullie verzoeken! Op donderdag 17/vrijdag 18 mei is de universiteit gesloten vanwege Hemelvaart; op vrijdag 25 mei maken en bespreken we een oefententamen ter voorbereiding op het echte tentamen. Op het werkcollege van 10 mei is nog de ruimte om vragen te stellen over de derde prakticum-opdracht (naast een aantal vragen die dan besproken worden). Het laatste werkcollege is op donderdag 24 mei.

(20-4-2012) De derde practicumopdracht staat online! Zie onder.

(20-4-2012) We hebben het kort gehad over Edsger W. Dijkstra, tot nu toe Nederlands enige Turing Award winnaar. Dijkstra is zo belangrijk voor de informatica dat zijn vele artikelen, dictaten, brieven enzovoorts allemaal een eigen index hebben gekregen, waaronder het artikel met het naar hem genoemde kortste paden-algoritme.

(18-4-2012) Wat kleine aanpassingen in het schema, met name met betrekking tot de laatste werkcolleges. Het hoorcollege van vrijdag 4 mei is het laatste (inhoudelijke) hoorcollege. De week erna is beschikbaar voor uitloop, extra herhaling (laat me weten of je iets graag herhaald wilt zien!), en/of extra facultatieve stof ter lering en vermaak. Op vrijdag 25 mei bespreken we een oud tentamen als voorbereiding op het reguliere tentamen.

(2-4-2012) De cijfers voor de eerste practicumopdracht zijn bekend. Zie onder. Staat er 'onv' bij je studentnummer, neem dan contact op: enkele uitwerkingen waren onvolledig (geen verslag b.v.) of onvoldoende. Staat je studentnummer er niet bij en heb je wel iets ingeleverd: kijk dan eerst of je uberhaupt wel je studentnummer op de uitwerking hebt gezet (en zo nee, laat deze per omgaande weten en zet 'm er de volgende keer wel bij), zo ja, geef dan aan wanneer je precies de opdracht hebt ingestuurd. In de cijfers zijn de strafpunten voor te laat inleveren al meegenomen.

(26-3-2012) Inmiddels draaien alle scripts weer en is de website up-to-date (inclusief de permissies die nu wel in orde zouden moeten zijn).

(16-3-2012) De tweede practicumopdracht staat online! Zie onder.

(24-2-2012) De wikipedia-pagina over de N-queens puzzle is de moeite waard om te bekijken.

(17-2-2012) De practicumopdracht is online gezet, net als de instructie voor het tweede werkcolege. Vandaag heb ik enkele problemen geschetst die te vertalen zijn naar graafproblemen, om aan te geven waarom grafen zo belangrijk zijn in de informatica. Op de Wikipedia-pagina over Graph theory vind je er nog een aantal. Enkele van deze problemen bespreken we later in het college.

(10-2-2012) Hier vind je links naar een algemene website over De Elementen en meer specifiek, een artikel over de meetkundige benadering van de grootste gemene deler. Ook vond ik informatie over het Vierkleurenprobleem. N.B. dit is ter illustratie en verdere verdieping, en geen examenstof.

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. De datum stelt de vrijdag van de betreffende week voor. 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
10 februari HC1: Introductie, datastructuren slides 1.1, 1.2, 1.4 (t/m graafrepresentaties) 16 februari opgaven
17 februari HC2: Grafen en bomen slides 1.4 (totaal) 23 februari opgaven (instructie)
24 februari HC3: Toestand-actie-ruimte slides sheets (lees 6.6 / 4.5 uit boek) 1 maart opgaven
2 maart HC4: Complexity, brute force slides 2.1-3, 2.6-7 (lezen), 3 t/m 3.3 8 maart WC4 (practicum)
9 maart HC5: Exhaustive search, backtracking slides 3.4, sheets, 12 t/m 12.1 15 maart opgaven
16 maart HC6: Divide and conquer slides 12.1, 5 t/m 5.2, 4 t/m 4.1 22 maart opgaven
23 maart HC7: Dynamisch programmeren (1) slides 4.1, 4.4, 5.3-5.5, 8 29 maart geen werkcollege
30 maart geen hoorcollege op vrijdag slides 4.1, 4.4, 5.3-5.5, 8 5 april HC8: Dynamisch programmeren (2)
6 april geen hoorcollege ... ... 12 april WC7 (practicum)
13 april geen hoorcollege ... ... 19 april opgaven
20 april In zaal 412 HC9: Greedy algoritmen, Dijkstra slides 9 inleiding en 9.3, sheets 26 april opgaven
27 april HC10: Dijkstra, branch-and-bound slides 9.3, 12.2 3 mei WC10 (practicum)
4 mei HC11: Transform-and-Conquer slides 12.2, 6 inleiding, 6.4 10 mei opgaven + practicum
11 mei HC12: overzicht, extra stof (9.1-2) slides lezen 9.1 en 9.2 (geen tentamenstof) 17 mei geen werkcollege
18 mei geen hoorcollege ... ... 24 mei opgaven
25 mei HC13: bespreken oefententamen tentamen ... 31 mei geen werkcollege

Toelichting: in de week van 26 maart tot 30 maart zijn de hertentamens van het vorige semester. Op 6 april is de universiteit gesloten wegens Goede Vrijdag. Op 12 en 13 april vertoeft de docent in het buitenland. Op 20 april is de open dag, waarvoor zaal 174 wordt gebruikt. Op 17 en 18 mei is het Hemelvaart, respectievelijk is de universiteit gesloten.

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

 Tijdens het tweede werkcollege zal er een practicumopdracht worden gedaan in de computerzaal 306-308. Het skeletprogramma staat hier. 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 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.

Op dit moment is beschikbaar:

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. Zie hier de gemiddelde cijfers voor het programmeren - dit is dus een derde van je eindcijfer. Zie hier de eindcijfers.

Tentamen

Het tentamen vindt plaats op dinsdag 12 juni 2012, 10.00-13.00 uur, in zaal B1 en B2. Het hertentamen is op dinsdag 31 juli 2012, 10.00-13.00 uur.

De tentamens van 2010 en 2011 zijn hieronder te vinden, alsmede uitwerkingen van de mei/juni-tentamens.


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

Laatste wijziging 21 juni 2012 - http://www.liacs.nl/~kwisthou/ALGO/