Seminar Artificial Intelligence and Complexity

The Seminar Artificial Intelligence and Complexity is intended for Master students in Computer Science. Lectures are in English. The seminar is organised by dr. J.M. (Jeannette) de Graaf and dr. W.A. (Walter) Kosters. Example topics include: temporal difference learning, swarm intelligence, data mining, support vector machines, AdaBoost, approximation algorithms, generation of permutations. Students can also suggest subjects. For a full list, see below.
Dates: Thursday 9 February 2006 - Thursday 4 May 2006 (8 sessions, see below); time: 13.45-15.30; room: 412, Snellius; credit points: 7 ECTS.


In this seminar we will discuss several issues from Artificial Intelligence (AI) and complexity theory. Students present these topics in one hour lectures, based on book chapters (first half of the seminar) and research papers (second half of the seminar). Note that in some cases the difference between book and paper is not very clear. Next to the oral presentations (in PowerPoint or PDF) 10 page individual essays on the subject must be written (in LaTeX). (Each person writes on his/her own two presentations.) Essays should be improved until students and lecturers agree on the contents. Students must be present during all sessions, and are supposed to actively take part in the presentations, e.g., ask quesions. Immediately after each lecture there is a short discussion between lecturers and organizers, where the presentation is evaluated. Some of the subjects can be split into two, together making a two hour lecture. The first meeting is used to make a proper schedule. Every student is supposed to choose and present two subjects, one in the first half and one in the second half of the seminar. Preferably, one is on AI, the other on complexity; and one is from a book, the other from a research paper.
You can use your own laptop for the presentations. If you don't have one available, you can use ours — let us know in advance. In that case, please email the .ppt- or .pdf-files a day before the presentation — at the latest. It is wise to also put them on a memory-stick and/or CD. We take care of a beamer.

Prerequisites: Algorithms, Artificial intelligence, Data mining, Complexity (all at bachelor's level, see for instance the Dutch course pages Artificial intelligence and Complexity).

Students should register in advance, in december 2005. (Personal visit to the organizers.) The number of participants is at most 12.

Literature, available in room 159:


Subjects are either B—"book" or P—"paper", and AI—"AI" or Com—"Complexity". Many other books on AI and/or complexity, and the internet, may be helpful.
  1. AdaBoost — B AI
    [A], Chapter 15.5; [HTF], Chapter 10; [RN], Chapter 18.4; [TSK], Chapter 5.6.5.
  2. Approximation Algorithms — B Com
    [BG], Chapter 13.4/13.8.
  3. Fuzzy Logic and Implication — B AI
    [BH], Chapter 8.2.5; [KS], Chapter 2.6; [N], Chapter 4.
  4. Knuth's Volume 4 — B/P Com
    [K] (pre-versions available on the internet); subject: generating all tuples, permutations, combinations, partitions, ...
    Example topics: de Bruijn sequences, Topological sorting.
  5. Local Models — B AI
    Self organizing maps, etc.; [A], Chapter 12; [HTF], Chapter 14.4; [KS], Chapter 5.4.
  6. Neuro-fuzzy Systems — B AI
    [KS], Chapter 7.
  7. n-Queens — P AI/Com
    Choose paper(s) from bibliography.
  8. PSPACE — B Com
    [KT], Chapter 9.
  9. Quantum computing — Com
    Complexity, see papers.
  10. Randomized Complexity Classes — B Com
    [P], Chapter 11.2: Monte Carlo, Las Vegas, RP, PP, ZPP, BPP.
  11. Stable Marriages — P Com
    Perform some googling, and pick a paper.
  12. Sudoku — P AI/Com
    Choose one from the many papers on Sudoku and complexity (perform some googling).
  13. Support Vector Machines — B AI
    [A], Chapter 10.9; [HTF], Chapter 12.3; [RN], Chapter 20.6; [TSK], Chapter 5.5.
  14. Surreal Numbers and Games — B Com
    [C] and Claus Töndering's text on Surreal Numbers. (Though it has perhaps not much relation with the other subjects, it is really great fun.)
  15. Swarm Intelligence — P AI
    Do some googling, and select a paper.
  16. Temporal Difference Learning — B AI
    [A], Chapter 16.5; [RN], Chapter 21.2; [SB].
  17. Tetris — P Com
    R. Breukelaar, E.D. Demaine, S. Hohenberger, H.J. Hoogeboom, W.A. Kosters and D. Liben-Nowell, Tetris is Hard, Even to Approximate, International Journal of Computational Geometry & Applications 14 (2004) 41-68;
    H.J. Hoogeboom and W.A. Kosters, Tetris and Decidability, Information Processing Letters 89 (2004) 267-272;
    H.J. Hoogeboom and W.A. Kosters, How to Construct Tetris Configurations, International Journal of Intelligent Games & Simulation (IJIGS) 3 (2004) 94-102.


12 May 2006 —