Forgot to tell you about the Turing award for PAC...

In my haste to complete the class on time, I forgot to mention that the Turing award for last year

went to Leslie Valiant for inventing the notion of PAC (probably approximately correct) as part of his work

on the theory of the learnable.

see http://www.acm.org/press-room/news-releases/2011/turing-award-10

(I hope you still remember that the Turing award for this year went to Judea Pearl for his work on

bayes networks)

Rao

ps: I misspoke a bit when talking about "sample complexity"--it is the least number of examples needed to learn the

     concept by any algorithm (not the "most"). You saw that the inequality on the slide was N >=