Toegangseisen
Aanbevolen voorkennis: Algoritmiek
Beschrijving
Algoritmen en datastructuren vormen een onafscheidbaar stel. Enerzijds zijn goed ontworpen datastructuren essentieel om efficiënt algoritmische problemen op te lossen. Zo gebruiken we Adjacency lists en Priority queues om het algoritme van Dijkstra voor kortste paden op te lossen. Anderzijds worden bij niet-triviale datastructuren slimme algoritmes gebruikt om de structuur aan te passen wanneer er gegevens worden toegevoegd of verwijderd.
Bij het gebruik en implementatie maken we onderscheid tussen abstracte datastructuren en de concrete implementaties daarvan. De basis structuur Stack (of Stapel) met operaties Pop en Push kan bijvoorbeeld geïmplementeerd worden ofwel met behulp van een array ofwel als gelinkte lijst.
In dit college zullen we de standaard datastructuren zoals stapels (stacks), rijen (queues), lijsten (lists), binaire en multiway bomen, priority queues, en grafen de revue laten passeren. Elk van deze gegevensstructuren kun je karakteriseren vanwege hun (interne) structuur en hun methoden (tests op, en wijzigen van, de opgeslagen gegevens). We schetsen mogelijke implementaties van de abstracte structuren, en bekijken de consequenties voor de efficiëntie van de operaties. Ook bekijken we enkele algoritmes die slim gebruik maken van een aantal van deze structuren.
Leerdoelen
Na afloop van dit vak kan de ijverige student:
onderscheid maken tussen abstracte datastructuren en hun implementaties
diverse basisstructuren (lineaire lijsten, bomen) beschrijven en onderscheiden (structureel, ordening van sleutels)
recursieve boomwandelingen definiëren (voor pre-orde, in-orde en post-orde), deze kunnen uitvoeren op simpele voorbeelden, en kunnen aangeven welk toepassing elk van de drie ordeningen heeft
de behandelde implementaties (zoals binaire zoekboom, binaire heap, B-boom, ...) omschrijven, de werking van deze implementaties begrijpen en uitleggen, toepassen en illustreren aan de hand van kleine voorbeelden, en de complexiteit ervan bepalen en vergelijken
daar waar verschillende implementaties van dezelfde ADT bestaan de relatieve voor- en nadelen aangeven
de behandelde algoritmen (op grafen, datacompressie, matching) omschrijven, uitleggen waar deze toepasbaar zijn, toepassen en illustreren aan de hand van kleine voorbeelden, en de complexiteit ervan bepalen
Rooster
In MyTimetable kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je je via MyStudyMap hebt ingeschreven, worden automatisch in je rooster getoond.
Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging. Je kunt notificaties aanzetten bij Instellingen, nadat je bent ingelogd.
Vragen? Bekijk de video, lees de instructie of neem contact op met de ISSC helpdesk.
Let op: Joint Degree studenten Leiden/Delft dienen de informatie uit de Leidse en Delftse MyTimetables samen te voegen om een volledig rooster te zien. Deze video legt uit hoe dat werkt.
Onderwijsvorm
Per week 2 uur hoorcollege en daarnaast 2 uur werkcollege.
Toetsing en weging
Schriftelijk tentamen (100%)
3 programmeeropgaven (pass/fail)
Het cijfer voor het schriftelijk tentamen dient minstens 5,5 te bedragen om het vak te halen. De programmeeropgaven moeten alle voldoende worden afgesloten.
Bij een goed resultaat voor de opgaven kan in totaal een bonus van 1 punt worden verdiend op het eindcijfer, mits het cijfer voor het tentamen minstens 5,5 bedraagt.
Het tentamen kent een schriftelijke herkansing. Voor iedere programmeeropgave wordt ook een herkansingsmogelijkheid aangeboden. Hiermee kan geen bonus meer worden verdiend voor het eindcijfer.
Literatuurlijst
Er is een uitgewerkt diktaat beschikbaar met de collegestof. Die stof is hoofdzakelijk gabaseerd op het boek van Adam Drozdek, Data Structures and Algorithms in C++, 4th/International Edition. Dit boek is niet verplicht, maar aanbevolen voor wie het dictaat te compact is.
Inschrijven
Als student ben je zelf verantwoordelijk voor het tijdig inschrijven via MyStudyMap.
In deze korte video zie je stap voor stap hoe je je kunt inschrijven voor cursussen in MyStudyMap.
Uitgebreide informatie over de werking van MyStudyMap vind je hier.
Er zijn twee inschrijfperiodes per jaar:
de inschrijving voor het najaar opent in juli
de inschrijving voor het voorjaar opent in december
Zie deze pagina voor meer informatie over deadlines en inschrijven voor vakken en tentamens.
Let op:
Het is verplicht om je in te schrijven voor alle activiteiten die je gaat volgen van een vak.
Je inschrijving is pas voltooid wanneer je je cursusplanning indient in het tabblad ‘Klaar voor inschrijving’ door op ‘indienen’ te klikken.
Niet ingeschreven zijn voor een (her)tentamen betekent dat je niet mag deelnemen aan het (her)tentamen.
Contact
Onderwijscoördinator LIACS bachelors
Opmerkingen
Software
Vanaf collegejaar 2024/2025 werkt de faculteit Wiskunde en Natuurwetenschappen met het software distributieplatform Academic Software. Via het platform kun je toegang krijgen tot de software die je nodig hebt voor bepaalde vakken in je studie. Voor sommige software moet je laptop aan bepaalde systeemeisen voldoen. Dit staat aangegeven bij de software. Belangrijk is dat je de software installeert voor de start van het vak. Meer informatie over het laptopprofiel vind je op de studentenwebsite.