(24.09.2024)
De laatste inzendingen voor de eerste kans van programmeeropdracht 3
zijn nagekeken.
De deadline voor de herkansing van deze opdracht is
vrijdag 25 oktober 2024, 23.59 uur.
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 BM.2.03 van het (nieuwe) Gorlaeus
telefoon: even geen telefoon...
email: rvvliet(at)liacs(dot)nl Assistenten werkcollege en practicum: ...
Voor vragen over de programmeeropdrachten zijn de assistenten 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:
hoorcollege van Rudy van Vliet op woensdag, 15.15-17.00 in de Sitterzaal
in het Oortgebouw
(alleen op 14, 21, 28 februari en 6 maart in zaal C1 van schotel Gorlaeus)
werkcollege van de assistenten,
op vrijdag,
13.15-15.00, in diverse zalen in Snellius (meestal), Huygens en Sylvius.
practicumbijeenkomst op maandag, 13.15-15.00 in zalen 302-304, 303,
306-308, 307, 309 en 411 van het Snellius
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.:
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 2023-2024
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 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.
De tentamenstof bestaat uit: alles wat we gedurende het semester
bij hoorcollege, werkcollege en practicum hebben behandeld.
Dit is in de loop van het semester opgebouwd op deze website,
in het bijzonder hierboven bij het programma.
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:
Download het .zip-bestand, en zet het in de gewenste directory
(niet online openen dus!)
Pak het skeletprogramma uit
(onder Linux kan dat bijvoorbeeld met "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 skeletprogramma 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.
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.
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:
specificatie opdracht 1
Grotendeels gepubliceerd: donderdag 29 februari/vrijdag 1 maart 2024.
Nader uitgewerkt: maandag 4 maart 2024 (nu bijna compleet).
Correctie in beschrijving leesInSpel (nu consistent met skeletprogramma):
woensdag 6 maart 2024.
Helemaal compleet gemaakt, inclusief beschrijving verslag,
zaterdag 9 maart 2024.
een compleet
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: donderdag 29 februari/vrijdag 1 maart 2024.
enkele extra
voorbeeldbestanden,
waar je voor het verslag onderzoek naar moet doen
Gepubliceerd: vrijdag 8 maart 2024.
twee tips:
De uitkomst van besteScore bij spel1.txt zou 0 moeten zijn (als score).
Zorg ervoor dat doeZet en unDoeZet ook goed werken
als de pot leeg is, maar er nog wel tegels op de schalen liggen. Dit
kan bijvoorbeeld gebeuren bij doorrekenen van spel3.txt.
Deze opdracht is nagekeken. De cijfers staan in
Brightspace.
De deadline voor de herkansing van deze opdracht is vrijdag 28 juni 2024,
23.59 uur.
specificatie opdracht 2
Gepubliceerd: zondag 7 / maandag 8 april 2024.
Aanvulling over het gebruik van de klasse Steen (in rood), 17 april 2024.
Deadline verschoven naar maandag 6 mei 2024, 23.59 uur (in PDF staat nog
oude datum), 26 april 2024.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: zondag 7 / maandag 8 april 2024.
Een tip bij het verslag: om te beredeneren hoeveel verschillende
oplossingen er zijn op het 4x5 bord met de stenen uit Figuur 2, lijkt
het handig om te beginnen met de mogelijkheden voor stenen 4 en 5.
Een klein, vierde voorbeeld van een bestand met stenen is
stenen4.in.
Op een 3x3 bord zijn er, als je rekening houdt met symmetrie, acht
oplossingen met deze stenen.
Deze opdracht is nagekeken. De cijfers staan in
Brightspace.
De deadline voor de herkansing van deze opdracht is woensdag 14 augustus
2024, 23.59 uur.
specificatie opdracht 3
Gepubliceerd: dinsdag 7 / woensdag 8 mei 2024.
Normering en `late' deadlines ingevuld, maandag 13 mei 2024.
een
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: dinsdag 7 / woensdag 8 mei 2024.
Deze opdracht is nagekeken. De laatste cijfers komen nog in
Brightspace.
De deadline voor de herkansing van deze opdracht is vrijdag 25 oktober
2024, 23.59 uur.
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:
2017 (opdracht 1), 2018 (1,2), 2019 (1,2,3), 2020 (1,2), 2021 (1,2,3),
2022 (1,2,3), 2023 (1,2,3).
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 7 februari 2024 zijn cijfers uit eerdere jaren die nog geldig zijn
in Brightspace
gezet.
Althans, voor studenten die op dat moment in Brightspace waren ingeschreven.
Hierbij geldt de volgende
legenda.
Mis je een cijfer van jezelf, neem 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 (in totaal, over alle jaren)
proberen om een reeds voldoende deelresultaat te verbeteren.
Tentamens
Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens
het tentamen.
Er zijn twee tentamens gepland, allebei on-campus:
Eerste tentamen: maandagmiddag 10 juni 2024, 13.00-16.00
in het Universitair Sportcentrum.
Hertentamen: maandagmiddag 8 juli 2024,
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. Bij het eerste tentamen staat daar ook een uitwerking
van de docent.
Beide tentamens zijn nagekeken.
De cijfers, inclusief eindcijfers, staan in
Brightspace.
Vragenuur
Op vrijdag 7 juni is er een vragenuur voor het tentamen, vanaf 15.00 uur,
in zaal BW.0.30 van het (nieuwe) Gorlaeus.
Daarbij kun je de vragen stellen die opgekomen zijn bij
het leren voor het tentamen.
Het vragenuur duurt maximaal tot 17.00 uur. Als de vragen eerder op zijn,
stoppen we ook eerder.
Het vak Algoritmiek wordt al vele jaren gegeven.
De vorige keer was in het voorjaar van 2023. 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: 24 september 2024
- https://liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/
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).
