CA 2011-2012

Email docenten: Bart Demoen en Jon Sneyers

CA wordt gedoceerd in het tweede semester. We zullen een deel van het boek Computational Complexity: A Modern Approach, auteurs Sanjeev Arora and Boaz Barak zien (+ iets uit het boek Traub en Werschulz). Zie de redelijk volledige draft van het eerste boek. Druk die draft niet af: we bespreken dat in de eerste les.

De planning van de toegekende projecten

Willem Van Onsem en Tom Desair: oblivious TM - 18 april PRESENTATIE en VERSLAG
Jonas: Primes is in P - 30 april PRESENTATIE en VERSLAG
Brian: 3-stacks - 2 mei
Nathan en Jo: Manuel Blum en aximatische complexiteitstheorie - 2 mei PRESENTATIE en VERSLAG
Sander en Ingmar: Fagin's theorem - 14 mei PRESENTATIE en VERSLAG
Job en Gijs: Quantum computing en complexity - 16 mei PRESENTATIE en VERSLAG
Freek en Lynn: Langste pad - 21 mei
Timon en Maarten: complexity of (parallel) deadlock detection - 23 mei
Jesper en David: Kolmogorov complexity: 23 mei

Les voorbereiden ...

tegen 7 maart: hoofdstuk 2 "NP and NP completeness"
tegen 14 maart: hoofdstuk 3 "Diagonalization"
tegen 19 maart: tot en met pagina 87
tegen 21 maart: heel hoofdstuk over SPACE COMPLEXITY
tegen 26 maart: tot pagina 100
tegen 28 maart: tot pagina 112
tegen 30 april: rest van hoofdstuk over randomised algorithm
tegen 2 mei: copies uit boek van Traub (af te halen aan secretariaat)
tegen 7 en 9 mei: copies uit boek van Traub
tegen 14 mei en later: copies uit eindwerk K. Spletinckx over Benaderingsalgoritmes

Het examen

Op de volgende data kan je examen afleggen - bij elke datum staat hoeveel slots er (nog) zijn. Als je een datum wil, mail dan naar ons, eventueel met voorkeur voor- of namiddag (niet gegarandeerd). Als geen enkele van deze dat kan, mail ons met een voorstel. Mogelijk komen er nog data/slots bij, maar dit is het zowat voorlopig.

woensdag 6 juni (6 slots) [Timon Van Overveldt (liefst voormiddag), Freek Holvoet, Nathan Vandecauter, Sander Deryckere]
vrijdag 8 juni (7 slots) [Tom Desair (voorkeur namiddag), Willem Van Onsem (voorkeur namiddag), Jesper Cockx]
maandag 11 juni (8 slots) [Maarten Allard, Ingmar Dasseville (voorkeur voor de namiddag)]
woensdag 13 juni (9 slots) [Job Noorman]
vrijdag 15 juni (7 slots) [Jo Devriendt, Gijs Vanspauwen (liefst vroege namiddag), Brian Burlet]

Het examen is mondeling met schriftelijke voorbereiding en open boek.
De leerstof bestaat uit wat in de les behandeld werd (tot op de diepte waarop het behandeld werd), je eigen project en 1 project van een medestudent - je kiest zelf welk.

De punten voor het vak zullen verdeeld worden als volgt: 14/20 op het examen (reproductie en inzicht), 3/20 op de uitwerking van je project, 3/20 op activiteit tijdens de lessen/oefenzittingen.

De examenregeling wordt gemaakt in overleg met de studenten.

Informatie over de oefeningen: oefeningen en lessen lopen wat door elkaar. Het is best alles te volgen.

Gelieve fouten in de documenten te melden. Dank u.

Meest recente update: 21-3-2012