Complexiteit 2023/2024

Het tweedejaarsvak Complexiteit (officieel: Complexity) wordt in het voorjaar van 2024 verzorgd door Jeannette de Graaf en Luc Edixhoven. De assistentie, waaronder de begeleiding van de werkcolleges, wordt verleend door Pjotr Beerens, Perri van den Berg, Rachel de Jong en Hessel Sieburgh. Het vak 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. Overigens vind je in de e-studiegids bij de algemene beschrijving van elk vak meer informatie over het inschrijven voor vakken.

De hoorcolleges vinden plaats op maandagen van 11.00 uur tot 12.45 uur in de De Sitterzaal of de Havingazaal. Het bij de colleges behorende werkcollege is op woensdagen van 11.00 uur tot 12.45 uur, in Snelliuszalen 174, 402 en 407--409. Op 25 maart (hertentamenweek), 1 april (Pasen) en 20 mei (Pinksteren) is er geen college; verder is er vanwege de hertentamenweek geen werkcollege op 27 maart. 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 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 2024 is inmiddels beschikbaar. Deze verschilt niet veel van de versie van 2023; alleen hoofdstuk 2 (wiskundige achtergrond) is wat uitgebreid. 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

Het tentamen Complexiteit is nagekeken: tentamencijfers en gemiddelde huiswerkcijfers staan op Brightspace. Er is bij de becijfering rekening gehouden met het feit dat het tentamen nogal veel tijd kostte om te maken. De eindcijfers moeten nog berekend worden, maar zullen in de loop van de week naar de studentenadministratie worden gestuurd om in usis te registreren. Het tentamen zelf staat inmiddels op deze website, nu (6 juli) nog even zonder uitwerking.

Het tentamen Complexiteit (20 juni, 9 - 12 uur) vindt plaats in het Snellius, zalen 174, 407-409 en 412.

Een uitwerking van de vierde huiswerkopdracht staat inmiddels verderop op deze pagina.

Een behoorlijk uitgebreide uitwerking van de opgaven van werkcollege 12 is nu ook beschikbaar.

Met een beetje vertraging, maar vandaag (16 mei) is ook een uitwerking van opgaven van werkcollege 11 op de website geplaatst. Die van werkcollege 12 volgt als het goed is morgen.

Zie het schema op deze webpagina voor de invulling van college en werkcollege in de week van 13 mei en de week van 20 mei. Op 27 mei is er geen college meer.

De vierde (en tevens laatste) huiswerkopgave is beschikbaar. Zie verderop op deze pagina.

De feedback bij huiswerkopgave 2 op Brightspace is gepubliceerd. Vragen daarover kun je stellen aan de docenten. De uitwerking van het huiswerk wordt morgen (1 mei) op deze website geplaatst.

De derde huiswerkopgave is beschikbaar. Zie verderop op deze pagina.

Opgave 2 uit het tentamen van juni 2019 (zie werkcollege week 9) is nuttig ter illustratie bij het college(gedeelte) over matrixvermenigvuldigen. Hier wordt de "gewone" methode recursief geformuleerd, leidend tot een recurrente betrekking voor het aantal getalsvermenigvuldigingen, net als we voor het algoritme van Strassen hebben afgeleid.

Er staat nu ook een uitwerking van de eerste huiswerkopgave online. Zie verderop op deze pagina.

Op woensdag 3 april is er college in plaats van werkcollege in zaal 407/409 van het Snellius. Het eerste uur maken we het onderwerp sorteren middels arrayvergelijkingen af, het tweede uur maak ik (een deel van) opgave 1 en 2 van het hertentamen van 2023 voor: beslissingsboom en recurrente betrekking.

De antwoorden van de werkcollege-opgave zijn inmiddels bijgewerkt tot en met werkcollege 7.

De tweede huiswerkopgave is beschikbaar. Zie verderop op deze pagina. De achterliggende stof hebben we al behandeld; je kunt de opgave dus in principe nu al maken.

Antwoorden bij werkcollege 4 staan inmiddels ook online.

Er is een uitwerking van opgave 19 toegevoegd in de pdf met antwoorden bij werkcollege 3.

Huiswerkopgave 1: In tegenstelling tot wat vandaag op het college werd aangegeven, en in tegenstelling tot de mededeling die eerder vanavond is gedaan via BS, is er geen foutje geslopen in de opgegeven grenzen waar k en n aan moeten voldoen. Er moet dus gelden (en dat gebruik je bijvoorbeeld bij onderdeel a.) dat 2 < k <= n; precies zoals in de opgave stond (en staat). (Dit heeft overigens tot gevolg dat dan ook n > 2, maar dat doet er verder niet toe.) Vanwege de onbedoelde verwarring zal de deadline voor deze huiswerkopgave met een dag verlengd worden tot dinsdag 5 maart om 23.59 uur.

Op de laatste twee sheets van college 4 staat een voorbeeld (algoritme uit opgave 18 uit het dictaat) van hoe je alle worst case gevallen gestructureerd kunt afleiden uit het algoritme. Op college is dit heel kort besproken, in de sheets is dit iets verder uitgewerkt.

In onderdeel g. van de eerste huiswerkopgave is een kleine slordigheid geslopen. Dat het slechtste geval uit d. niet haalbaar is voor het aangepaste algoritme, geldt alleen als k < n. Voor k=n is het wel haalbaar. Het zal je niet worden aangerekend als je het geval k=n niet hebt opgemerkt; ik was dat zelf immers ook vergeten.

Er staan nu ook antwoorden van opgaven uit werkcollege 3 online. Een uitwerking van opgave 19 komt nog.

Naar aanleiding van een vraag van een student: de deadline voor het inleveren van de eerste huiswerkopdracht is maandag 4 maart om 23.59 uur. Je hoef hem dus niet voor het begin van het college al ingeleverd te hebben.

Er staan (eindelijk) ook antwoorden van opgaven uit werkcollege 2 online.

De eerste huiswerkopgave is beschikbaar. Zie verderop op deze pagina. Lees de opgave eerst goed door.

Antwoorden op de opgaven van de werkcolleges zullen te vinden zijn in het schema waarin ook de sheets van de colleges staan. Die van het eerste werkcollege zijn inmiddels beschikbaar. Bekijk ook de uitgebreidere uitwerkingen van sommige opgaven onder het kopje Werkcollege-opgaven op deze website.

Het eerste werkcollege is op woensdag 7 februari 2024 van 11.00 tot 12.45 uur in de het Snellius (174, 402, 407-409). Verspreid je een beetje over de verschillende zalen, zodat niet iedereen in dezelfde zaal zit.

Het eerste college is inmiddels geweest en de sheets zijn (waar nodig) aangepast. Volgende week, 12 februari, is het college in zaal 2.26 van het Huygens, en niet in de De Sitterzaal.

Het eerste college is op maandag 5 februari 2024 van 11.00 tot 12.45 uur in de De Sitterzaal.

Programma

Hieronder zal het programma voor het hoorcollege/werkcollege van het voorjaar 2024 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	5 februari	De Sitterzaal	Inleiding	1; 2.1 t/m 2.3	college 1	1,2,3abcd,4,6 antwoorden
2	12 februari	Huygens, zaal 2.26	Restant 5/2; Zoeken	1.6; 4	college 2	(6,) 3e, 8, 10, 17, 20 antwoorden
3	19 februari	Havingazaal	Beslissingsbomen, selectieprobleem	3, 6.1 t/m 6.4	college 3	19, 20, 22, 27, 23abc, 24 antwoorden
4	26 februari	Havingazaal	Adversary argument, selectie is O(n)	5, 6.5 t/m 6.6	college 4	18, 29abc, 31, 32, 33 antwoorden
5	4 maart	Havingazaal	Insertion sort, recurrente betrekkingen	7.1, 1.7, 2.4	college 5	7, extra, 14aeg, 15, 1abc tentamen 5/6/23 (als tijd) antwoorden
6	11 maart	Havingazaal	Recurrente betrekkingen, Mergesort, Ondergrens sorteren	2.4, 7.2, 7.3	college 6	15, 16, 34, 36, 1abc tentamen 5/6/23, 35 antwoorden
7	18 maart	Havingazaal	Quicksort, Shellsort	7.4, 7.5	college 7	39 (geen Heapsort), 40, 41,42, 43 antwoorden
-	25 maart	---	---	---	---	---
8	3 april	Snellius zaal 407/409	restant Shellsort, optimaal sorteren	7.5, 7.6	college 8	college i.p.v. werkcollege
9	8 april	De Sitterzaal	O(n)-sorteren, polynoomevaluatie, matrixvermenigvuldiging	7.7, 8	college 9	(43,) 44, 47, 48ac, 45, 46b, 2 tentamen 4/6/19 antwoorden
10	15 april	De Sitterzaal	Graafproblemen, inleiding complexiteitstheorie	9, 10.1, 10.3	college 10	49, 52a, 55, 58ac, 2 tentamen 4/6/19 antwoorden
11	22 april	De Sitterzaal	Voorbeeldproblemen, de klasse NP	10.2, 10.4	college 11	53, 54, 59abc, 61, 58bd antwoorden
12	29 april	De Sitterzaal	Reducties, NPC	10.5	college 12	62, 63, 65, 64 antwoorden
13	6 mei	De Sitterzaal	Afsluiting NPC	---	college 13	66, 67, 68 antwoorden
14	13 mei	De Sitterzaal	Herhaling	---	gastcollege	Gastcollege: complexiteit en spellen
15	20 mei	Geen college	Pinksteren	---	---	Oefententamen

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 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 4 maart 2024 via Brightspace. Let op: de deadline is verschoven naar dinsdag 5 maart 2024, 23.59 uur.
Maak het huiswerk in LaTeX en lever het als pdf in.
Een uitgebreide uitwerking is hier te vinden.

Tweede huiswerkopgave
Uiterlijk inleveren: woensdag 3 april 2024 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, huiswerkdrie2024-template.tex.
Uiterlijk inleveren: maandag 29 april (23.59 uur). Net als voorheen: maak het huiswerk in LaTex en lever het als pdf in via Brightspace.
Lees de opgave en het bijgeleverde programma eerst goed door!

Vierde huiswerkopgave
Uiterlijk inleveren: vrijdag 17 mei (23.59 uur). Zoals gebruikelijk: maak het huiswerk in LaTex en lever het als pdf in via Brightspace.
Een uitgebreide uitwerking is hier te vinden.

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 staat hieronder nog een aantal oude (uit 2018/2019) uitwerkingen. 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 2024)

uitwerking opgave 5ab (versie 2024)

uitwerking opgave 6 (versie 2024)

uitwerking opgave 16 (versie 2024)

uitwerking opgave 20 (versie 2024)

uitwerking opgave 21 (versie 2024)

uitwerking opgaven 23, 24 en 25 (versie 2024)

uitwerking opgave 26 (versie 2024)

uitwerking opgaven 27a en 31 (versie 2024)

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

uitwerking opgave 43 (versie 2024)

uitwerking opgaven 47 en 48 (versie 2024)

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 donderdag 20 juni 2024 van 09:00 tot 12:00 uur.
Op maandag 15 juli 2024 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.