Basics of algorithmics, computation models, formal languages

Between the many theoretical computer science issues that one should be aware of when working in Machine learning, we visit, in this series of lectures, two. The first corresponds to strings, and through the study of strings, the questions about more complex structures like trees and graphs. We describe the main algorithmic and combinatorial questions about substrings and subsequences, and concentrate our attention to the topological questions: ordering strings and computing distances and kernels. The second is complexity. Not only should we be aware (and have a reasonable control of the techniques involved) of the usual barriers, but we should know something about classes for randomized algorithms. We also show some examples concerning Las Vegas and Monte Carlo techniques.