Algoritmiek,

voorjaar 2024

Toren Academiegebouw

Laatste nieuws

(01.03.2024) Programmeeropdracht 1 is (grotendeels) beschikbaar. Zie verderop.

(01.03.2024) Op vrijdag 1 maart is er geen werkcollege.

(23.02.2024) Er is een voorbeelduitwerking van het bomenpracticum beschikbaar. Zie verderop.

(07.02.2024) Voldoende cijfers uit eerdere jaren die dit jaar nog geldig zijn, staan in Brightspace. Zie verderop.


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.

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

This course is not intended for students Data Science and Artificial Intelligence, students Bioinformatica and students Informatica en Economie. They follow the course Algorithms and Data Structures, with equivalent content, but in English instead of Dutch, and with Python instead of 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: ...
Onderwijsvorm: per week in principe twee uur hoorcollege, twee uur werkcollege en twee uur practicum, allemaal on-campus.
Collegetijden: van 7 februari t/m 27 mei 2024.
In de week van 25 t/m 29 maart (tentamenweek, Goede Vrijdag), op maandag 1 april (Tweede Paasdag), woensdag 8 mei, vrijdag 10 mei, maandag 20 mei (Tweede Pinksterdag), en woensdag 22 mei zijn er geen colleges/bijeenkomsten van dit vak. 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 2023-2024 wordt men verwezen naar de algemene webpagina.

Doelstelling

Materiaal

In het studiejaar 2023/2024 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 2023.

Datum Onderwerp Slides Boek Werkcollege
7 februari Introductie slides1 1.1, 1.2, 1.4 (t/m graafrepresentaties) opgaven1, antwoorden opgaven 1,2,6-9
14 februari Grafen en bomen slides2 1.4, 4.5 (subpar `Searching and Insertion in a BST') opgaven2 voor bomenpracticum, zie verderop voor skeletprogramma + 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 2,3,5 (presentatie Jan van Rijn uit 2011), antwoorden opgaven 1,2,4,6-8, toestand-actie-ruimte bij opgave 1b, toestand-actie-ruimte bij opgave 4b
28 februari Toestand-actie-ruimte, brute force, exhaustive search slides4, Kannenprobleem (Die Hard) 3 inl., 3.1-3.3, slides

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

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 (19 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 19 februari

Tijdens de practicumbijeenkomst in week 3 (19 februari) wordt er een practicumopdracht rond een implementatie van binaire bomen gedaan, in de computerzalen van het Snellius. Daarvoor kun je gebruik maken van het skeletprogramma in bomenpracticum.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.
N.B.: je hoeft je oplossing niet in te leveren.

De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen het bestand "readmelinux.txt".

Een voorbeelduitwerking is 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 in veel (maar niet alle!) gevallen ook 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 huisuil, is hier te vinden. Inmiddels is beschikbaar: