Algoritmiek,

voorjaar 2021

Toren Academiegebouw

Laatste nieuws

Het coronatentamen van 18 augustus 2021 is nagekeken. Cijfers staan in Brightspace. Mocht je je tentamen willen inzien, maak dan een afspraak met de docent.

Een aantal (nog niet allemaal) herkansingen voor opdrachten 2 en 3 is nagekeken. Negen voldoende eindcijfers zijn doorgegeven aan de cijferadministratie voor registratie in usis.


Het eerstejaarsvak Algoritmiek is verplicht voor alle studenten Informatica, AI, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 6 EC op.

Studenten Bioinformatica / Informatica en Econonie

Voor studenten Bioinformatica en voor studenten Informatica en Economie is er het vergelijkbare vak Algorithms and Data Structures (met Python in plaats van C++).

Praktische informatie

Docent: Rudy van Vliet
te vinden op: kamer 140 van het Snellius
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistenten practicum: Het speciale emailadres wordt niet meer gebruikt. Bij vragen, mail de docent.
Onderwijsvorm: weblectures voor hoorcollege en werkcollege, online vragenuren en drie programmeeropdrachten met on-campus practicumbijeenkomsten
Collegetijden: hoorcollege als weblecture op woensdag, 14.15-16.00
werkcollege als weblecture op donderdag, 14.15-15.00
interactief vragenuur op donderdag, 15.15-16.00, in de Kaltura liveroom,
allemaal van Rudy van Vliet van 1 februari t/m 25 mei 2021.
Afgezien van weken 1, 2 en 4 is er elke week een practicumbijeenkomst, op dinsdag, 10.30-12.15. Vanwege de verlengde lockdown was deze bijeenkomst tot en met 20 april online, in de Kaltura liveroom. Deze is te bereiken via de Brightspace pagina van Algoritmiek, Course Tools, Kaltura Media Gallery, Join Live Room.
Van 4 t/m 25 mei was de practicumbijeenkomst ook on-campus, in zalen 302-304, 313, 407-409 en 408 van het Snellius.
In de week van 22 t/m 26 maart, en op dinsdag 27 april, woensdag 5 mei en donderdag 13 mei waren er om diverse redenen geen colleges/bijeenkomsten van dit vak.
In afwijking van de eerdere aankondiging blijven de weblectures toch, tot en met het hertentamen, online. Net als andere onderdelen van deze website, zoals de collegeslides.

Aanbevolen 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).

Inhoud van het vak

Algoritmiek gaat uiteraard over algoritmen. Het vak behandelt diverse algemene algoritmische methoden voor het oplossen van problemen, alsmede enkele bekende algoritmen zoals het algoritme van Dijkstra. Elke methode wordt geillustreerd aan de hand van bekende of minder bekende voorbeelden. Probleemoplossingsmethoden die worden behandeld zijn o.a.: Verder kijken we bij veel algoritmen ook naar de tijdcomplexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken).

Voor globale informatie over het vak in studiejaar 2020-2021 wordt men verwezen naar de algemene webpagina.

Doelstelling

Materiaal

In het studiejaar 2020/2021 wordt evenals in de voorgaande jaren gebruik gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, third edition (Pearson, 2012). Of de internationale editie van hetzelfde boek (ISBN: 978-0-273-76411-3).

De bij het college behorende slides komen ook via deze website beschikbaar.

Programma

Het programma van colleges en werkcolleges zal hieronder worden bijgehouden. Voor elke week wordt vermeld welke onderwerpen aan de orde zijn gekomen, met de bijbehorende hoofdstukken uit het boek en de gebruikte slides. Op de laatste pagina van de slides staat overigens doorgaans ook welke stof uit het boek bij het betreffende college hoort. Ten slotte vind je hieronder de bij het werkcollege behandelde opgaven, met (soms) antwoorden. Om vast een idee te krijgen van (de rest van) de te behandelen stof, kunt u kijken op de website van Algoritmiek, voorjaar 2020.

Datum Onderwerp Slides Boek Werkcollege
3 februari Introductie slides1, weblecture 1.1, 1.2, 1.4 (t/m graafrepresentaties) opgaven1, weblecture, antwoorden opgaven 1,2,6-9
10 februari Grafen en bomen slides2, weblecture 1.4, 4.5 (subpar `Searching and Insertion in a BST') opgaven2 voor bomenpracticum, zie verderop voor framework + uitleg
17 februari Complexiteit, toestand-actie-ruimte slides3, weblecture slides, 2.1-2.3, 4.5 (subpar `The Game of Nim') en 6.6 (subpar `Reduction to Graph Problems') opgaven3, weblecture, antwoorden opgaven 1-3,5 (presentatie Jan van Rijn uit 2011), antwoorden opgave 4,6-8, toestand-actie-ruimte bij opgave 4
24 februari Toestand-actie-ruimte, brute force, exhaustive search slides4, weblecture, Kannenprobleem (Die Hard) 3 inl., 3.1-3.3, slides programmeeropdracht 1
3 maart Exhaustive search, backtracking slides5, weblecture, 3.4, 3.5, slides opgaven5, weblecture, antwoorden5
10 maart Backtracking slides6, weblecture 12 inl., 12.1, slides opgaven6, weblecture, antwoorden6, SST opgave 7, SST opgave 8
17 maart Verdeel en heers slides7, weblecture 5.inl, 5.1, 5.2, 5.4 (geen Strassen), 4 inl., 4.1 programmeeropdracht 1
31 maart Rest verdeel en heers, dynamisch programmeren slides8, weblecture slides; 5.5 (geen convex hull), 5.3, 4.2, 4.4 (geen Russian peasant), 4.5 (inl + Binary Search Tree), 8 inl. opgaven8, weblecture, enkele antwoorden
7 april Dynamisch programmeren slides9, weblecture uit 2020 (de opname van dit jaar is mislukt) slides; 8.2, voorbeeld 2 in 8.1 opgaven9, weblecture, antwoorden opgaven 2,3,4,5ac,6, antwoord opgave 7
14 april Gretige algoritmen, algoritme van Dijkstra slides10, weblecture slides, 9 inl., 9.2 t/m blz. 353, 9.3 opgaven10, weblecture, antwoorden van opgaven 1,2,4-7
21 april Algoritme van Dijkstra, gretige algoritmen slides11, weblecture van vorig jaar (nog onduidelijk of de opname van dit jaar is gelukt) slides, 9.1, 9.2 (inclusief implementatie Union Find), 9.3 programmeeropdracht 2
28 april Branch & bound slides12, weblecture 12.2 opgaven12, weblecture, antwoorden van opgaven 1,2,3
19 mei Oud tentamen oefenen weblecture Tentamen van 8 juli 2019

Tentamenstof

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

Opgaven

Tijdens werkcolleges worden opgaven gemaakt die aansluiten bij de stof uit de hoorcolleges. Deze opgaven worden hierboven in de tabel opgenomen.

Practicumbijeenkomsten

In week 3 en elke week vanaf week 5 is een practicumbijeenkomst gepland. De bijeenkomst in week 3 is voor het bomenpracticum, de andere bijeenkomsten zijn bedoeld om, met assistentie, te werken aan de programmeeropdrachten.

Practicumbijeenkomst week 3

Tijdens de practicumbijeenkomst in week 3 wordt er een practicumopdracht rond een implementatie van binaire bomen gedaan, online in de Kaltura liveroom Daarvoor kun je gebruik maken van het volgende framework. 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.

De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen het bestand "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.

Programmeeropdrachten

Bij het vak horen drie programmeeropdrachten in de programmeertaal C++, in elk waarvan een besproken oplossingsmethode toegepast moet worden om een gegeven probleem op te lossen.

De opdrachten moeten alle drie voldoende zijn (>=5.5). Programmeerwerk mag in tweetallen worden gemaakt. De opdrachten dienen op (of voor) de deadlines te worden ingeleverd. Eventueel mag (uiterlijk) twee weken te laat worden ingeleverd, maar dan gaat er voor iedere (gedeeltelijke) week 1 punt van het cijfer af.

Als plagiaat wordt geconstateerd, wordt hiervan melding gemaakt bij de examencommissie, en wordt de beoordeling van de opdracht voor die teams opgeschort, in afwachting van een oordeel van de examencommissie. Een mogelijke sanctie is dat beide teams geen cijfer krijgen en ook geen mogelijkheid krijgen om de opdracht nog in hetzelfde collegejaar af te ronden.

Meer informatie over te laat, niet voldoende en plagiaat...

Studenten die vorig studiejaar alle drie programmeeropdrachten hebben afgerond, hoeven het programmeerwerk dit jaar niet opnieuw te doen. Deelresultaten blijven niet automatisch geldig. Zie ook het paragraafje `Cijfers uit eerdere jaren' verderop.

Je kunt je oplossingen voor de opdrachten inleveren in Brightspace. Daarvoor moet je in Brightspace eerst een groepje vormen (met z'n twee-en of eventueel in je eentje). Ook als je steeds met dezelfde programmeerpartner werkt, moet je voor elke opdracht opnieuw een groepje vormen.

De drie programmeeropdrachten van dit jaar worden t.z.t. hieronder gepubliceerd. Meer informatie, zoals over het schrijven van het verslag in LaTeX en over het werken op de huisuilen, is hier te vinden. Inmiddels is beschikbaar

Eventuele opmerkingen of tips bij de opdrachten zullen hier worden bekendgemaakt.

Toetsing

Schriftelijk tentamen aan het eind van het semester. Het eindcijfer van het vak is een gewogen gemiddelde van de cijfers voor het tentamen (twee derde) en de programmeeropdrachten (samen een derde). Zowel tentamen als (alle) programmeeropdrachten moeten voldoende (>=5.5) zijn.

Wie het tentamen niet haalt, krijgt het (onvoldoende) tentamencijfer als eindcijfer. Wie het tentamen wel haalt, maar de programmeeropdrachten niet (allemaal) heeft afgerond, krijgt nog geen eindcijfer. In dit laatste geval blijft het voldoende tentamencijfer staan totdat het programmeerwerk is afgerond (zie ook het paragraafje `Cijfers uit eerdere jaren' hieronder).

Cijfers uit eerdere jaren

Wie in een eerder jaar het tentamen wel heeft gehaald, maar het practicum nog niet heeft afgerond, kan het (voldoende) tentamencijfer meenemen naar dit jaar.
Wie, omgekeerd, in een eerder jaar het practicum (alle drie de opdrachten) heeft afgerond, maar het tentamen nog niet heeft gehaald, kan het gemiddelde practicumcijfer meenemen naar dit jaar. Dit geldt ook, als een van de drie opdrachten die je hebt gemaakt opdracht 3 van 2020 is (die je niet als losse opdracht kunt meenemen).
Wie in een eerder jaar (of meerdere jaren) één of twee losse opdrachten heeft afgerond, kan de cijfers daarvoor niet per se meenemen naar dit jaar. Het kan wel standaard met de cijfers voor de volgende opdrachten: opdracht 1 2017, opdracht 1 2018, opdracht 2 2018, opdracht 1 2019, opdracht 2 2019, opdracht 3 2019, opdracht 1 2020, opdracht 2 2020. Ouderejaars die zich afvragen of ze cijfers van andere opdrachten mee mogen nemen, moeten contact opnemen met de docent: rvvliet(at)liacs(dot)nl.
Wanneer deelresultaten uit een eerder jaar wel geldig blijven, is het niet nodig en niet de bedoeling om de betreffende opdracht(en) opnieuw te maken. Alle cijfers uit eerdere jaren die in ieder geval nog gelden, staan in Brightspace, althans voor wie zich tijdig voor het vak heeft aangemeld. Dan kun je dus zien wat je nog wel hoeft te doen en wat niet meer. Hierbij geldt de volgende legenda. Mis je (een cijfer van) jezelf, neem dan contact op met de docent.

Tentamens

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Er zijn twee tentamens gepland, allebei on-campus:
Eerste tentamen: 3 juni 2021, 13.00-16.00, on campus in het Universitair Sportcentrum.
Hertentamen: 13 juli 2021, 13.00-16.00, on campus in het Snellius. Zie de richtlijnen tentamens en onderwijs.
Beide tentamens zijn nog terug te vinden in de lijst met oude tentamens onderaan deze pagina. Van het eerste tentamen staat daar ook een handgeschreven uitwerking van de docent.
Beide tentamens zijn nagekeken. De tentamencijfers, inclusief eindcijfers, staan in Brightspace. Hierbij geldt de volgende legenda.

Vragenuur

Op woensdag 2 juni 2021 is er vanaf 13.30 uur een vragenuur voor het tentamen, in de Kaltura Live Room. Daarbij kun je dan de vragen stellen die opgekomen zijn bij het leren voor het tentamen. Het vragenuur duurt maximaal tot 15.30 uur. Als de vragen eerder op zijn, stoppen we ook eerder.

Oude tentamens


Het vak Algoritmiek wordt al vele jaren gegeven. De vorige keer was in het voorjaar van 2020. De website van die keer vindt u hier. U vindt daar ook nog meer oude tentamens.
Vragen en/of opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 23 augustus 2021 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/