|
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.
LET OP: Deze website is alleen bedoeld voor de eerstejaars studenten Informatica, Informatica en Biologie en studenten die een dubbele propedeuse Wiskunde/Informatica doen. Zij volgen het vak in Leiden. De Haagse studenten (studenten Informatica en Economie) hebben een eigen website.
Het vak Algoritmiek in de studie Informatica is in principe hetzelfde als het vak Algoritmiek in de studie Informatica en Economie. De inhoud is gelijk en de tentamens worden hetzelfde. Alleen de werkcollege-assistenten, de locatie, de collegetijden en de inleverdata voor de practicumopdrachten zijn anders.
In het voorjaar van 2017 is de docent
Rudy van Vliet.
In het Snellius in Leiden is zijn kamer 140.
Zijn email-adres is rvvliet(at)liacs(dot)nl.
Assistentie bij de werkgroep: Sebastiaan Brand.
Extra assistentie bij het practicum:
Hanjo Boekhout (hanjo(dot)boekhout(at)gmail(dot)com),
David Nieuwenhuizen, Ruben van der Waal.
De colleges zijn op vrijdagen van 11.15 tot 13.00 uur. De bijbehorende werkcolleges vinden plaats op dezelfde dagen als de colleges, maar dan van 13.45 tot 15.30 uur. De eerste colleges zijn op vrijdag 3 februari 2017, de laatste op vrijdag 19 mei 2017. Op de vrijdagen 17 maart, 14 april en 5 mei 2017 zijn er om diverse redenen geen colleges van dit vak.
Zowel hoorcollege als werkcollege is in principe in collegezaal B2 in het Snellius. Alleen op vier donderdagen vindt het werkcollege plaats in de computerzalen.
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)).
Voor globale informatie over het vak in studiejaar 2016-2017 wordt men verwezen naar de algemene webpagina.
De bij het college behorende slides komen ook via deze website beschikbaar.
Datum | Onderwerp | Slides | Boek | Werkcollege |
---|---|---|---|---|
3 februari | Introductie | slides1 | 1.1, 1.2, 1.4 (t/m graafrepresentaties) | opgaven1, antwoorden opgaven 7-9, |
10 februari | Grafen en bomen | slides2 | 1.4, 4.5 (subpar `Searching and Insertion in a BST') | opgaven2 |
17 februari | Toestand-actie-ruimte | slides3, Kannenprobleem (Die Hard) | slides, 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), antwoord opgave 4, toestand-actie-ruimte bij opgave 4 |
24 februari | Complexiteit, brute force | slides4 | 2.1-3; 3 inl., 3.1-3 | Programmeeropdracht 1 |
3 maart | Exhaustive search | slides5 | 3.4, 3.5; slides | opgaven5, antwoorden5 |
10 maart | Backtracking | slides6 | 12 inl., 12.1, 5 inl, 5.1 | opgaven6, antwoorden opgaven 1-6 werkcollege 6, antwoord opgave 7 |
24 maart | Verdeel en heers | slides7 | 4 inl., 4.1, 4.4, 5.2-5.5 | opgaven7, enkele antwoorden |
31 maart | Rest decrease and conquer, dynamisch programmeren | slides8 | slides; 4.5 (inl + Binary Search Tree), 8 inl. | Programmeeropdracht 2 |
7 april | Dynamisch programmeren | slides9 | slides; 8.2, voorbeeld 2 in 8.1 | opgaven9, antwoorden opgaven 3, 4, 5ac (presentatie Jan van Rijn uit 2011, met afwijkende nummering) |
21 april | Gretige algoritmen, algoritme van Dijksta | slides10 | sheets, 9 inl., 9.2 t/m blz. 353, 9.3 | opgaven10, antwoorden van opgaven 4-6 |
28 april | Algoritme van Dijkstra, heapsort | slides11 | slides, 9.3, 6.4 | Programmeeropdracht 3 |
12 mei | Branch & bound | sheets12 | 12.2 | opgaven12 |
19 mei | oud tentamen oefenen | tentamen van juli 2016 | -- |
De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Zie voor de gewenste codering van de bomen het bestand "readmelinux.txt".
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. 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.
Alle opdrachten zijn nagekeken, en ook de herkansingen. U vindt de cijfers in het overzicht van alle cijfers.
Meer informatie, zoals over het schrijven van het verslag in LaTeX, is hier te vinden.
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.
Er zijn twee tentamens geweest:
Eerste tentamen: dinsdag 6 juni 2017, 14.00-17.00 uur.
Hertentamen: maandag 10 juli 2017, 14.00-17.00.
in zalen 407/409 en 312 in het Snellius.
Beide tentamens zijn nagekeken.
U vindt de resulterende tentamencijfers, inclusief eindcijfers,
in het
overzicht van alle cijfers.
Je kunt je tentamen inzien bij de docent, op kamer 140 van het Snellius.
Beide tentamens zijn nog terug te vinden in het lijstje met oude tentamens
onderaan deze pagina. Van het eerste tentamen staat er ook een uitwerking.
Vragen en/of opmerkingen kunt u sturen naar: Rudy van Vliet; rvvliet(at)liacs(dot)nl Laatste wijziging: 12 september 2017 - http://www.liacs.leidenuniv.nl/~vlietrvan1/algoritmiek/voorjaar2017/leiden/ |