Basics of algorithmics, computation models, formal languages

author: Colin de la Higuera, University Jean Monnet, St Etienne
published: July 2, 2007,   recorded: July 2007,   views: 19949


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 1:01:07
Watch Part 2
Part 2 56:35
Watch Part 3
Part 3 24:14


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.

See Also:

Download slides icon Download slides: bootcamp07_higuera_bacm.pdf (522.0 KB)

Download slides icon Download slides: bootcamp07_higuera_bacm.ppt (723.0 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Colin de la Higuera, July 6, 2007 at 4:39 p.m.:

A comment upon the talk. The idea was to start imagining some elements of TCS revisited for ML students. I suppose there are other possible ways of doing this, and I don't claim this is the most important bits nor that it is essential.
I also wish to say that there are some murky bits, specially about the KMP algorithm. (sorry)

Comment2 Alex Gillis, September 29, 2007 at 2:56 a.m.:

I really enjoyed this lecture. Its the one that has most stayed with me. I knew a little about complexity classes, but you introduced a lot of incredible new stuff, quickly but it a very intuitive way.

Comment3 Abazh, December 22, 2007 at 2:21 p.m.:

I do really enjoyed this lecture. I like the way you deliver explanation, thus make me stayed until the end of the vid lecture. Thanks!

Comment4 quelqu'un, January 16, 2008 at 2:37 p.m.:

la partie 2 s'arrete et ne bouge plus après 18 minutes 52!
(the part 2 stops and do not want to continue when reaching 18 minutes 52!)

Write your own review or comment:

make sure you have javascript enabled or clear this field: