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:
hoorcollege van Rudy van Vliet op dinsdag, 11.00-12.45 in de Sitterzaal
in het Oortgebouw (februari/maart)
en dinsdag,
13.15-15.00 in zaal 313
van het Snellius
(april/mei)
werkcollege van de assistenten,
op vrijdag,
13.15-15.00, in zaal 313
van het Snellius;
na afloop zullen van de werkcolleges weblectures
uit 2021 gepubliceerd worden
practicumbijeenkomst op woensdag, 13.15-15.00 in zalen 302-304, 303,
306-308, 307 en 309 van het Snellius
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.:
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 2022-2023
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.
Om vast een idee te krijgen van
de te behandelen stof, kunt u kijken op de
website van Algoritmiek, voorjaar 2022.
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:
Download het framework, en zet het in de gewenste directory
(niet online openen dus!)
Pak het framework 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 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
Begin gepubliceerd, maandag 6 maart 2023.
Compleet gemaakt, vrijdag 10 maart 2023.
een compleet
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd: maandag 6 maart 2023.
Kijk voor het invullen van de TODO's in territorium.cc eerst
in territorium.h om te zien wat er in een memberfunctie moet gebeuren.
In aanvulling op territorium.h: de constructor van klasse Territorium
met parameters moet ook een vulvolgorde bepalen voor de lege vakjes.
Dit moet een random volgorde zijn.
Enkele uitkomsten van besteScore:
bord1.txt: besteScore voor speler 2: -3
bord2.txt: besteScore voor speler 1: 1
bord3.txt: besteScore voor speler 1: -2
bord4.txt: besteScore voor speler 2: 2
Eigenlijk was de bedoeling dat parameter aantalStanden van
functie besteScore in die functie zelf op 0 ge-initialiseerd zou
worden. Voor jullie gemak mag je ervan uitgaan dat hij al voor
aanroep van de functie op 0 ge-initialiseerd is. Dat mag je dan
ook aanpassen in main.cc.
Een nuttige test voor doeZet en unDoeZet is om een aantal zetten
te doen, tussendoor een paar keer bepaalZet aan te roepen, dan
een aantal zetten ongedaan te maken, en daar tussendoor ook een
paar keer bepaalZet aan te roepen. Krijg je tijdens het doen van
zetten dezelfde zetten te zien als tijdens het ongedaan maken
van de zetten?
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is woensdag 12 juli 2023,
23.59 uur.
Ook de herkansing is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
(complete!)
specificatie opdracht 2
Gepubliceerd, woensdag 12 april 2023.
Compleet gemaakt, dinsdag 18 april 2023.
In afwijking van de specificatie is de uiterste inleverdatum
maandag 8 mei 2023, 23.59 uur.
een
(nu echt!)
compleet
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd, woensdag 12 april 2023.
Compleet gemaakt, dinsdag 18 april 2023.
Alleen de functie maakPuzzelMetWaardeReeksGretig is toegevoegd aan
puzzel.h en puzzel.cc, en aan het hoofdmenu in main.cc.
Bestand reeks1.txt
ontbrak nog in het skeletprogramma. Bij dezen alsnog,
woensdag 26 april 2023.
Bij memberfunctie doeExperiment wordt geen postconditie genoemd.
Het is dus niet verplicht (maar natuurlijk wel netjes)
om de puzzel na afloop terug te brengen in de toestand bij aanroep,
woensdag 3 mei 2023.
Punten om op te letten (mede om aftrek te voorkomen):
Houd je aan de aanwijzingen in de paragrafen
Enkele tips bij het programmeren en
Algemene opmerkingen in de specificatie.
Gebruik geen (of in ieder geval zo weinig mogelijk) hard-coded
constantes zoals 12 voor MaxDimensie in je programma.
Maak memberfuncties en membervariabelen van een klasse alleen public
als de gebruiker er bij moet kunnen (van membervariabelen is dat
overigens moeilijk voor te stellen). Hulpfuncties zijn dus ook private.
Als een andere klasse er bij moet kunnen (maar de gebruiker niet), kun
je ook gebruik maken van de `friend class' constructie.
Laat geen aanwijzingen `TODO' achter in de code.
Als je verschillende stukken code hebt die sterk op elkaar lijken,
probeer er dan een hulpfunctie van te maken, eventueel met een parameter
om verschillende varianten mee aan te duiden (zoals parameter slim in
bepaalOplossingBT en bepaalAlleOplossingenBT).
Je mag er niet vanuit gaan
dat parameter aantalDeeloplossingen een
bepaalde waarde heeft (de waarde 0 bijvoorbeeld), bij aanroep van
bepaalOplossingBT of bepaalAlleOplossingenBT. Initialisatie van deze
teller moet dus in de functie zelf gebeuren. Dat kan bijvoorbeeld door
de functie als wrapper functie te gebruiken die een recursieve
hulpfunctie aanroept waar het grote werk gebeurt. Net zo voor parameter
oplossing.
Bij het skeletprogramma is een hoofdprogramma main.cc geleverd, waarin
de belangrijkste functies van klasse Puzzel pas aangeroepen worden
als het inlezen gelukt is. Bij het testen zullen we een ander
hoofdprogramma gebruiken, waarin die belangrijke functies ook
aangeroepen kunnen worden als er niet ingelezen is, of als het inlezen
mislukt is.
Bij de memberfunctie haalWaardeWeg hoeft de waarde die je weghaalt niet
per se de laatst ingevulde waarde te zijn. Het mag zelfs een waarde zijn
die je ingelezen hebt uit het tekstbestand met de puzzel.
Het klinkt misschien raar dat je dan feitelijk
de ingelezen puzzel wijzigt, maar je hebt die mogelijkheid nodig om
een zinvol experiment te kunnen draaien. Als je de functie haalWaardeWeg
bij het backtracken gebruikt, zal het overigens waarschijnlijk wel om
de laatst ingevulde waarde gaan.
Het is mogelijk (eigen ervaring en ik hoorde het ook van een student)
dat de slimme variant voor sommige puzzels veel meer tijd kost dan
de standaard variant. Als je dit tegenkomt, ligt dat dus niet per se
aan een fout in je code.
Als je programma uit meer bestanden bestaat dan het skeletprogramma
(bijvoorbeeld voor een extra klasse), stuur dan ook een aangepaste
Makefile mee.
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is donderdag
24 augustus 2023, 23.59 uur.
Ook de herkansing is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
(complete!)
specificatie opdracht 3
Begin gepubliceerd, maandag 8 mei 2023.
Compleet gemaakt, woensdag 10 mei 2023.
Er is via email (van vrijdagavond 19 mei 2023) enige nadere uitleg
over de bedoeling van de opdracht gegeven.
een compleet
skeletprogramma,
waarop je verder kunt bouwen.
Gepubliceerd, maandag 8 mei 2023.
Deze opdracht is nagekeken.
Iedereen heeft de beoordeling van zijn/haar inzending ontvangen.
De deadline voor de herkansing van deze opdracht is vrijdag
27 oktober 2023, 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:
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.
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/
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).