Algoritmiek 2015/2016

LET OP:

Mocht je een opdracht wel hebben ingeleverd, maar er nog geen cijfer en ook geen vermelding `nog niet nagekeken' in de cijferlijst staan, neem dan contact op met Rudy van Vliet, rvvliet(at)liacs(dot)nl.

De laatste cijfers voor opdracht 3 zijn bekend (29 augustus 2016). Zie verderop.

LET OP: Eerstejaars studenten Informatica en Economie volgen het vak in Den Haag. Deze website (http://liacs.leidenuniv.nl/~graafjmde/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. Zie aldaar voor de informatie over Algoritmiek zoals dat in Den Haag wordt gegeven.

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2016 verzorgd door Jeannette de Graaf. Het vak is verplicht voor alle studenten Informatica, Informatica en Biologie, Informatica en Economie, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 6 EC op. Studenten die deel gaan nemen aan Algoritmiek wordt verzocht zich via uSis aan te melden. Je kunt dit het beste doen via het nummer van de studieactiviteit Algoritmiek (dat is 10466). Je bent dan meteen aangemeld voor het tentamen. Zie hier voor informatie over inschrijven voor vakken/tentamens.

De colleges zijn op vrijdagen van 11:15 tot 13:00 uur in zaal B2 van het Snelliusgebouw. De bijbehorende werkcolleges vinden plaats op donderdagen van 13:45 uur tot 15:30 uur in zaal B1 en B2 (meestal) of in computerzaal 306/308 en/of 302/304 (soms). Assistentie bij de werkgroep en het practicum wordt verleend door Leon Helwerda, Hanjo Boekhout, Ruud Heesterbeek en Bart van Strien. Voor vragen/hulp bij de programmeeropdrachten kun je hen aanschieten tijdens de practicumbijeenkomsten en vragenuren, of je kunt mailen naar bart(dot)bes(at)gmail(dot)com (Bart). Het eerste college is op vrijdag 5 februari 2016; het eerste werkcollege is op donderdag 11 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 2015-2016 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2015/2016 wordt wederom 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 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 studiejaar 2015/2016

25-07-2016 - De definitieve tentamencijfers zijn inmiddels bekend. Voor degenen met een voldoende (>=5,5) wordt het eindcijfer berekend uit het tentamencijfer en het practicumcijfer. Het eindcijfer wordt in dat geval pas geboekt wanneer het practicum met een voldoende is afgesloten. Als het tentamen onvoldoende is wordt het eindcijfer gelijk aan het tentamencijfer (maar dan op helen/halven afgerond).

22-07-2016 - De cijfers moeten nog definitief gemaakt worden in overleg met de docent van Algoritmiek in Den Haag, maar wel is al bekend wie het tentamen gehaald hebben en wie niet. Zie daarvoor deze lijst. Ik verwacht maandag of dinsdag a.s. de definitieve cijfers te kunnen publiceren.

19-07-2016 - De uitslag van de hertentamens zal naar alle waarschijnlijkheid a.s. vrijdag na de middag bekend zijn en op deze website worden geplaatst. Nog even geduld dus.

06-07-2016 - De deadline voor aanvullingen voor de eerste twee programmeeropdrachten is verstreken.

27-06-2016 - Mocht je het nagekeken tentamen willen inzien/kopieren/meenemen, kom dan donderdag 30 juni (na 11 uur) of vrijdag langs in kamer 151. Dinsdag en woensdag ben ik niet aanwezig.

25-06-2016 - De tentamencijfers zijn nu allemaal bekend. Zie de lijst met resultaten.

24-06-2016 - En inmiddels is er ook een (handgeschreven) uitwerking van het tentamen van 7 juni op deze website verschenen. Zie verderop.

24-06-2016 - De cijfers voor het tentamen zijn bijna allemaal bekend. Een lijstje met een tussenstand staat hier. Ongeveer 2/3 van alle tentamencijfers zijn daar te vinden (alfabetisch op achternaam gesorteerd). Indien je nog niet op de lijst staat heb je het tentamen zeker gehaald, maar moet het definitieve tentamencijfer nog bepaald worden. Vanavond of morgen verwacht ik alle cijfers te kunnen publiceren.

24-06-2016 - Aanvullingen voor de derde programmeeropdracht kunnen uiterlijk 19 augustus 2016, 23.59 worden ingeleverd. Het papieren verslag (inclusief code) plus het verslag van de eerste poging (met opmerkingen van de nakijker) in het inleverbakje in de postkamer van het Snellius. De code kan digitaal naar Rudy van Vliet, rvvliet(at)liacs(dot)nl.

24-06-2016 - De (meeste) cijfers voor opdracht 3 staan online (en ook nog een paar extra cijfers voor opdracht 2).

23-05-2016 - De dag voor het tentamen is er een vragenuur. Dit zal plaatsvinden in een nader bekend te maken (op het mededelingenbord en de website) zaal in het Snellius. Datum: maandag 6 juni. Aanvang: 11.00 uur.

17-05-2016 - Op vrijdag 20 mei gaan we een oud tentamen oefenen, Tentamen van juli 2015.

13-05-2016 - De (meeste) cijfers voor opdracht 2 staan online.

10-05-2016 - Op donderdag 12 mei en vrijdag 13 mei is er van 15.30 uur tot 17.30 uur vragenuur voor de derde programmeeropdracht. In de computerzalen van het Snellius.

10-05-2016 - (De meeste inzendingen voor) de tweede programmaaropdracht is nagekeken. Verslagen met beoordeling worden op 12 en 13 mei bij werkcollege en hoorcollege uitgedeeld.

29-04-2016 - De cijfers voor de eerste programmeeropdracht staan online.

28-04-2016 - Er is aanvullende uitleg bij de derde programmeeropdracht.

26-04-2016 - Alle hulpbestanden voor de derde programmeeropdracht zijn beschikbaar.

20-04-2016 - De derde programmeeropdracht is beschikbaar.

13-04-2016 - Het werkcollege op donderdag 14 april is in zaal B03 in plaats van B01/B02.

13-04-2016 - De eerste programmeeropdracht is nagekeken, in ieder geval voor degenen die op tijd hadden ingeleverd. Verslagen met beoordeling worden op 14 en 15 april bij werkcollege en hoorcollege uitgedeeld.

12-04-2016 - Op donderdag 14 en vrijdag 15 april zijn er vragenuren voor de tweede programmeeropdracht, beide dagen van 15.30 tot 17.30 in zaal 302-304.

05-04-2016 - Ook op donderdag 7 april is er vragenuur voor het practicum. Er loopt dan vanaf 15.30 een assistent in de grote computerzalen om te helpen met opdracht 2.

24-03-2016 - De tweede programmeeropdracht is beschikbaar.

16-03-2016 - Op vrijdag 18 maart zal er van 15:30 tot 17:30 uur een vragenuur zijn in computerzaal 302/304 over de eerste programmeeropdracht. Assistentie is aanwezig.

14-03-2016 - Let op: deze week is er twee keer college, namelijk op donderdag 17 maart van 13.45 tot 15.30 uur EN op vrijdag 18 maart van 11:15 tot 13:00 uur. Beide dagen vindt het college plaats in zaal B2. Er is deze week dus geen werkcollege. Het eerstvolgende werkcollege is op 24 maart, volgende week donderdag dus.

10-03-2016 - Op vrijdagmiddag 11 maart is er een vragenuur voor de eerste programmeeropdracht van Algoritmiek. Tussen 15:00 en 17:00 uur zal er assistentie aanwezig zijn in computerzaal 302/304.

07-03-2016 - Door ziekte van de docent is het college van vrijdag 4 maart uitgevallen. Het is de bedoeling dat dit college nu op donderdag 17 maart plaatvindt, van 13.45 tot 15.30 uur, in plaats van het werkcollege. Wellicht is er op vrijdag 18 maart dan werkcollege i.p.v. college, maar dat is nog lang niet zeker. Houd dus deze website in de gaten.

26-02-2016 - De beloofde uitwerking van het bomenpracticum staat inmiddels online. Tevens is er een uitwerking van opgave 4 van het derde werkcollege beschikbaar.

23-02-2016 - Op Youtube is onder andere deze (gekuiste versie) van het kannenprobleem uit de film Die Hard with a Vengeance te vinden.

23-02-2016 - Voor de liefhebbers (naar aanleiding van het tweede college): het originele artikel van Euler (in het Latijn!) over het Koningsberger bruggenprobleem is te vinden via de Engelse Wikipedia.

15-02-2016 - De eerste programmeeropdracht staat online. Het skeletprogramma waarover in de opdracht gesproken wordt komt er waarschijnlijk morgen bij te staan.

15-02-2016 - Verderop op deze website heb ik uitwerkingen van enkele opgaven van het eerste werkcollege gezet. het bomenpracticum voor de werkgroep van donderdag 18 februari staat ook reeds online.

22-12-2015 - Er is nog geen nieuws. Het eerste college is op vrijdag 05-02-2015.

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. Op de laatste pagina van de collegesheets staat overigens ook altijd welke stof uit het boek bij het betreffende college hoort. Op de sheets staat vaak meer informatie/voorbeelden, zoals over backtracking. Verder kan men hier de bij het werkcollege behandelde opgaven vinden. (Let 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
5 februari	Introductie	college1	1.1, 1.4, 1.4 (t/m graafrepresentaties)	11 februari	opgaven1
12 februari	Grafen en bomen	college2	1.4	18 februari	opgaven2
19 februari	Toestand-actie-ruimte	college3	sheets, 4.5 (Searching and Inserting in a BST, The Game of Nim), 6.6 (Reduction to Graph Problems)	25 februari	opgaven3
26 februari	Complexiteit, brute force	college4	2.1-3, 3 inl., 3.1-3	3 maart	Programmeeropdracht 1
17 maart	Exhaustive search, backtracking	college5	3.4, 3.5; sheets; 12 inl., 12.1	24 maart	opgaven5
18 maart	Backtracking, verdeel en heers	college6	12.1; 5 inl., 5.1, 5.2, 4 inl., 4.1	31 maart	Programmeeropdracht 2
1 april	Verdeel en heers	college7	5.3-5.5, 4.inl., 4.4, 4.5	7 april	opgaven6
8 april	Kortste pad met BFS, Dynamisch programmeren	college8.1, college8.2	sheets, 8.inl, 8.2	14 april	opgaven8
15 april	Dynamisch programmeren	college9	sheets, 8.2, voorbeeld 2 in 8.1	21 april	opgaven9
22 april	Gretige algoritmen, Algoritme van Dijkstra	college10	sheets, 9.inl, 9.2 t/m blz 353, 9.3	28 april	Programmeeropdracht 3
29 april	Algoritme van Dijkstra, Branch & Bound	college11	sheets, 9.3, 12.2	12 mei	opgaven10
13 mei	Branch & Bound, heaps	college12	sheets, 12.2, 6.4	19 mei	opgaven12
20 mei	Oud tentamen oefenen	Tentamen van juli 2015		--	--

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

De hierboven gegeven slides bij de hoor- en werkcolleges (wordt in de loop van semester opgebouwd).
De hierboven vermelde delen uit de derde editie van het boek van Anany Levitin (wordt in loop van semester opgebouwd).
De opgaven die bij het werkcollege zijn behandeld, en die je hierboven in het schema kunt vinden (wordt in loop van semester opgebouwd).
Alles wat bij hoor- en werkcollege en de programmeeropdrachten aan de orde is gekomen.
Uiteraard moet je behandelde ontwerptechnieken voor algoritmes ook op nieuwe problemen kunnen toepassen.

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. Van enkele opgaven is een uitwerking beschikbaar. Deze worden gaandeweg het semester hieronder gepubliceerd.

Antwoorden van opgave 7 t/m 9 van het eerste werkcollege
Antwoorden van en Toestand-actie-ruimte bij opgave 4 van het derde werkcollege
Antwoorden van opgaven van het vijfde werkcollege
Antwoord van opgave 2 van het zesde werkcollege
Antwoorden van opgaven 1 en 6 van het zesde werkcollege
Antwoord van opgave 8 van het zesde werkcollege
Antwoord van opgave 11 van het achtste werkcollege
Antwoorden van opgaven 5-7 van het tiende/elfde werkcollege
Handgeschreven uitwerking van de heapopgaven uit het twaalfde werkcollege

Tweede Werkcollege 2015/2016

Tijdens het tweede werkcollege wordt er een practicumopdracht (over bomen) gedaan in de computerzalen. Zet de PC eerst op Linux (UNIX). Het skeletprogramma zoals dat moet worden gebruikt staat hier. Volg de volgende stappen om te beginnen:

Maak een nieuwe directory, bijvoorbeeld "binairebomen" (Linux: mkdir binairebomen), en ga daarheen (cd binairebomen).
Pak het skeletprogramma uit (onder Linux kan dat bijvoorbeeld met "tar xvfz bomenpracticum2016.tar.gz").
Ga naar de directory "bomenpracticum" (onder Linux kan dat bijvoorbeeld met "cd bomenpracticum").
Bekijk het bestand "readmelinux.txt" voor de precieze bedoeling en werking van het programma.

Het skeletprogramma bestaat uit een aantal files, waarvan je in het bestand "boom.cc" enkele functies moet invullen. Het programma is de compileren via de bijgeleverde Makefile. De opgaven staan hierboven in de tabel met het programma van colleges en werkcolleges (opgaven2). Bewerk "boom.cc" zoals aangegeven in de twaalf opgaven. In dit bestand kunnen vanaf ongeveer regel 35 de functies gevonden worden die moeten worden aangepast.

Liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen de bovengenoemde readme-file "readmelinux2016.txt".

Hier kun je voorbeelduitwerkingen vinden van het bomenpracticum. Uiteraard zijn andere oplossingen mogelijk, maar in principe lijken die allemaal op de functies uit de uitwerkingen. 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.

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. Voor elke opdracht is er in elk geval 1 keer een werkcollege in de computerzaal; je kunt dan aan de opdracht werken en de werkcollegebegeleiders zijn aanwezig om vragen te beantwoorden. Er zullen ook enkele speciale vragenuren worden georganiseerd in de twee weken voor de deadlines.
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 komen de drie programmeeropdrachten van dit studiejaar.

Programmeeropdracht 1 (brute force).
Uiterste inleverdatum: maandag 21 maart, 12:00 uur.
Er is een skeletprogramma beschikbaar, waarop je verder kunt bouwen. Onder Linux kun je het uitpakken met
- gunzip algoritmiek2016_1.tar
- tar xvf algoritmiek2016_1.tar
Extra uitleg over functie integerInBereik uit main.cc.
Een mogelijke werkwijze bij het programmeren is:
- Lees de opdracht helemaal door, want bijvoorbeeld vragen die je in het verslag moet beantwoorden, kunnen helpen bij de implementatie.
- Toestand-actie-ruimtes zoals die in het verslag moeten komen, behandelen we bij het derde college, op vrijdag 19 februari 2016 en bij het werkcollege van donderdag 25 februari.
- Implementeer achtereenvolgens:
  - constructor(s)
  - functie drukaf
  - functie eindstand
  - functie doezet(kolom), zowel voor gewoon vooruitzetten als voor slaan
  - recursieve functie winst (aantal)
  - functie doerandomzet
  - functie bestezet
- Het is verstandig om in principe na elke nieuwe functie (of deel daarvan) te testen of het programma doet wat je verwacht, door de op dat moment geschreven functies aan te roepen vanuit main.cc.
Deze opdracht is nagekeken. U vindt de resulterende cijfers hier.
Programmeeropdracht 2: Knock Out (backtracking).
Gepubliceerd: donderdag 24 maart.
Uiterste inleverdatum: maandag 18 april, 12:00 uur.
Er zijn een skeletprogramma en voorbeeldinvoerbestanden beschikbaar. Op het skeletprogramma kun je verder bouwen. De invoerbestanden kun je gebruiken. Onder Linux kun je het pakketje uitpakken met
- gunzip algoritmiek2016_2.tar
- tar xvf algoritmiek2016_2.tar
Nog een tip/waarschuwing:
- Bij de beoordeling van opdracht 1 hebben we geen punten afgetrokken voor memberfuncties en membervariabelen van een klasse die public gedeclareerd waren, terwijl ze private moesten zijn. Bij opdrachten 2 en 3 zullen we dat wel doen.
Deze opdracht is nagekeken. U vindt de resulterende cijfers hier.
Programmeeropdracht 3: Bloemen Plukken (dynamisch programmeren).
Gepubliceerd: woensdag 20 april.
Uiterste inleverdatum: dinsdag 17 mei, 11.00 uur.
Er is een pakketje met vier hulpbestanden beschikbaar. Onder Linux kun je het pakketje uitpakken met
- gunzip algoritmiek2016_3.tar
- tar xvf algoritmiek2016_3.tar
Aanvullende uitleg:
- Wanneer b.v. mogelijk[i][j][154]=true, betekent dit dat het mogelijk is om in vak (i,j) een boeket te hebben dat met de bitstring 10011010 (binaire representatie van 154) overeenkomt: een oneven aantal bloemen van soort 7, een even aantal bloemen van soort 6, een even aantal bloemen van soort 5, een oneven aantal bloemen van soort 4, een oneven aantal bloemen van soort 3, een even aantal bloemen van soort 2, een oneven aantal bloemen van soort 1, en een even aantal bloemen van soort 0.
  Als mogelijk[i][j][154]=false, is zo'n boeket niet mogelijk in vak (i,j).
Deze opdracht is nagekeken. U vindt de resulterende cijfers hier.

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 of de docent. Eventuele opmerkingen, tips of testgevallen 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

In studiejaar 2015/2016 vindt het tentamen plaats op dinsdag 7 juni 2016, 14.00-17.00 uur. Op maandag 6 juni 2016 is er een vragenuur. Aanvang: 11.00 uur. Zaal: B2.

Het hertentamen is op donderdag 7 juli 2016, 10.00-13.00 uur.

De tentamens van 2014 en 2015 en het juni-tentamen van 2016 zijn hieronder te vinden, alsmede uitwerkingen van enkele daarvan.

Tentamen van juni 2014 met een uitwerking.

Tentamen van juli 2014 met een uitwerking.

Tentamen van juni 2015 met een uitwerking.

Tentamen van juli 2015.

Tentamen van juni 2016 met een uitwerking.

Tentamen van juli 2016.

Vragen en/of opmerkingen kunnen worden gestuurd naar: j.m.de.graaf@liacs.leidenuniv.nl.

Laatste wijziging 29 augustus 2016 - http://liacs.leidenuniv.nl/~graafjmde/ALGO/