English subtitles

← 18-35 Randomization Vs Determinism Solution

Get Embed Code
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.