CS341 Study Guide - Random Seed, Quicksort, Quickselect
Document Summary
Now, when considering find-majority as a solution, there are some objections you might propose: For example, if there is no majority element, the algorithm will loop forever. Problem 2: sometimes it might take a long time. True, this is expected to be extremely rare, but perhaps your application is very time-sensitive (e. g. , air traffic control, surgery assistant, etc. ) in which guaranteed run-time is important. Problem 3: in practice, we do not use truly random numbers, but rather pseudo-random numbers. Many algorithms in computer science are based on access to a random series of coin flips, or a random series of numbers. Polling: sometimes it is impractical to test all items in a set, and we test some random sample instead. Monte-carlo methods: sometimes functions are estimated using random sampling. Allocation: sometimes it is useful to be able to make an unbiased decision, for example, by drawing straws to see who gets the last piece of pie.
