Random Numbers
Randomized Algorithms can be broken down into two classes of algorithms:
- Las Vegas Algorithms, which use the random input to reduce the expected running time or memory usage but are guaranteed to terminate with a correct result, and
- Monte Carlo Algorithms, which have a chance of producing an incorrect result (but hopefully perform "pretty well" on average).
there exist computational algorithms that can produce long sequences of seemingly random results, which are in fact completely determined by a shorter initial value, known as a seed.
Basically, you create an instance of a random number, and you seed it with some number, which is then used to generate the sequence of "random" numbers. This type of a random number generator is said to be pseudo-random because it seems to be random for all intents and purposes, but given the seed, it's fully deterministic.
In C++, the random number generator is the rand() function, which generates a random integer between 0 and RAND_MAX, inclusive.
- Before we call rand(), however, we must first seed it by calling the srand() function (which stands for seed rand) and passing our seed integer as a parameter. It is common to use the current system time as a seed.