Algoritmiek,

voorjaar 2018

Toren Academiegebouw

Laatste nieuws

Er is weer een inzending voor opdracht 2 en een inzending voor opdracht 3 goedgekeurd (10 augustus 2018). Zie verderop in het cijferoverzicht.

De eindcijfers na het hertentamen van 9 juli 2018 zijn bekend. Zie verderop in het cijferoverzicht.

Er is een deadline gesteld voor de herkansing van de derde programmeeropdracht: woensdag 15 augustus 2018, 23.59 uur.

Vrijwel alle inzendingen voor het practicum, voor zover ingeleverd voor 27 juli 2018, zijn nagekeken. Zie verderop in het cijferoverzicht.

Zoek je de docent? Hij is in de vakantietijd vooral vaak op dinsdag of vrijdag op het Snellius, vanaf 10.30. Of maak een afspraak.

Als je een herkansing van een opdracht (digitaal) inlevert, lever dan ook het oude verslag (op papier) in. Anders kan er niet worden nagekeken (sorry voor de late melding). Inleveren van het oude verslag kan ook na inzending van de nieuwe oplossing nog. In persoon bij de docent, in zijn postvak in kamer 156a, of in de speciale doos buiten kamer 140.


Het eerstejaarsvak Algoritmiek is verplicht voor alle studenten Informatica, Informatica en Biologie, Informatica en Economie, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 6 EC op.

Practische 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, Sebastiaan Brand, Jacob Jonkman, David Nieuwenhuizen
Onderwijsvorm: hoorcollege, werkcollege en drie programmeeropdrachten
Collegetijden: hoorcollege vrijdag, meestal van 11.00-12.45 uur van Rudy van Vliet, in wisselende zalen.
werkcollege vrijdag, meestal van 13.30-15.15 uur van de assistenten, in wisselende zalen.
van 9 februari tot en met 1 juni 2018. Op de vrijdagen 16 maart, 30 maart, 27 april en 11 mei 2018 zijn er om diverse redenen geen colleges van dit vak.

Zowel hoorcollege als werkcollege is in principe in een collegezaal. Alleen op vier vrijdagen vindt het werkcollege plaats in de computerzaal.

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

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 wordt de sorteermethode heapsort behandeld, en komt het begrip complexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken) zijdelings aan de orde.

Voor globale informatie over het vak in studiejaar 2017-2018 wordt men verwezen naar de algemene webpagina.

Doelstelling

Materiaal

In het studiejaar 2017/2018 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 2017.

Datum Onderwerp Slides Boek Werkcollege
9 februari Introductie slides1 1.1, 1.2, 1.4 (t/m graafrepresentaties) opgaven1, antwoorden opgaven 7-9
16 februari Grafen en bomen slides2 1.4, 4.5 (subpar `Searching and Insertion in a BST') opgaven2
23 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
2 maart Toestand-actie-ruimte, exhaustive search slides4 slides; 3.5 Programmeeropdracht 1
9 maart Brute force, exhaustive search slides5 3 inl., 3.1-3.4, slides opgaven5, antwoorden5
23 maart Backtracking slides6 12 inl., 12.1, slides, 5 inl, 5.1 opgaven6, antwoorden6, SST opgave 7, SST opgave 8
6 april Verdeel en heers slides7 4 inl., 4.1, 4.4, 5.2-5.5 opgaven7, enkele antwoorden
13 april Rest decrease and conquer, dynamisch programmeren slides8 slides; 4.5 (inl + Binary Search Tree), 8 inl. Programmeeropdracht 2
20 april Dynamisch programmeren slides9 slides; 8.2, voorbeeld 2 in 8.1 opgaven9, antwoorden opgaven 2,3,6 antwoorden opgaven 4,5ac (presentatie Jan van Rijn uit 2011)
4 mei Gretige algoritmen, algoritme van Dijksta slides10 slides, 9 inl., 9.2 t/m blz. 353, 9.3 opgaven10, antwoorden van opgaven 1,2,4-7
18 mei Algoritme van Dijkstra, heapsort slides11 slides, 9.3, 6.4 Programmeeropdracht 3
25 mei Branch & bound slides12 12.2 opgaven12, antwoorden van opgaven 1,3
25 mei oud tentamen oefenen Tentamen van 10 juli 2017. vragenuur voor tentamen

Tentamenstof

De tentamenstof bestaat uit: alles wat we gedurende het semester behandelen. Dat komt op het volgende neer:

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, krijgen de betrokken teams 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. Ouderejaars studenten die het practicum helemaal niet of slechts gedeeltelijk hebben gedaan, moeten contact opnemen met de docent: rvvliet(at)liacs(dot)nl. Deelresultaten blijven niet automatisch geldig.

De drie programmeeropdrachten van dit jaar zijn:

Meer informatie, zoals over het schrijven van het verslag in LaTeX, is hier te vinden.

Voor vragen/hulp bij de programmeeropdrachten kun je terecht bij de assistenten: Hanjo Boekhout (h.d.boekhout(at)umail(dot)leidenuniv(dot)nl) of David Nieuwenhuizen (d.f.a.nieuwenhuizen(at)umail(dot)leidenuniv(dot)nl).

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.

Tentamens

Grafische/programmeerbare rekenmachines zijn niet toegestaan tijdens het tentamen.

Er zijn twee tentamens gepland:
Eerste tentamen: dinsdag 5 juni 2018, 14.00-17.00 uur, in het Snellius in Leiden.
Hertentamen: maandag 9 juli 2018, 14.00-17.00, in het Snellius in Leiden.
Ook het hertentamen is nagekeken, en alle cijfers zijn bekend, ook de eindcijfers (voor zover die al berekend konden worden), zie het overzicht van cijfers (versie van 10 augustus 2018). Je kunt je nagekeken tentamen inzien bij de docent, als hij aanwezig is.
Beide tentamens zijn nog terug te vinden in het lijstje met oude tentamens onderaan deze pagina. Bij het eerste tentamen is er ook een uitwerking van de docent beschikbaar.

Vragenuur

Op vrijdag 1 juni 2017 was er vanaf 13.30 uur een vragenuur voor het tentamen, in de De Sitterzaal. Daarbij kon je dan die vragen stellen die opgekomen waren bij het leren voor het tentamen.

Oude tentamens


Het vak Algoritmiek wordt al vele jaren gegeven. De vorige keer was in het voorjaar van 2017. 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: 10 augustus 2018 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/