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 Algorithmics (met Python in plaats
van C++). Ouderejaars van deze twee varianten, die in een eerder jaar
al actief hebben meegedaan aan Algoritmiek (door bijvoorbeeld opdrachten
in te sturen of een tentamen te maken), mogen kiezen of ze verder gaan
met Algoritmiek of dat ze Algorithmics doen.
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 drie programmeeropdrachten Collegetijden:
hoorcollege dinsdag,
van 11.15-13.00 uur van Rudy van Vliet, in de Havingazaal in het Gorlaeus;
werkcollege dinsdag,
van 14.15-16.00 uur van de assistenten, in zalen 412, 403 en 405
in het Snellius;
van 4 februari tot en met 19 mei 2020.
Op de dinsdagen 24 maart en 5 mei
zijn er om diverse redenen geen colleges van dit vak.
In vier van de weken is er geen werkcollege in een collegezaal,
maar een practicumbijeenkomst in de computerzalen. Dit wordt nog aangegeven.
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
(en Economie/Bioinformatica)).
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 2019-2020
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 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.
Omdat de tentamens online worden, en daarmee ook open-boek, zullen
er minder (of geen) directe weetvragen gesteld worden. Er zal meer getoetst
worden op inzicht, bedenken van ad-hoc algoritmes, en het toepassen
van algoritmes.
Opgaven
Tijdens werkcolleges worden opgaven gemaakt, meestal op papier,
soms achter de computer. Deze opgaven worden hierboven in de tabel opgenomen,
maar zullen ook tijdens het werkcollege worden uitgedeeld.
Tweede werkcollege
Tijdens het tweede werkcollege is er een practicumopdracht gedaan
in de computerzalen van het Snellius.
Daarvoor kon 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.
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".
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 krijgen de betrokken teams in principe
geen cijfer voor de betreffende opdracht en dit collegejaar ook geen
mogelijkheid om de opdracht alsnog te doen.
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.
Meer informatie, zoals over het schrijven van het verslag in LaTeX en
over het werken op de huisuilen,
is hier
te vinden.
Alle opdrachten zijn nagekeken, en ook de herkansingen.
U vindt de cijfers in
Blackboard.
Hierbij geldt de volgende
legenda.
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.
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.
Tentamens
Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens
het tentamen.
Er zijn twee tentamens geweest:
Eerste tentamen: donderdag 4 juni 2020, 14.15-17.15 uur,
online, met behulp van platform ANS.
Dit tentamen is nog terug te vinden in de lijst met oude tentamens onderaan,
inclusief een uitwerking van de docent.
Hertentamen: maandag 6 juli 2020, 14.15-17.15,
online, met behulp van platform ANS.
Beide tentamens zijn nagekeken.
Alle cijfers, inclusief eindcijfers, staan in
Blackboard.
Hierbij geldt de volgende
legenda.
Online tentamens
De tentamens dit jaar waren online.
We maken hiervoor gebruiken van het digitale tentamenplatform Ans.
Als het goed is, zijn alle studenten die op 25 mei 2020 in Blackboard
stonden aangemeld voor een oefententamen. Zij zullen door ons ook
worden aangemeld voor het echte tentamen. Er is een korte
instructie voor het werken met Ans.
Omdat het tentamen online wordt gehuden, zal het een open boek karakter
hebben. Je mag het boek, de slides, en al het andere materiaal op deze
website gebruiken bij het maken van het tentamen. Dit betekent wel dat
het type vragen mogelijk iets anders wordt dan bij tentamens in eerdere
jaren: geen/minder directe weetvragen, en meer vragen naar inzicht / bedenken
van ad hoc algoritmes / toepassing en analyse van algoritmes.
Het is niet toegestaan om bij het tentamen samen te werken, noch met
elkaar, noch met andere personen. Het is ook niet toegestaan om
antwoorden letterlijk te kopieren uit het beschikbare materiaal.
Formuleer je antwoorden altijd in je eigen woorden.
Als onderdeel van het tentamen moet je ook schriftelijk bevestigen
dat je het tentamen zelf hebt gemaakt.
We zullen je tijdens het tentamen niet met webcams in de gaten
houden. Wel is het onze bedoeling om met de beschikbare tools
te controleren op mogelijk plagiaat, net zoals bij de programmeeropdrachten
gebeurt.
Vragenuur
Op dinsdag 2 juni 2020 was er vanaf 14.15 uur een vragenuur voor
het tentamen, in de Kaltura Live Room.
Daarbij kon je de vragen stellen die opgekomen waren bij
het leren voor het tentamen.
Oude tentamens
De tentamens in eerdere jaren waren geen open boek tentamens.
De tentamens van dit jaar kunnen dus een iets ander karakter
hebben.
Het vak Algoritmiek wordt al vele jaren gegeven.
De vorige keer was in het voorjaar van 2019. 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: 17 mei 2021
- http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/
In het studiejaar 2019/2020 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).