Seminar Artificial Intelligence and Complexity

Schedule

• =======
• 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 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:

• [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, An Introduction, 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, Addison-Wesley, 2005.
• [N] — M. Negnevitsky, Artificial Intelligence, A Guide to Intelligent Systems, second edition, Addison-Wesley, 2005.
• [P] — C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
• [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.

Topics

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.

Questions/remarks: kosters@liacs.nl.

12 May 2006 — http://www.liacs.nl/home/kosters/saic/index.html