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
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.
2 March 2006:
Amit Oemraw and Alexander Nezhinsky on Fuzzy logic
9 March 2006:
Thijs Vermeulen and Robin van der Zwan on Surreal numbers
16 March 2006:
Alexander van der Kuijl and Kwie Min Wong on Neuro-fuzzy systems and Randomized complexity classes
23 March 2006:
Loïck Magnin on Temporal difference learning
13 April 2006:
Alexander Nezhinsky and Amit Oemraw on Sudoku
20 April 2006:
Robin van der Zwan and Thijs Vermeulen on Stable marriages and n-Queens
27 April 2006:
Kwie Min Wong and Alexander van der Kuijl on Swarm intelligence
12 May 2006, 10.00:
Loïck Magnin on Quantum computing.
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
(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.
Algorithms, Artificial intelligence, Data mining, Complexity
(all at bachelor's level, see for
instance the Dutch course pages
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:
- [A] — E. Alpaydin, Introduction to Machine Learning,
MIT Press, 2004.
- [BG] — S. Baase and A. Van Gelder,
Computer Algorithms, Introduction to Design and Analysis,
third edition, Addison-Wesley, 2000.
- [BH] — M. Berthold and D. Hand, Intelligent Data Analysis,
Springer, 1999. (second edition: 2003)
- [C] —
J.H. Conway, On Numbers and Games, second edition, Peters, 2001.
- [HTF] — T. Hastie, R. Tibshirani and J. Friedman,
The Elements of Statistical Learning, Springer, 2001.
- [KS] — F.O. Karray and C. De Silva,
Soft Computing and Intelligent Systems Design, Addison-Wesley, 2004.
- [KT] — J. Kleinberg and E. Tardos,
Algorithm Design, Pearson, 2006.
- [K] — D.E. Knuth,
The Art of Computer Programming, Volume 4 - Fascicle 2 and 3,
- [N] — M. Negnevitsky, Artificial Intelligence,
A Guide to Intelligent Systems, second edition, Addison-Wesley, 2005.
- [P] — C.H. Papadimitriou, Computational Complexity,
- [RN] — S.J. Russell and P. Norvig,
Artificial Intelligence, second edition, Prentice Hall, 2003.
- [SB] — R.S. Sutton and A.G. Barto,
Reinforcement Learning, An Introduction, MIT Press, 1998.
- [TSK] — P.-N. Tan, M. Steinbach and V. Kumar,
Introduction to Data Mining, Addison Wesley, 2006.
- Research papers, see below.
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.
- AdaBoost — B AI
[A], Chapter 15.5; [HTF], Chapter 10; [RN], Chapter 18.4; [TSK], Chapter 5.6.5.
- Approximation Algorithms — B Com
[BG], Chapter 13.4/13.8.
- Fuzzy Logic and Implication — B AI
[BH], Chapter 8.2.5; [KS], Chapter 2.6; [N], Chapter 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.
- Local Models — B AI
Self organizing maps, etc.;
[A], Chapter 12; [HTF], Chapter 14.4; [KS], Chapter 5.4.
- Neuro-fuzzy Systems — B AI
[KS], Chapter 7.
- n-Queens — P AI/Com
Choose paper(s) from
- PSPACE — B Com
[KT], Chapter 9.
- Quantum computing — Com
Complexity, see papers.
- Randomized Complexity Classes — B Com
[P], Chapter 11.2: Monte Carlo, Las Vegas, RP, PP, ZPP, BPP.
- Stable Marriages — P Com
Perform some googling, and pick a paper.
- Sudoku — P AI/Com
Choose one from the many papers on Sudoku and complexity (perform some googling).
- Support Vector Machines — B AI
[A], Chapter 10.9; [HTF], Chapter 12.3; [RN], Chapter 20.6; [TSK], Chapter 5.5.
- 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.)
- Swarm Intelligence — P AI
Do some googling, and select a paper.
- Temporal Difference Learning — B AI
[A], Chapter 16.5; [RN], Chapter 21.2; [SB].
- 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 — http://www.liacs.nl/home/kosters/saic/index.html