## ← 18-02 Poking Around

• 1 Follower
• 35 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=Li-5FiQFIbE" data-team="udacity"></div> ``` 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.