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.:
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 2020-2021
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
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.
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)
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 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:
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").
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 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
specificatie
opdracht 1
Gepubliceerd, woensdag 24 februari 2021.
Vier korte aanvullingen (in rood), vrijdag 26 februari 2021.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: woensdag 24 februari 2021.
Wellicht ten overvloede: het `nummer van de steen' i dat in een zet
(een object van de klasse Zet)
moet worden opgeslagen, is het nummer in de volgorde van inlezen
uit het tekstbestand. De eerste steen die wordt ingelezen heeft
nummer 0, de tweede steen heeft nummer 1, enzovoort.
Voor wie nog niet echt begonnen is: het lijkt raadzaam om een klasse
Steen te definieren, waarin je de vier getallen van een steen kunt
opslaan.
Als de speler-aan-beurt met de stenen in haar hand geen steen kan
neerleggen, moet de functie bepaalMogelijkeZetten een lege vector
retourneren. Dit is dus ook het geval als ze wel een steen zou kunnen
neerleggen, als ze eerst een steen uit de pot heeft gehaald.
Als de speler-aan-beurt een steen uit de pot moet halen, en ze kan
die meteen neerleggen, dan mag dat op elk mogelijk vakje met elke
mogelijke rotatie. Dat gebeurt echter niet in de functie
haalSteenUitPot zelf, maar `gewoon' met een aanroep van doeZet
NA de aanroep van haalSteenUitPot.
Enkele uitkomsten voor testinstanties bij het skeletprogramma:
ao1.txt: aan begin 4 mogelijke zetten voor speler 1,
bestescore=1 voor die speler
ao2.txt: aan begin 9 mogelijke zetten voor speler 1,
bestescore=2 voor die speler
ao3.txt: aan begin 1 mogelijke zet voor speler 1,
bestescore=-2 voor die speler
ao4.txt: aan begin 1 mogelijke zet voor speler 1,
bestescore=-1 voor die speler
Er is een
voorbeeld van een automatische test beschikbaar.
Daarin zitten ook bovenstaande uitkomsten voor ao1.txt t/m ao4.txt.
Pak het pakketje uit, en lees de readme.txt.
Het werkt in ieder geval op de huisuil.
Inleverdatum: maandag 29 maart 2021, 23.59 uur.
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Alle inzendingen voor deze opdracht zijn nagekeken.
De resulterende cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
Als je inzending technisch niet voldoende was, of je hebt geen oplossing
ingeleverd, dan kun je deze opdracht eenmalig herkansen/aanvullen
met deadline vrijdagavond 2 juli, 23.59 uur.
Haal je die deadline niet, dan is het voorjaar van 2022 de eerstvolgende
gelegenheid om de opdracht te halen.
specificatie
opdracht 2 (compleet)
Gepubliceerd, nog zonder specificatie verslag, woensdag 7 april 2021
Compleet gemaakt, inclusief specificatie verslag en
inclusief zalensymmetrie,
maandag 12 april 2021.
Kleine wijziging bij de zalensymmetrie: bij gretige algoritme hoef
je er geen rekening mee te houden, dinsdag 13 april 2021.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd, woensdag 7 april 2021.
Oud commentaar in main.cc gecorrigeerd, donderdag 8 april 2021.
Foute waarde 3 op regel 9 van rooster1.txt vervangen door 4,
zaterdag 10 april 2021.
Foute tracknummers op laatste regel van rooster1.txt gecorrigeerd,
en een preconditie toegevoegd aan functie drukAfRooster in rooster.h,
maandag 12 april 2021.
Fout in
Makefile
gecorrigeerd: aan regel voor main.o ook constantes.h toegevoegd,
vrijdag 23 april 2021.
Nog drie voorbeeldinstanties:
rooster2.txt,
waarvoor een minimaal rooster alleen de eerste vier tijdsloten
(ofwel: de eerste twee dagen) gebruikt
rooster3.txt
Je hoeft je niet per se zorgen te maken als de functies bepaalRooster
en bepaalMinRooster van je programma voor dit voorbeeld onacceptabel
veel tijd nodig hebben, en/of als je functie bepaalRoosterGretig
hiervoor een rooster vindt dat niet aan alle eisen voldoet.
Dat is dan vooral een illustratie van de moeilijkheid van
het roosterprobleem.
rooster4.txt
Voor dit voorbeeld vindt het programma van de docent binnen
anderhalve seconde een rooster (met bepaalRooster) van 9 tijdsloten,
en ook een minimaal rooster (met bepaalMinRooster) van 7 tijdsloten.
Enkele tips:
Het kan handig zijn om een recursieve hulpfunctie te schrijven,
waar het eigenlijke werk voor bepaalRooster en bepaalMinRooster
(het bepalen van een rooster met backtracking) gebeurt.
Om efficient te controleren of een uitbreiding van
een deelrooster nog aan de eisen voldoet, kun je gebruik maken
van, bijvoorbeeld, speciale hulparrays.
Inleverdatum: vrijdagavond 30 april, 23.59 uur voor studenten Informatica
en studenten Wiskunde,
en vrijdagavond 7 mei 23.59 uur voor studenten Kunstmatige Intelligentie.
Teams van studenten uit beide groepen mogen kiezen. Maak je gebruik
van de latere deadline, vermeld dan expliciet welke student(en) in je
team de richting Kunstmatige Intelligentie volgt/volgen.
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Alle inzendingen voor deze opdracht zijn nagekeken.
De resulterende cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
Als je inzending technisch niet voldoende was, of je hebt geen oplossing
ingeleverd, dan kun je deze opdracht eenmalig herkansen/aanvullen
met deadline vrijdagavond 30 juli, 23.59 uur.
Haal je die deadline niet, dan is het voorjaar van 2022 de eerstvolgende
gelegenheid om de opdracht te halen.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd, maandag 3 mei 2021.
Het maximale bedrag bij beurs1.txt is 269.15.
Twee tips:
Als je niet (meer) weet hoe je bits uit een getal isoleert:
met (a >> i)%2 krijg je het i-de bit van achteren,
met i>=0. Eerst alle bits i plekjes naar achteren schuiven,
en dan het achterste bit isoleren.
Het kan handig zijn om een recursieve hulpfunctie te schrijven,
waar het eigenlijke werk voor bepaalMaxBedragRec
(het recursief bepalen van het maximale bedrag (al dan niet met
opslag en hergebruik van berekende deelresultaten)) gebeurt.
Inleverdatum: vrijdagavond 28 mei, 23.59 uur.
Inleverdatum met 1 punt aftrek: maandagavond 21 juni, 23.59 uur.
Inleverdatum met 2 punten aftrek: maandagavond 28 juni, 23.59 uur.
Vergeet niet te controleren dat je programma ook werkt onder Linux
bij LIACS, zie
hier
Alle inzendingen voor deze opdracht zijn nagekeken.
De resulterende cijfers staan
in Brightspace.
Hierbij geldt de volgende
legenda.
Als je inzending technisch niet voldoende was, of je hebt geen oplossing
ingeleverd, dan kun je deze opdracht eenmalig herkansen/aanvullen
met deadline vrijdagavond 13 augustus, 23.59 uur.
Haal je die deadline niet, dan is het voorjaar van 2022 de eerstvolgende
gelegenheid om de opdracht te halen.
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.
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 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/
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).