YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 18-02 Poking Around

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. So we have talked about using search trees, pre-processing,
  2. and approximation to solve NP complete problems.
  3. But there's one technique that we haven't yet talked about
  4. and that is using randomness to solve challenging problems.
  5. Now you know that so far in this course, I have always insisted
  6. on finding guarantees for the performance of algorithms.
  7. I wanted to have guarantees for the running time of the search trees.
  8. I even wanted to have guarantees for approximation. So am I ready to give that up now?
  9. Actually, I'm not, because even when we use randomness,
  10. we can demand certain guarantees from our algorithms.
  11. So, one way we could demand a guarantee from a random algorithm is,
  12. that we say it produces the correct or best possible solution with a certain probability.
  13. So best would be in the case of optimization problems
  14. and correct, of course, in the case of decision problems.
  15. And so, we'll also write this down for decision problems
  16. and finally we could also say that the algorithm has a running time that is random,
  17. and we want the running time to be polynomial with a certain probability
  18. and of course in this case here, we would be demanding that the solution is always
  19. the best possible solution or the correct solution.
  20. Well, actually we could also have combinations of these,
  21. but then the algorithm becomes rather weak in my mind
  22. and actually I'm not aware of any example where I have seen this before.
  23. Now, some of these approaches have special names
  24. and this one here is known as a Monte Carlo algorithm,
  25. and this one here is known as a Las Vegas approach.
  26. Don't ask me what that says about casinos in
  27. Europe versus casinos in America because I have no clue.
  28. Now the two approaches, Monte Carlo and Las Vegas are actually related to each other,
  29. and if you think about it for a little while, I think you can figure that out yourself.
  30. So my question for you is how are Monte Carlo algorithms
  31. and Las Vegas algorithms related to each other, and I'll give you three choices here.
  32. Is it that any Las Vegas algorithm can be turned into a Monte Carlo algorithm?
  33. So any algorithm over here can be turned into an algorithm like this.
  34. Is it the other way around, that any Monte Carlo algorithm can be turned into a Las Vegas algorithm?
  35. Or is it even that the two approaches are, roughly speaking, of course, more or less the same.