De laatste eindcijfers (na herkansing voor opdracht 3) zijn doorgegeven
aan de cijferadministratie. Hopelijk worden ze snel verwerkt.
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 werkcollege en practicum: ...
Onderwijsvorm: hoorcollege, werkcollege en practicumbijeenkomsten,
in principe (als de coronasituatie het toestaat) allemaal on-campus.
De hoorcolleges zullen waarschijnlijk ook wel live worden gestreamd
en achteraf als weblectures zijn na te kijken, via
deze link.
Collegetijden:
hoorcollege van Rudy van Vliet op dinsdag, 11.15-13.00 in zaal 3
van het Gorlaeus
werkcollege op dinsdag, 14.15-16.00 in zalen 401, 402, 403 en 405
van het Snellius
practicumbijeenkomst op woensdag, 14.15-16.00 in zalen 302-304, 303,
306-308, 307 en 309 van het Snellius
van 8 februari t/m 25 mei 2022.
De practicumbijeenkomsten op 9 en 23 februari
2022 vervallen.
In de loop van het semester zullen ook enkele ingeroosterde werkcolleges
vervallen.
Op dinsdagmiddag 8 februari, in de week van 28 maart t/m 1 april,
en op woensdag 27 april zijn
er om diverse redenen geen colleges/bijeenkomsten van dit vak.
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.:
toestand-actie-ruimte/state space tree
(als hulp bij het probleemoplossen),
brute force,
exhaustive search
(waaronder depth first search en breadth first search),
verdeel en heers,
backtracking,
dynamisch programmeren,
gretige algoritmen,
en branch-and-bound.
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 2021-2022
wordt men verwezen naar de
algemene webpagina.
Doelstelling
Het leren toepassen van diverse probleemoplossingsmethoden.
Het leren en bestuderen van enige concrete algoritmen.
De bij het college behorende slides komen ook via deze website beschikbaar.
Programma
Het programma van colleges en werkcolleges
is hieronder nog na te kijken.
Voor elke week is 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.
De tentamenstof bestaat uit: alles wat we gedurende het semester behandeld
hebben.
Dat komt op het volgende neer:
De hierboven gegeven slides bij de hoorcolleges.
Alleen slides 18 t/m 21 van hoorcollege 3
(over complexiteit-en-recursie),
slides 29 t/m 32 van hoorcollege 7 (over vermenigvuldiging van grote
integers)
en slides 24 t/m 26 en 41 van hoorcollege 11 (over de correctheid van
het algoritme van Dijkstra en de correctheid van het algoritme van
Kruskal)
hoef je niet te kennen.
De hierboven vermelde delen uit de derde editie van
het boek van Anany Levitin.
De opgaven die bij het werkcollege zijn behandeld,
en die je hierboven nog kunt vinden.
Alles wat bij hoor- en werkcollege en de programmeeropdrachten
aan de orde is gekomen.
Uiteraard moet je behandelde ontwerptechnieken voor algoritmen
ook op nieuwe problemen kunnen toepassen.
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 2 (16 februari) en elke week vanaf week 4 of 5
is een practicumbijeenkomst gepland.
De bijeenkomst in week 2 is voor het bomenpracticum, de andere
bijeenkomsten zijn bedoeld om, met assistentie, te werken aan
de programmeeropdrachten.
Practicumbijeenkomst week 2
Tijdens de practicumbijeenkomst in week 2
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
framework
of als .zip.
Volg de volgende stappen om te beginnen:
Download het framework, en zet het in de gewenste directory.
Pak het framework uit
(onder Linux kan dat bijvoorbeeld met "tar xvfz bomenpracticum.tar.gz"
of "unzip bomenpracticum.zip")
Ga naar de directory "bomenpracticum" (onder Linux kan dat bijvoorbeeld
met "cd bomenpracticum").
Bekijk het bestand "readmelinux.txt"
voor de precieze bedoeling en werking van het programma.
Je kunt het framework desgewenst ook in Codeblocks laden.
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.
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:
specificatie
opdracht 1
Gepubliceerd, maandag 7 maart 2022.
Twee kleine aanvullingen (in rood), wellicht ten overvloede,
zaterdag 2 april 2022.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: maandag 7 maart 2022.
een
aantal tests,
die je kunt uitvoeren (lees het bestand testsVierOpEenRij.txt)
Gepubliceerd: vrijdag 25 maart 2022.
Inleverdatum: woensdag 6 april 2022, 23.59 uur.
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is maandag 11 juli 2022,
23.59 uur.
Ook de inzendingen bij de herkansing zijn nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
Alle cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
specificatie
opdracht 2
Gepubliceerd, vrijdag 8 april 2022.
Compleet gemaakt, met specificatie verslag, vrijdag 15 april 2022.
Aanvulling:
Bij functie bepaalSchemaGretig
moet je in alle gevallen een COMPLEET schema bepalen.
Hiermee wordt bedoeld: een schema met net zo veel rondes (en dus ook net
zoveel posities) als een compleet, geldig schema voor hetzelfde aantal
spelers.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: vrijdag 8 april 2022.
een
testprogramma,
waarmee je schema's kunt controleren die je eigen programma gemaakt
hebt. Je kunt dit zip-bestand wellicht niet openen in je browser, maar
misschien wel downloaden en vervolgens op je eigen computer openen.
Als dat ook niet lukt, kijk dan (op de huisuil) in /scratch/rvvliet,
of in Brightspace.
Lees in het bestand readme.txt hoe je het testprogramma kunt gebruiken.
Gepubliceerd: donderdag 28 april 2022.
Tip:
Gebruik een membervariabele om het deelschema in op te slaan dat
je moet inlezen bij de functie leesInDeelschema.
Tip 2:
Als je je afvraagt hoe je rekening moet houden met symmetrie,
vraag je dan eerst bij equivalente schema's (zoals genoemd in
de opdracht) af welk schema je voorkeur zou hebben om te genereren,
en waarom. Probeer dat `waarom' vervolgens in code te zetten.
Tip 3:
Bij de docent heeft een minimaal schema voor n=8 spelers een waarde
van 62.2222. Laat je echter niet te veel afleiden als je programma op
een iets andere waarde uitkomt. Een kleine rekenfout kan grote gevolgen
hebben.
Inleverdatum:
maandag 2 mei 2022, 23.59 uur.
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is vrijdag 29 juli 2022,
23.59 uur. Lever ook je oplossing voor deze herkansing in via
Brightspace.
Ook de inzendingen bij de herkansing zijn nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
Alle cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
specificatie
opdracht 3
Gepubliceerd, zondag 8 mei 2022.
Compleet gemaakt, met specificatie verslag, maandag 9 mei 2022.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: zondag 8 mei 2022.
Minimale totale kosten voor de drie tekstbestanden met instanties
bij het skeletprogramma:
h1.txt: 55
h2.txt: 137
h3.txt: 100.49
Inleverdatum:
maandag 30 mei 2022, 23.59 uur.
Inleverdatum met 1 punt aftrek:
maandag 6 juni 2022, 23.59 uur.
Inleverdatum met 2 punten aftrek:
maandag 4 juli 2022, 23.59 uur (zodat het niet samenvalt met de tentamens).
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is woensdag
17 augustus 2022, 23.59 uur.
Lever ook je oplossing voor deze herkansing in via
Brightspace.
Ook de inzendingen bij de herkansing zijn nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
Alle cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
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.
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.
Ouderejaars die zich afvragen of ze cijfers van andere opdrachten mee mogen
nemen,
moeten contact opnemen met de docent: rvvliet(at)liacs(dot)nl.
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.
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.
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: donderdagmiddag 9 juni 2022, 14.15-17.15
on campus in zaal 4-5 van het Gorlaeus.
Hertentamen: dinsdagmiddag 19 juli 2022,
13.00-16.00 uur
on campus in de grote sporthal van 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, inclusief eindcijfers, staan in
Brightspace.
Hierbij geldt de volgende
legenda.
Vragenuur
Op dinsdagochtend 7 juni is er een vragenuur voor het tentamen,
vanaf 11.15 uur, in zaal 312 van het Snellius.
Daarbij kun je dan de vragen stellen die opgekomen zijn bij
het leren voor het tentamen.
Het vragenuur duurt maximaal tot 13.15 uur. Als de vragen eerder op zijn,
stoppen we ook eerder.
Tentamen van 6 juli 2020.
Dit was een online tentamen en daarmee ook een open boek tentamen.
Het type vragen was dan ook wellicht iets anders dan gebruikelijk.
Tentamen van 4 juni 2020,
met de handgeschreven
uitwerking
van de docent.
Dit was een online tentamen en daarmee ook een open boek tentamen.
Het type vragen was dan ook wellicht iets anders dan gebruikelijk.
Het vak Algoritmiek wordt al vele jaren gegeven.
De vorige keer was in het voorjaar van 2021. 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 2022
- https://liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/
In het studiejaar 2021/2022 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).