I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of the currently most interesting/greatest algorithmic results in machine learning. The potentially tricky constraint is that the students will not have any particular previous knowledge of linear algebra or the other main topics in machine learning.
This is really to excite them about the topic and to let them know that ML is a potentially exciting research area for algorithms experts.
EDIT: This is a final year undergraduate course (as we don't have graduate courses in the UK in the main). They will have done at least one basic algorithms course beforehand and presumably done well in it to have chosen the advanced follow up course. The current syllabus of the advanced course has topics such as perfect hashing, Bloom filters, van Emde Boas trees, linear prog., approx. algorithms for NP-hard problems etc. I don't intend to spend more than one lecture exclusively on ML but if something is really relevant to both an algorithms course and an ML one then of course it could also be included.