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

1. Title:
   18-02 Poking Around
2. Description:

3. 0 0:00 - 0:03
   So we have talked about using search trees, pre-processing,
4. 3060 0:03 - 0:06
   and approximation to solve NP complete problems.
5. 6270 0:06 - 0:09
   But there's one technique that we haven't yet talked about
6. 8820 0:09 - 0:13
   and that is using randomness to solve challenging problems.
7. 13080 0:13 - 0:16
   Now you know that so far in this course, I have always insisted
8. 16280 0:16 - 0:20
   on finding guarantees for the performance of algorithms.
9. 20100 0:20 - 0:23
   I wanted to have guarantees for the running time of the search trees.
10. 23120 0:23 - 0:28
    I even wanted to have guarantees for approximation. So am I ready to give that up now?
11. 28040 0:28 - 0:31
    Actually, I'm not, because even when we use randomness,
12. 30860 0:31 - 0:35
    we can demand certain guarantees from our algorithms.
13. 34720 0:35 - 0:38
    So, one way we could demand a guarantee from a random algorithm is,
14. 38100 0:38 - 0:44
    that we say it produces the correct or best possible solution with a certain probability.
15. 43640 0:44 - 0:46
    So best would be in the case of optimization problems
16. 46130 0:46 - 0:49
    and correct, of course, in the case of decision problems.
17. 49370 0:49 - 0:52
    And so, we'll also write this down for decision problems
18. 52090 0:52 - 0:58
    and finally we could also say that the algorithm has a running time that is random,
19. 57610 0:58 - 1:02
    and we want the running time to be polynomial with a certain probability
20. 62410 1:02 - 1:06
    and of course in this case here, we would be demanding that the solution is always
21. 65640 1:06 - 1:09
    the best possible solution or the correct solution.
22. 68730 1:09 - 1:11
    Well, actually we could also have combinations of these,
23. 71470 1:11 - 1:14
    but then the algorithm becomes rather weak in my mind
24. 73840 1:14 - 1:18
    and actually I'm not aware of any example where I have seen this before.
25. 77650 1:18 - 1:20
    Now, some of these approaches have special names
26. 79550 1:20 - 1:23
    and this one here is known as a Monte Carlo algorithm,
27. 82860 1:23 - 1:26
    and this one here is known as a Las Vegas approach.
28. 85510 1:26 - 1:28
    Don't ask me what that says about casinos in
29. 88410 1:28 - 1:33
    Europe versus casinos in America because I have no clue.
30. 92580 1:33 - 1:36
    Now the two approaches, Monte Carlo and Las Vegas are actually related to each other,
31. 96340 1:36 - 1:40
    and if you think about it for a little while, I think you can figure that out yourself.
32. 100170 1:40 - 1:43
    So my question for you is how are Monte Carlo algorithms
33. 103220 1:43 - 1:47
    and Las Vegas algorithms related to each other, and I'll give you three choices here.
34. 107460 1:47 - 1:52
    Is it that any Las Vegas algorithm can be turned into a Monte Carlo algorithm?
35. 112150 1:52 - 1:56
    So any algorithm over here can be turned into an algorithm like this.
36. 116150 1:56 - 2:02
    Is it the other way around, that any Monte Carlo algorithm can be turned into a Las Vegas algorithm?
37. 122290 2:02 -
    Or is it even that the two approaches are, roughly speaking, of course, more or less the same.