Algoritmiek 2014/2015

LET OP: Eerstejaars studenten Informatica en Economie volgen het vak in Den Haag. Deze website (http://keep.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 2015 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. 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 9913). 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, Mathe Zeegers en Ruud Heesterbeek. Het eerste college is op vrijdag 6 februari 2015; het eerste werkcollege is op donderdag 12 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 2014-2015 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2014/2015 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 2014/2015

21-07-2015 - Vandaag heb ik de eindcijfers zoals berekend uit het programmeerwerk en de tentamencijfers van het JUNI-tentamen opgestuurd om te laten boeken in uSis. Schrik dus niet als je een automatische mail krijgt uit uSis met een onvoldoende. De eindcijfers op basis van het hertentamen moeten nog berekend worden; die komen eind deze week of begin volgende week in uSis.

16-07-2015 - Ook de cijferlijst van het programmeerwerk is weer ge-updatet.

16-07-2015 - Hier de tentamencijfers van het hertentamen van 9 juli. Indien het tentamencijfer onvoldoende is (dus minder dan 5,5), dan is het tentamencijfer tevens het eindcijfer voor Algoritmiek. Dit staat dan als zodanig in de lijst al (afgerond) vermeld. Zo niet, dan moet nog gemiddeld worden met het gemiddelde practicumcijfer. Binnenkort zullen de eindresultaten van zowel het tentamen als het hertentamen worden berekend en in uSis worden gezet. Indien je het tentamen niet gehaald hebt moet je in principe volgend jaar weer met de reguliere tentamens meedoen. Mochten er echter zwaarwegende redenen zijn waarom je nog een extra kans zou moeten/kunnen krijgen in dit studiejaar ... meld je dan met de reden hiervoor bij de docent. Eind augustus wordt er namelijk geheel toevallig nog een extra herkansing van het vak gegeven.

07-07-2015 - De uitwerking van het tentamen van afgelopen juni staat nu op de website. Excuses dat het wat lang heeft geduurd.

06-07-2015 - Er is vandaag een kleine update geweest van de practicumcijfers. Zie hieronder (15 juni).

27-06-2015 - Met enige moeite heb ik het bestand met tentamencijfers van het juni-tentamen op de site weten te zetten. Je kunt zelf je eindcijfer uitrekenen. In de sheets van het eerste college staat hoe je eindcijfer berekend wordt. Studenten die de minor doen hebben niet de aanvullende eis dat zowel practicum als tentamen voldoende moeten zijn; alle andere studenten moeten wel aan die eis voldoen.

26-06-2015 - Het tentamen van juni is nu voor driekwart volledig nagekeken en becijferd. Van een kwart moet nog de tweede correctie gedaan worden. Het is de bedoeling dat morgen (27/6) af te hebben en de tentamencijfers op de website te zetten.

15-06-2015 - Er is een overzicht beschikbaar van alle tot dusver bekende cijfers van de drie programmeeropdrachten van Algoritmiek. Mocht je iets tegenkomen dat niet klopt, laat dat dan even weten. Enkele opdrachten zijn later ingeleverd en nog niet nagekeken. Tevens zijn er nog enkele studenten die een of meer opdrachten moeten aanvullen. Zie ook de mededeling hieronder. Nagekeken werken zijn uiteraard bij mij terug te halen (kamer 151).

05-06-2015 - !!! Eind volgende week zal ik alle cijfers voor het programmerwerk -voor zover die bekend zijn- op deze site zetten. Studenten die nog opdrachten moeten aanvullen en nog geen contact daarover met mij hebben gehad moeten zich alsnog melden om e.e.a. te bespreken. De bedoeling is om uiterlijk 3 juli (eerder mag natuurlijk ook) alles wat aangevuld moest worden alsnog in verbeterde vorm in te leveren.

05-06-2015 - Het tentamen van augustus 2013 is ook weer bereikbaar! Met excuses voor het ongemak.

05-06-2015 - Zoals beloofd staat er nu ook een uitwerking van het hertentamen van 2014 op de site. Omdat ik het origineel niet heb kon ik niet de paar kleine onvolkomenheden verbeteren. Bij deze dus. In opgave 5 moeten de laatste twee koppelingen bij oplossing 14 resp. 15 zijn: (C&M, D&N) resp. (C&N, D&M). De bijbehorende succeswaarden kloppen wel. Verder in opgave 4c: het aantal vergelijkingen 2(n-1) is correct, mits we aannemen dat er geen short circuiting plaatsvindt. Dan worden altijd beide tests gedaan, ook al is blijkt de eerste False op te leveren. Met short circuiting wordt het aantal vergelijkingen iets lastiger te bepalen (ongeveer 3/2 n).

04-06-2015 - Het vragenuur zal plaatsvinden in zaal 174 van het Snellius.

26-05-2015 - Afgelopen vrijdag is een datum+tijd voor het vragenuur voor het tentamen afgesproken. Dit gaat plaatsvinden op vrijdag 5 juni a.s., aanvang 11:00 uur. De zaal wordt later bekendgemaakt.

21-05-2015 - Programmeeropdracht 2 is nu ook nagekeken (op een paar inzendingen na). Ze zullen na afloop van het werkcollege worden uitgedeeld. Vanaf vrijdag 22 mei zijn de nagekeken werken uiteraard ook via de docent terug te krijgen, bijvoorbeeld bij het college.

21-05-2015 - Tijdens het college van 22 mei zal een oud tentamen worden besproken. Het is zinvol om daar zelf alvast naar te kijken en wellicht zelfs te maken. Het werkcollege van 21 mei zal plaatsvinden in zaal B2. Het zal gaan over branch & bound en heaps / heapsort. Aangezien ten minste een van deze twee onderwerpen op het tentamen verschijnt is het verstandig om hiermee tijdens het werkcollege te oefenen.

21-05-2015 - Er zijn inmiddels (eindelijk) testgevallen beschikbaar. Zie bij de programmeeropdracht zelf.

18-05-2015 - Er zal a.s. donderdag 21 mei na het werkcollege, dus vanaf 15.30 uur, assistentie aanwezig zijn in de computerzalen om te helpen met opdracht 3, voor zover je daar nog niet uit bent gekomen. Maak daar gebruik van! Hetzelfde geldt voor vrijdagmiddag 22 mei.

18-05-2015 - Gezien gekregen vragen van studenten staan er in de tips-file nog twee opmerkingen over de manieren waarop je de uiteindelijke optimale oplossing moet terugvinden.

13-05-2015 - Er staat ook weer een file met een paar opmerkingen bij programmeeropdracht 3 op de site (zie verderop). Tevens is -zoals bij college reeds aangegeven- de deadline op vrijdag 22 mei gezet. Laat even weten of er nog een vragenuur gewenst is bij deze opdracht, dan kunnen we voor de donderdag nog wat regelen.

28-04-2015 - De derde programmeeropdracht (dynamisch programmeren) staat online. Enige toelichting volgt aanstaande vrijdag op college.

24-04-2015 - Bij college 9 is als voorbeeld van dynamisch programmeren het berekenen van binomiaalcoefficienten gebruikt. Behalve in de sheets kun je daarover ook iets vinden in de tweede editie van het door ons gebruikte boek van Levitin. Deze paragraaf is bij de overgang van de tweede editie naar de derde editie uit het boek verdwenen. Een scan daarvan is hier beschikbaar.

23-04-2015 - Zoals jullie weten is programmeeropdracht 1 nagekeken. Vorige week is nagekeken werk al bij college en werkcollege teruggegeven aan de aanwezigen. Als je je werk nog niet terughebt kun je dit bij de docent afhalen. De cijfers zullen overigens binnenkort ook op deze site worden geplaatst.

23-04-2015 - Er zijn enige uitwerkingen van opgaven van de werkcolleges toegevoegd.

23-04-2015 - Vragenuren voor de tweede programmeeropdracht deze week: donderdag 23 april om 15:30 uur en vrijdag 24 april om 15:30 uur. Computerzaal 302/304.

16-04-2015 - De opmerkingen en aanwijzingen bij de tweede programmeeropdracht zijn uitgebreid met enige belangrijke zaken betreffende de te schrijven backtracking-functies. Lezen dus!

02-04-2015 - Er zijn nu ook enige tips en opmerkingen bij de tweede programmeeropdracht verschenen. En alvast het volgende .... graag de programmacode t.z.t. in het verslag zetten en als geheel op papier inleveren. Net als bij Programmeermethoden dus.

26-03-2015 - De tweede programmeeropdracht (backtracking) staat online.

19-03-2015 - Het werkcollege is voortaan in zaal B2 als er opgaven op papier worden gemaakt.

17-03-2015 - Vragenuren voor de eerste programmeeropdracht deze week: donderdag 19 maart om 15:30 uur en vrijdag 20 maart om 15:30 uur. Computerzaal 306/308.

17-03-2015 - Er is een uitwerking van opgave 4 van werkcollege 3 beschikbaar. Dit was in 2011 een tentamenopgave.

06-03-2015 - De aanwijzingen bij de eerste programmeeropdracht zijn uitgebreid en de layout van de makefile verbeterd. Lees verder bij Programmeeropdrachten.

06-03-2015 - Inmiddels zijn de uitwerkingen van de opgaven van het bomenpracticum beschikbaar. Zie verderop op deze pagina.

05-03-2015 - Er zijn enige tips/aanwijzingen bij de eerste programmeeropdracht verschenen. Deze gaan voornamelijk over de opbouw van je programma (opdeling in klassen en files), zoals ook al even aan de orde is geweest aan het eind van het vierde college.

23-02-2015 - De aangepaste (en definitieve) versie van de eerste programmeeropdracht staat nu online. Toegevoegd zijn de normering en een stukje over de klasse-structuur van het programma. Verder is de vormgeving iets veranderd.

23-02-2015 - Zoals beloofd staat de eerste programmeeropdracht online. Er moet nog over een paar dingen worden overlegd met de docent van het vak in Den Haag, zoals over de normering. De versie die nu online staat is dus nog niet helemaal definitief. Inhoudelijk zal de opdracht niet veranderen. De definitieve versie zal morgenmiddag op deze site geplaatst worden.

13-02-2015 - Voor de liefhebbers: het originele artikel van Euler (in het Latijn!) over het Koningsberger bruggenprobleem is te vinden via de Engelse Wikipedia.

10-01-2015 - Er is nog geen nieuws. Het eerste college is op vrijdag 06-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
6 februari Introductie college1 1.1, 1.4, 1.4 (t/m graafrepresentaties) 12 februari opgaven1
13 februari Grafen en bomen college2 1.4 19 februari opgaven2
20 februari Toestand-actie-ruimte college3 4.5 (p. 189-192), 6.6 (p. 272-272) 26 februari opgaven3
27 februari Complexiteit, brute force college4 2.1-3, 2.6-7 (lezen), 3 inl., 3.1-3 5 maart Eerste programmeeropdracht
6 maart Exhaustive search, graafwandelingen, backtracking college5 3.4-5, 12 inl., 12.1 19 maart opgaven5
13 maart geen (werk)college --- herkansingen --- ---
20 maart Backtracking, verdeel en heers college6 12.1, 5 inl., 5.1-2, 4 inl., 4.1 26 maart opgaven6
27 maart Verdeel en heers college7 4 inl., 4.1, 4.4, 5.2-5 deels 2 april Tweede programmeeropdracht
3 april Geen college Goede Vrijdag --- 9 april opgaven8
10 april Dynamisch programmeren + restant V&H college8 ex. 4.5.12, 8 inl., 2.5 16 april Tweede programmeeropdracht
17 april Dynamisch programmeren college9 8 inl., 8.1 (vb. 2), 8.2 23 april opgaven10
24 april Gretige algoritmen, algoritme van Dijkstra college10 ... 30 april opgaven11
1 mei Branch and bound college11 12.2 7 mei Derde programmeeropdracht
8 mei Heap, heapsort college12 6.4 14 mei Hemelvaart
15 mei Geen college ----- --- 21 mei opgaven13
22 mei Hertentamen 2014 hertentamen --- --- ---


De tentamenstof bestaat uit: alles wat we gedurende het semester behandelen. Dat komt in 2014/2015 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 zullen hieronder worden gepubliceerd.

Tweede Werkcollege 2014/2015

 Tijdens het tweede werkcollege wordt er een practicumopdracht worden 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-files "readmelinux2015.txt" of "readmewindows2015.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. 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. 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.


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

Tentamen

In studiejaar 2014/2015 vindt het tentamen plaats op dinsdag 9 juni 2015, 14:00-17:00 uur. Op vrijdag 5 juni 2015 is er een vragenuur. Aanvang: 11:00 uur. Zaal: 174.

Het hertentamen is op donderdag 9 juli 2015, 10:00-13:00 uur.

De tentamens van en 2013 en 2014 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 31 juli 2015 - http://liacs.leidenuniv.nl/~graafjmde/ALGO/