English subtitles

← 18-34 Randomization Vs Determinism

Get Embed Code
1 Language

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

  1. It's actually a wide open discussion whether randomization is actually helpful
  2. because with considerable analysis many randomized algorithms
  3. can actually be turned into deterministic algorithms by using a process
  4. called derandomization, and derandomization usually keeps fundamental properties
  5. such as polynomial running time, all the base of the exponent.
  6. Randomized algorithms therefore might be a bit faster
  7. but it's unclear whether this is due to luck if you will or lack of thinking.
  8. So, if you were to pit these two against each other, randomization versus determinism,
  9. it's not really clear who would win or if it's a draw.
  10. So to conclude our exploration of randomization, what might be some reasons that randomization
  11. is actually at least a bit more powerful than determinism?
  12. Is it that randomized algorithms are in some way harder to trick
  13. into a worst case behavior as compared to determinism
  14. and after all we're analyzing all of the algorithms using worst case analysis.
  15. Is it that randomized algorithm can usually be easier to analyze than deterministic algorithms
  16. or is it that randomized algorithms actually explore solutions
  17. that their deterministic counterparts could miss.