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:

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.

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: 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.


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.



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/