I wanted to know what are randomized algorithms and what are some of their uses?

When do you think they outperform "standard" algorithms?

  • $\begingroup$ This may be a start: en.wikipedia.org/wiki/Randomized_algorithm to answer the part "what". I think your question should be "when do randomized algorithms outperform non-randomized algorithms", if that question even makes sense. $\endgroup$ – nbro Jan 7 '17 at 0:59
  • 2
    $\begingroup$ This is an extremely broad question. I'm tempted to say you'd need a book to answer it, but maybe a bookshelf would be more appropriate. Are you just looking for a definition? Could you restrict your question to something more specific? $\endgroup$ – quicksort Jan 7 '17 at 1:01
  • $\begingroup$ I would like to know where are these algorithms used (the wikipedia examples were not ovious to me). $\endgroup$ – ryuzakinho Jan 7 '17 at 18:23
  • $\begingroup$ They're literally everywhere. Every algorithm which "flips a coin" is called randomized algorithm. When you have two choices but don't know which one is better, what would you do? If you know they are good "in average", you can flip a coin to make the decision. That's how randomized algorithms work. The best thing is they are simple. Besides, sometimes deterministic algorithms (what you called "standard") are vulnerable to an adversary who always feed them the worst input, while randomized algorithms are still good "in average". $\endgroup$ – aaaaajack Jan 9 '17 at 11:09
  • $\begingroup$ Thanks a lot. It is more clear now. The last sentence gave me some more insight about the benefits of using a randomized algorithm. $\endgroup$ – ryuzakinho Jan 10 '17 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.