Algoritmiek,

voorjaar 2023

Toren Academiegebouw

Laatste nieuws

De herkansing voor programmeeropdracht 1 is (eindelijk) helemaal nagekeken. Zie verderop.

Programmeeropdracht 3 is (eindelijk) helemaal nagekeken. De deadline voor de herkansing is vastgesteld op vrijdag 27 oktober 2023, 23.59 uur.

Je oplossing voor de herkansing van een programmeeropdracht kun je in Brightspace gewoon bij de betreffende opdracht inleveren. Op dezelfde plek dus waar je voor de eerste kans kon inleveren.


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

Studenten Data Science and Artificial Intelligence / Bioinformatica / Informatica en Econonie

Voor studenten Data Science and Artificial Intelligence, studenten Bioinformatica en 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 werkcollege en practicum: Hanjo Boekhout, Perri van den Berg, Rogier van den Burgh, Amber van den Broek, Sara Kooistra, Rob Mourits, Steven van Popele. Voor vragen over de programmeeropdrachten zijn zij bereikbaar via het speciale emailadres algoritmiek@liacs.leidenuniv.nl
Onderwijsvorm: per week in principe twee uur hoorcollege, twee uur werkcollege en twee uur practicum, allemaal on-campus.
Collegetijden: van 7 februari t/m 17 mei 2023.
Op woensdagmiddag 8 februari (Dies), de week van 27 t/m 31 maart (tentamenweek), en de vrijdagen 7 april (Goede Vrijdag) en 5 mei (bevrijdingsdag) zijn er geen colleges/bijeenkomsten van dit vak. De practicumbijeenkomst op 22 februari en het werkcollege op 17 februari 2023 vervallen. In de loop van het semester zullen nog enkele ingeroosterde werkcolleges vervallen.

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

Doelstelling

Materiaal

In het studiejaar 2022/2023 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. Om vast een idee te krijgen van de te behandelen stof, kunt u kijken op de website van Algoritmiek, voorjaar 2022.

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

Tentamenstof

De tentamenstof bestaat uit: alles wat we gedurende het semester bij hoorcollege, werkcollege en practicum behandelen. Dit zal in de loop van het semester worden opgebouwd op deze website, in het bijzonder hierboven bij het programma. Het zal echter weinig afwijken van de tentamenstof van het vak in voorjaar 2022.

Werkcollege

Tijdens het werkcollege worden opgaven op papier gemaakt die aansluiten bij de stof uit de hoorcolleges. Deze opgaven worden hierboven in de tabel opgenomen.

Practicumbijeenkomsten

In week 3 (22 februari) en elke week vanaf week 4 of 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, in de computerzalen van het Snellius. Daarvoor kun je gebruik maken van het volgende .zip. 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 in een eerder 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.

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 huisuil, is hier te vinden. Inmiddels is beschikbaar:

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

Toetsing

Drie programmeeropdrachten in de loop van het semester, en schriftelijk tentamen aan het eind van het semester. Het minimumcijfer voor elke programmeeropdracht is 0, het minimumcijfer voor het tentamen is 1. Zowel tentamen als (alle) programmeeropdrachten moeten voldoende (>=5.5) zijn. In dat geval is het eindcijfer van het vak een gewogen gemiddelde van de cijfers voor het tentamen (twee derde) en de programmeeropdrachten (samen een derde).

Als het tentamencijfer minder dan 5.5 is, is het tentamencijfer tevens het eindcijfer. Als het tentamen voldoende is, maar niet alle programmeeropdrachten voldoende zijn, volgt er 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.
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, opdracht 1 2021, opdracht 2 2021, opdracht 3 2021, opdracht 1 2022, opdracht 2 2022, opdracht 3 2022.
Ouderejaars die zich afvragen of ze cijfers van andere opdrachten mee mogen nemen, moeten contact opnemen met de docent: rvvliet(at)liacs(dot)nl.
Op 24 februari 2023 zijn cijfers van eerdere jaren die nog geldig zijn door de docent alvast in Brightspace gezet. Althans, voor zover de betreffende studenten op dat moment al in Brightspace geregistreerd waren, en vorig jaar ook in Brightspace geregistreerd waren. Hierbij geldt de volgende legenda.
Hier kun je dus zien wat je nog wel hoeft te doen en wat niet meer. Mis je (een cijfer van) jezelf, neem dan contact op met de docent.
Wanneer deelresultaten uit een eerder jaar geldig blijven, is het niet nodig en niet de bedoeling om de betreffende opdracht(en) opnieuw te maken. Je mag hoogstens één keer proberen om een reeds voldoende deelresultaat te verbeteren.

Tentamens

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Er zijn twee tentamens geweest, allebei on-campus:
Eerste tentamen: maandagmiddag 12 juni 2023, 13.00-16.00 in het Universitair Sportcentrum.
Hertentamen: maandagmiddag 17 juli 2023, 13.00-16.00 uur eveneens in het Universitair Sportcentrum.
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 cijfers, in veel gevallen inclusief eindcijfers, staan in Brightspace. Hierbij geldt de volgende legenda.

Vragenuur

Op vrijdagochtend 9 juni was er een vragenuur voor het tentamen. Daarbij kon je dan de vragen stellen die opgekomen waren bij het leren voor het tentamen.

Oude tentamens


Het vak Algoritmiek wordt al vele jaren gegeven. De vorige keer was in het voorjaar van 2022. 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: 28 september 2023 - https://liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/