USCKI Incognito Logo link

Docent: Hans Bodlaender

Voorkennis

Imperatief en Objectgeoriënteerd Programmeren is een vereiste. En dat is nog wel het minste. Ik ben ervan overtuigd dat dit vak niet goed te doen is als je ook nog geen Datastructuren en Algoritmen voor CKI hebt gehad. Datastructuren komen (naast algoritmen) namelijk ook veel voorbij. Algoritmiek gaat veel dieper in op algoritmen, maar het is er nauw mee verwant.

Inhoud

Bij Algoritmiek leer je volledige en efficiënte algoritmen te schrijven. Een les begint vaak met een probleemstelling, zoals hoe je het op-x-na-hoogste getal uit een lijstje vindt, of welke gewogen kanten van een graaf gebruikt moeten worden om alle knopen met elkaar te verbinden met zo licht mogelijke kanten (Minimum Spanning Tree). Het gaat over technieken die je zou kunnen gebruiken om bepaalde specifieke problemen op te lossen en hoopt je daarmee de algemenere methoden aan te leren om andere problemen te kunnen oplossen.
Ook wordt er behandeld hoe je de (tijds)complexiteit van een algoritme kan bepalen en complexiteit is een thema door het hele vak heen. Het raakt tevens wat onderwerpen aan die met algoritmiek verwant zijn, zoals NP-volledigheid, cryptografie en benaderingsalgoritmen.

Vorm

Het vak wordt in twee delen opgedeeld, en voor elk van de delen is een tentamen. Het eerste deel gaat over algoritmen in het algemeen: complexiteit berekenen, dynamisch programmeren, divide-and-conquer, greedy algoritmen, en behandelt daarmee enkele eenvoudige algoritmen die met nummers en lijstjes rekenen. Het tweede deel gaat geheel over grafen, maar heeft nog een extra deel er aan vast over enkele losse onderwerpen zoals amortisering, NP-volledigheid en cryptografie. Het tweede tentamen gaat ervanuit dat je het eerste deel impliciet kent.
Er zijn zes practicumopgaven die tijdens het blok moeten worden ingeleverd. Je wordt geacht om deze thuis te maken, en er wordt redelijk veel tijd voor gegeven (1 week voor de eenvoudige opgaven, 2 voor de moeilijkere aan het eind). Je moet er vier van gemaakt hebben om het vak te halen. De laatste twee geven 0,5 bonuspunt op je eindcijfer per stuk. De practica zijn in C#, dus hiervoor is .NET-ontwikkelomgeving nodig, zoals Visual Studio of MonoDevelop (voor OSX/Linux) om ermee te kunnen werken. Als je alleen kennis van Java hebt, hoef je niet bang te zijn, want C# gebruikt vrijwel identieke syntax als Java.
Verder zijn er nog twee werkcolleges per week (voor of na elk hoorcollege) waarin opgaven uit het boek worden opgegeven. Je mag echter wel gewoon aan het practicum werken en hier vragen over stellen

De twee toetsen tellen even zwaar. Als je alle inleveropgaven gemaakt hebt krijg je dus 1 punt extra bovenop je toetsgemiddelde. Je eindcijfer (na eventuele ophoging) moet minstens een 5.5 zijn.

Werklast

Het is moeilijke stof. De tentamens zijn niet makkelijk. Het is belangrijk dat je elke les bijwoont en wat goede tijd besteedt om te leren voor je tentamens. Alles in het boek lezen is misschien niet nodig. Als je de werkgroepopgaven goed bijhoudt (en dus echt allemaal probeert te maken) is zijn de tentamens echter een stuk beter te doen. Soms wordt er zelfs een huiswerkvraag (subtiel) in het tentamen verwerkt.
Het eerste practicum was een oefening om met het DomJudge systeem (een automatische nakijker voor C# code) te leren omgaan. De andere vijf zijn aardig veel werk, maar het is wel leuk om te doen en met Wikipedia aan de hand en de aantekeningen van de hoorcolleges ben je er zo doorheen.

Literatuur

Introduction to Algorithms is een verplicht boek voor het vak. Ze gaan er kris-kras doorheen zoals altijd, maar de stof die behandeld wordt is dezelfde als de stof in dit beroemde boek.
In de werkcolleges worden de opgaven uit het boek gemaakt.
Het is dus ten zeerste aangeraden om dit (dure) boek dus echt te kopen/huren/lenen. De derde editie is de goede, maar de tweede werkt net zo goed.

Presentatie

Hans Bodlaender is een droge informaticus. Voor het college begint staat hij met zijn horloge te wachten tot het op de seconde precies 9 uur is om te beginnen en soms zijn de voorbeelden die hij gebruikt saai en langdradig. Echter is het ontzettend nuttig om de colleges te volgen, omdat de stof die uitgelegd wordt vaak direct terugkomt in de practica. Op de slides staan vaak alleen wiskundige beschrijvingen van algoritmes die zonder uitleg moeilijk te begrijpen kunnen zijn.

Ik vond dit een cool vak, welke vakken nog meer?

Keywords


Naar de Studiedatabase
Terug naar de Studiegids