LasVegas Algorithm

Understand the random nature of Las Vegas Algorithms and how they are written.

Las Vegas is known for gambling. Sometimes “gambling” with the amount of time it takes for an algorithm to run is a great method to ensure that you get the right answer. In this project we will gamble with time and number of points generated to ensure that we find a point within a circle with a specific radius.

Probability- How likely an event is to occur, typically determined after many repeated trials.

Uniform Distribution- A probability distribution where every value has an equal probability.

Random number seed- A number used to initialize a random number generator to get a specified set of random numbers so the results are the same across runs.

Las Vegas Algorithm- a randomized algorithm that always gives the correct answer but in an indeterminate amount of time.

Write a function in StudentAnswer.py that:

1.     Uses a random seed.

2.     Generates an x and y value for a point based off a random uniform distribution from -1 to 1.

3.     Adds the points to the pts list.

4.     Calculates the distance from the point to the center of the circle at (0,0)

5.     Determines if the distance is within the radius of the circle.

a.     If it is, end the loop.

b.     Otherwise, loop through step 2-5

6.     Run the program using a specific seed and a specific radius.

• Set the seed to 5 and the circle radius to 1.

  • • What is the runtime?

    • How many points does it generate?

• Restart the program and set the seed to 42 and the circle radius to 1.

  • • What is the runtime?

    • How many points does it generate?

      • • Are the point(s) in the same spot(s) as previously?

• What difference does the seed make?

• Restart the program and set the seed to 5 and the circle radius to 0.05.

  • • What is the runtime?

    • How many points does it generate?

• Restart the program and set the seed to 5 and the circle radius to 0.0005 ()

  • • What is the runtime?

    • How many points does it generate?

• Restart the program and set the seed to 5 and the circle radius to 0.000005 ().

  • • What is the runtime?

    • How many points does it generate?

• What difference does the radius make?

What is Las Vegas?

What does a random number seed do?

What does changing the radius of the “target” in a Las Vegas algorithm do?

Another highly used Las Vegas algorithm to implement (Quicksort)