Complexiteit 2024/2025

Het tweedejaarsvak Complexiteit (officieel: Complexity) wordt in het voorjaar van 2025 verzorgd door Jeannette de Graaf en Mark van den Bergh. De assistentie, waaronder de begeleiding van de werkcolleges, wordt verleend door Pjotr Beerens, Perri van den Berg, Angela van Delft en Niels Heslenfeld. Complexiteit is verplicht voor alle studenten Informatica en levert 6 EC op. Het vak bestaat uit hoorcolleges, werkcolleges, huiswerkopgaven en een afsluitend tentamen.
Studenten die deel gaan nemen aan Complexiteit wordt verzocht zich voor alle onderdelen van het vak in te schrijven via MyStudyMap. Schrijf je ook meteen in voor het tentamen! Overigens vind je in de e-studiegids bij de algemene beschrijving van elk vak meer informatie over het inschrijven voor vakken en tentamens. Ook meer over inschrijven voor vakken en tentamens op de Brightspacepagina van de bachelor Informatica onder de tegel Studiezaken.
Let op: het vak Complexiteit in de huidige vorm wordt dit jaar voor het laatst gegeven. Het is dus aan te raden dat je dit vak actief volgt en het huiswerk serieus maakt, zodat je het tentamen straks haalt.

De hoorcolleges vinden plaats op vrijdagen van 11.00 uur tot 12.45 uur in het Gorlaeusgebouw, zaal BW.0.40. Het bij de colleges behorende werkcollege is aansluitend op vrijdagmiddagen van 13.15 uur tot 15.00 uur in zalen BW.0.29 en BW.0.30 van het Gorlaeusgebouw. Op 28 maart (hertentamenweek, week 13) is er geen college en geen werkcollege. Hetzelfde geldt voor 18 april (Goede Vrijdag, week 16). Zie ook het globale rooster of kijk in MyTimeTable.

Informatievoorziening

Alle relevante informatie voor het vak komt in principe op deze website te staan. Brightspace wordt hoofdzakelijk gebruikt voor het inleveren van opdrachten en het geven van cijfers, en voor (extra) belangrijke mededelingen. Ook kun je daar, via het discussieforum vragen stellen. Vragen stellen in persoon of per mail worden ook beantwoord (en misschien zelfs sneller).

Materiaal

Er is een (losbladig) dictaat dat min of meer de inhoud van de gebruikte sheets bevat alsmede enige verbindende tekst, en bovendien een verzameling opgaven bij het hoorcollege. Zorg dat je de opgaven bij je hebt tijdens werkcolleges! Het college zelf bestaat overigens uit meer dan alleen de inhoud van het dictaat of de sheets! De versie van 2025 is reeds beschikbaar. Deze verschilt niet essentieel van de versie van 2024. Hoofdstuk 2 (wiskundige achtergrond) wordt niet expliciet op college behandeld. Het is de bedoeling dat je dat hoofdstuk zelf bestudeert. Mochten er in de loop van het semester extra veranderingen/aanvullingen komen op dit dictaat, dan zullen die veranderingen op deze website gemeld worden. Overigens zullen eveneens de gebruikte sheets via deze website te raadplegen zijn. Zie hieronder, in het collegeschema.

Inhoud van het vak

Heel globaal: (1) analyse van algoritmen, en (2) NP-volledigheid. Een greep uit de te behandelen onderwerpen: tijdcomplexiteit (worst/average/best case) van diverse algoritmen (niet recursief en recursief), enige wiskunde (O-notatie, recurrente betrekkingen), complexiteit van problemen, optimaliteit, beslissingsbomen, selectie/zoeken/sorteren, polynoomevaluatie, NP-volledige problemen (waaronder enkele bekende graafproblemen zoals het handelsreizigersprobleem) en reducties.

Nieuws / updates

(23/04) Er is nu een uitwerking van de tweede huiswerkopgave beschikbaar.

(14/04) In de slides van college 9 is bij preprocessing van polynomen een korte toelichting toegevoegd op de opmerking dat het polynoom zonder beperking der algemeenheid monisch van graad een tweemacht - 1 is.

(04/04) Volgende week, dus op 11 april, is het college eenmalig in zaal BM.1.33

(04/04) De uitwerking van de opgaven van werkcollege 7, die ik eerste vergeten was op de website te zetten, is daar zojuist alsnog neergezet.

(03/04) De cijfers en feedback van de eerste huiswerkopgave zijn inmiddels gepubliceerd op de Brightspacepagina van Complexiteit. Er is over het algemeen streng nagekeken, maar laat je niet afschrikken door een onvoldoende. Lees de feedback door en concentreer je op de tweede huiswerkopgave.

(23/03) De tweede huiswerkopdracht is zojuist online gezet. De deadline is 7 maart. Het is verstandig om, ter voorbereideing op het tentamen, ook deze huiswerkopdracht serieus te maken. Verder kun je hieronder inmiddels een vrij uitgebreide uitwerking van de eerste huiswerkopdracht vinden.

(22/03) Het eerstvolgende college is op vrijdag 4 april. We zullen dan nog even terugkomen op Shellsort en daarna onder andere bekijken in hoeverre we de bewezen (precieze) ondergrens voor sorteren kunnen halen. 's Middags is er geen werkcollege, maar je kunt dan wel in de gebruikelijke zalen zelf werken aan de tweede huiswerkopdracht. Er is dan tevens gelegenheid om vragen te stellen aan de docent.

De eerste huiswerkopdracht staat inmiddels online. De deadline is maandag 10 maart; dit lijkt haalbaar. Het is de bedoeling dat je het huiswerk individueel maakt en inlevert, maar vragen stellen aan docent/studentassistent/medestudent mag natuurlijk. Overschrijven mag niet, daar heb je niets aan. Het huiswerk is immers bedoeld als voorbereiding op het tentamen.

De uitwerking van opgave 20b op deze website is verbeterd nadat een wakkere student vrijdag had gezien dat er meer worst case gevallen waren dan alleen die in de oorspronkelijke uitwerking stonden. Het gaat om het aantal keer dat de test i is kleiner dan j wordt uitgevoerd in de worst case. Als dat zo vaak mogelijk moet gebeuren (worst case) moet elke ronde of alleen i, of alleen j worden opgehoogd, behalve eventueel als j=i+1. Hulde en dank aan de wakkere student.

Gisteren (14/2) zijn we niet erg opgeschoten met de werkgroep-opgaven. Maak dus zelf thuis opgave 17 (die is niet moeilijk) en kijk ook even heel goed naar opgave 20. Dat is een leuke, leerzame opgave. We zullen daar volgende week bij het werkcollege mee beginnen. Overigens zullen we volgende week en de week daarna nog een paar opgaven maken waarbij basisoperatie / best case / worst case bepaald moeten worden. Deze opgaven sluiten heel goed aan bij zowel de eerste huiswerkopgave als het tentamen. Kom dus vooral naar het werkcollege, doe daar actief mee en vraag hulp als je er niet uitkomt. Vragen of de assistent (een deel van) de opgave klassikaal behandelt mag uiteraard ook.

De slides van het eerste college zijn bijgewerkt en antwoorden op de opgaven van het eerste werkcollege zijn nu ook beschikbaar.

Vanaf komende vrijdag (14 februari) zal het college, zoals het hoort, om 11 uur beginnen, en niet pas om 10 over 11 zoals het eerste college. De docent was even --heel sukkelig-- in de war over de begintijd. Excuses.

Het eerste werkcollege is aansluitend op het college in zalen BW.0.29 en BW.0.30 van het Gorlaeusgebouw. Kies zelf een zaal, maar zorg wel dat er ongeveer evenveel studenten in elke zaal zitten.

Het eerste college is op vrijdag 7 februari 2025 van 11.00 tot 12.45 uur in zaal BW.0.40 van het Gorlaeusgebouw.

Programma

Hieronder zal het programma voor het hoorcollege/werkcollege van het voorjaar 2025 bijgehouden worden. Voor elke week zal daarin vermeld staan welke onderwerpen aan de orde zijn gekomen met de bijbehorende stukken uit het dictaat, de gebruikte sheets en de opgaven die bij het werkcollege behandeld zijn. In principe worden de sheets de ochtend of de dag voor het college op deze site gezet; direct na het college wordt dit zonodig aangepast naar de definitieve versie. Na het werkcollege zullen in onderstaand schema tevens antwoorden van de gemaakte opgaven worden geplaatst. Van sommige opgaven is een uitgebreidere uitwerking te vinden verderop op deze pagina, onder het kopje Werkcollege-opgaven.

#	Datum	Zaal	Onderwerp	Dictaat	Sheets	Werkcollege: opgaven
1	7 februari	BW.0.40	Inleiding	1.1 t/m 1.5, 2 (zelf)	college 1	1, 2, 3abcd, 4, 6 antwoorden
2	14 februari	BW.0.40	Restant 7/2; Zoeken	1.6, 4	college 2	3e, 8, 10, 17, 20 antwoorden
3	21 februari	BW.0.40	Beslissingsbomen, selectieprobleem	3, 6.1 t/m 6.4	college 3	19, 20, 22, 27, 23abc, 24 antwoorden
4	28 februari	BW.0.40	Adversary argument, selectie is O(n) (begin)	5, 6.5	college 4	18, 29abc, 31, 32, 33 antwoorden
5	7 maart	BW.0.40	Selectie is O(n), insertion sort, recurrente betrekkingen	6.6, 7.1, 1.7, 2.4	college 5	7, extra, opgave 2c tentamen juni 2024, 14aeg antwoorden
6	14 maart	BW.0.40	Recurrente betrekkingen, Mergesort, Ondergrens sorteren	2.4, 7.2, 7.3	college 6	15, 16, opgave 2 tentamen juni 2024, 34, 35, 36 antwoorden
7	21 maart	BW.0.40	Quicksort, Shellsort	7.4, 7.5	college 7	39 (geen Heapsort), 40, 41, 42, 43 antwoorden
-	28 maart	---	---	---	---	---
8	4 april	BW.0.40	restant Shellsort, optimaal sorteren, O(n)-sorteren	7.5, 7.6, 7.7	college 8	geen werkcollege
9	11 april	BM.1.33	Polynoomevaluatie, matrixvermenigvuldiging	8	college 9	43, 44, 47, 48ac, 45, 46b, 2 tentamen 4/6/19 antwoorden
-	18 april	---	Goede Vrijdag	---	geen college	geen werkcollege
10	25 april	BW.0.40	Complexiteitsklassen	9, 10.1, 10.3	college 10	49, 55, 61, 58ac, 51

Huiswerk

Gedurende het semester zijn er (maximaal) vier huiswerkopdrachten om in te leveren. Deze hebben als doel om te zorgen voor een beter begrip van de stof, en tellen mee als bonus voor het eindcijfer voor dit vak. De belangrijkste functie van het huiswerk is echter dat het een goede voorbereiding op het tentamen is: heb je de opgaven serieus gemaakt en begrijp je de stof, dan zou je normaal gesproken het tentamen moeten kunnen halen. Huiswerk gemaakt in voorgaande jaren telt niet mee voor het huiswerkcijfer van het huidige studiejaar.

De huiswerkopdrachten dienen individueel te worden gemaakt (in LaTeX!), en vervolgens ingeleverd op Brightspace. Uiteraard mag je bij het maken van de opgaven met elkaar de problemen en de leerstof bespreken, maar kopieren, overschrijven en dergelijke zijn niet toegestaan. Dus, geef bij het bespreken van de opgaven elkaar indien nodig een duwtje in de goede richting, tips en suggesties, maar geen panklare oplossing. Daar wordt niemand beter van.

Met de huiswerkopdrachten is maximaal 1 bonuspunt te verdienen. Om de bonus mee te kunnen laten tellen moet het cijfer voor het tentamen (op 1 decimaal nauwkeurig) ten minste een 5,0 zijn. Het eindcijfer voor Complexiteit wordt dan als volgt bepaald. Indien het tentamencijfer >= 5,0: eindcijfer = (gemiddeld huiswerkcijfer)/10 + tentamencijfer. Als het tentamencijfer lager dan 5,0 is, is het eindcijfer gelijk aan het tentamencijfer. Het eindcijfer wordt zoals gebruikelijk afgerond op een geheel- of halftallig cijfer tussen 1 en 10. Niet-ingeleverde huiswerkopgaven tellen als 0.

Eerste huiswerkopgave
Uiterlijk inleveren: maandag 10 maart 2025 uiterlijk 23.59 uur via Brightspace.
Maak het huiswerk in LaTeX en lever het als pdf in.
Een uitgebreide uitwerking is hier te vinden.

Tweede huiswerkopgave
Uiterlijk inleveren: maandag 7 april 2025 via Brightspace.
Maak het huiswerk in LaTeX en lever het als pdf in.
Een uitgebreide uitwerking is hier te vinden.

Derde huiswerkopgave
Bijgevoegd hierbij zijn verder een C++-programma om de experimenten mee uit te voeren, een makefile om de code mee te compileren, en (voor degenen die daar baat bij hebben) een LaTeX-template voor het te schrijven verslagje: shellsort.cc, makefile, huiswerkdrie2025-template.tex.
Uiterlijk inleveren: maandag 28 april (23.59 uur). Net als voorheen: maak het huiswerk in LaTex en lever het als pdf in via Brightspace.
Voor deze opgave moet je ook je code inleveren. Deze wordt niet nagekeken, maar dan hebben we een implementatie van je eigen rijtje (bij opgave b) en kunnen we dat uitvoeren zonder het zelf te hoeven implementeren. Je kan bij het inleveren van de opdracht op Brightspace meerdere bestanden uploaden, of het geheel comprimeren en het resulterende bestand uploaden (.zip, .tar.gz, ....).
Lees de opgave en het bijgeleverde programma eerst goed door!

Werkcollege-opgaven

In het dictaat staan opgaven, die grotendeels op het werkcollege (of college) behandeld zullen worden. Soms is er van een enkele opgave een uitgebreidere uitwerking beschikbaar. Deze uitwerkingen zijn hieronder te vinden ter referentie. Voor alle andere uitwerkingen van opgaven: bezoek het werkcollege en schrijf ze zelf!

Op dit moment staan hieronder nog de uitwerkingen van 2024. In de loop van dit semester zullen ---indien nodig--- die uitwerkingen worden bijgewerkt. Wanneer dit het geval is zal dit hieronder duidelijk worden aangegeven, zodat je weet dat het om de definitieve versie gaat. Tevens zal er hier en daar wellicht een extra uitwerking bijkomen.

uitwerking opgave 3 (versie 2025)

uitwerking opgave 5ab (versie 2025)

uitwerking opgave 6 (versie 2025)

uitwerking opgave 16 (versie 2025)

uitwerking opgave 20 (versie 2025)

uitwerking opgave 21 (versie 2024)

uitwerking opgaven 23, 24 en 25 (versie 2025)

uitwerking opgave 26 (versie 2025)

uitwerking opgaven 27a en 31 (versie 2025)

uitwerking opgave 36 (best case Mergesort) (versie 2025)

uitwerking opgave 43 (versie 2025)

uitwerking opgaven 47 en 48 (versie 2025)

uitwerking opgave 53 (versie 2024)

uitwerking opgave 59a (versie 2024)

uitwerking opgave 62 (versie 2024)

uitwerking opgave 65 (versie 2024)

uitwerking opgave 67 (versie 2024)

HC1 < HC2 (extra reductie; versie 2024)

Tentamen

Het tentamen Complexiteit bevat in elk geval zowel praktische vragen (zoals de werkcollege-opgaven en het huiswerk) als meer theoretische (college). Ook kleine bewijsjes en eenvoudige recurrente betrekkingen zijn mogelijk. Het tentamen is op woensdag 28 mei 2025 van 09:00 tot 12:00 uur.
Op dinsdag 1 juli 2025 is de herkansing (van 09:00 tot 12:00 uur).
Er zijn enige oude tentamens Complexiteit beschikbaar om mee te oefenen. Deze zijn hieronder te vinden. Van de tentamens van juni zijn zeer uitgebreide (bedoeld om de antwoorden nog eens uitvoerig uit te leggen) uitwerkingen te vinden. LET OP: in een paar oude tentamens staan nog opgaven over Turingmachines (DTMs). Deze behoren niet meer tot de stof van dit vak. Je kan deze opgaven dus overslaan.