TCS-TR-B-05-1

Date: Tue Jun 7 05:53:42 2005

Title: Course Notes on Theory and Practice of Algorithms - Part I: Algorithmic Learning

Authors: Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science, Hokkaido University, North 14, West 9, Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. This report contains the course notes of Part I of Theory and Practice of Algorithms. Within this part we deal with algorithmic learning. Some learning algorithms for fundamental learning problems are studied. Furthermore, we focus our attention on the complexity theoretical issues involved.

In addition to the usual wort-case analysis, we also deal with the average-case behavior. Therefore, one lecture is devoted to introduce the subject of average-case analysis of algorithms.

Finally, after having gained a deeper understanding of what algorithmic learning really is, we exemplify the application of algorithmic learning to the field of data mining.