## ← 18-35 Randomization Vs Determinism Solution

• 1 Follower
• 25 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=ljlT4lZyX54" data-team="udacity"></div> ``` 1 Language

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

1. And I think there are two correct answers here.
2. The first one is indeed that randomized algorithms are in some way
3. more difficult to trick into a worst-case behavior than deterministic algorithms.
4. Now, to illustrate this for example think about the greedy algorithm
5. that we use to approximate vertex cover.
6. We could trick that approximation algorithm into a worst-case behavior
7. simply because we expose the way that it works
8. and we knew how it would work because it works deterministically.
9. For randomized algorithm, of course, we never quite know what it is going to do.
10. So, constructing a worst-case instance or finding an instance
11. that really exposes worst-case behavior here
12. might in some way be more difficult than for deterministic algorithm.
13. Randomized algorithms can definitely be easier to analyze than deterministic algorithms
14. although of course this one is a little bit debatable
15. since statistics and probability can also get very nasty
16. but when you get down to search tree analysis versus the analysis of random algorithms
17. and with what probability they produce correct results
18. usually these over here are easier, and we also had that in the last quiz where I mentioned it.
19. Now, finally a random algorithm does not explore solutions that a deterministic algorithm would miss.
20. Rather, it's the other way around.
21. The deterministic algorithm at least if it's not in the approximation algorithm
22. will always guarantee that you find a correct solution.
23. On the other hand, with the randomized algorithm, you know about your probabilities
24. because you're demanding guarantees, but nevertheless, you can never be 100% sure.
25. You might be 99.9999% sure that it produces the correct answer but never 100.