Algoritmiek,

voorjaar 2020

Toren Academiegebouw

Laatste nieuws

Ook de herkansingen voor opdracht 3 zijn nagekeken. Cijfers staan in Blackboard. Eindcijfers volgen binnen een paar dagen.


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.: 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

Materiaal

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).

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 2019.

Datum Onderwerp Slides Boek Werkcollege
4 februari Introductie slides1 1.1, 1.2, 1.4 (t/m graafrepresentaties) opgaven1, antwoorden opgaven 1,2,6-9
11 februari Grafen en bomen slides2 1.4, 4.5 (subpar `Searching and Insertion in a BST') opgaven2, zie verderop voor framework + uitleg
18 februari Complexiteit, toestand-actie-ruimte slides3 slides, 2.1-2.3, 4.5 (subpar `The Game of Nim') en 6.6 (subpar `Reduction to Graph Problems') opgaven3, antwoorden opgaven 1-3,5 (presentatie Jan van Rijn uit 2011), antwoorden opgave 4,6-8, toestand-actie-ruimte bij opgave 4
25 februari Toestand-actie-ruimte, DFS-BFS, brute force slides4 3 inl., 3.1-3.3, 3.5, slides programmeeropdracht 1
3 maart Brute force, exhaustive search, backtracking slides5 3.4, slides opgaven5, antwoorden5
10 maart Backtracking slides6 12 inl., 12.1, slides opgaven6, antwoorden6, SST opgave 7, SST opgave 8
1 april Verdeel en heers slides7, weblecture 5.inl, 5.1, 5.2, 5.4 (geen Strassen), 4 inl., 4.1 opgaven7, enkele antwoorden7, weblecture
8 april Rest verdeel en heers, dynamisch programmeren slides8, weblecture slides; 5.5 (geen convex hull), 5.3, 4.2, 4.4 (geen Russian peasant), 4.5 (inl + Binary Search Tree), 8 inl. programmeeropdracht 2
15 april Dynamisch programmeren slides9, weblecture slides; 8.2, voorbeeld 2 in 8.1 opgaven9, antwoorden opgaven 2,3,4,5ac,6, antwoord opgave 7, weblecture
22 april Gretige algoritmen, algoritme van Dijkstra slides10, weblecture slides, 9 inl., 9.2 t/m blz. 353, 9.3 opgaven10, antwoorden van opgaven 1,2,4-7, weblecture
29 april Algoritme van Dijkstra, gretige algoritmen slides11, weblecture slides, 9.1, 9.2 (inclusief implementatie Union Find), 9.3 geen werkcollege, wel vragenuur
6 mei Branch & bound slides12, weblecture 12.2 opgaven12, antwoorden van opgaven 1,2,3, weblecture

Tentamenstof

De tentamenstof bestaat uit: alles wat we gedurende het semester behandelen. Dat komt op het volgende neer: 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 wordt er een practicumopdracht gedaan in de computerzalen van het Snellius. Daarvoor kun je gebruik maken van het volgende framework. Volg de volgende stappen om te beginnen: 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 krijgen de betrokken teams in principe geen cijfer voor de betreffende opdracht en dit collegejaar ook geen mogelijkheid om de opdracht alsnog te doen.

Meer informatie over te laat, niet voldoende en plagiaat...

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.

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

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. 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 Blackboard. 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:
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 zijn 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.

Je kunt je eigen computer of laptop gebruiken om het tentamen te maken. Heb je geen geschikte apparatuur, dan kun je wellicht tijdelijk een laptop van de universiteit lenen, zie hier.

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 dan 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: 25 september 2020 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/