[This quiz is due at the beginning of class on Monday, November 13.]

After making it through a challenging semester in 15-462/662, you decide to take a nice long vacation on a tropical island. Unfortunately, on the way there you get caught in a storm that leaves you stranded on a deserted island with nothing but a coconut palm. To pass the time as you wait for a rescue, you decide to use your newly-acquired Monte Carlo skills to estimate the value of pi. Using a stick and a little piece of rope, you draw a perfect circle and a square around it. You then climb high up into a tree and start tossing coconuts randomly down into the square. The fraction of coconuts that lands in the circle basically tells you the value of pi (though of course you must also account for the size of the square).

Task 1

Write some code that estimates the value of pi using the "coconut algorithm" described above. (You may use any programming language you like.). This code should take a single parameter, the number of coconuts, and return a single value, the estimate of pi.

double estimatePi( int nCoconuts )
{
   // TODO estimate pi, and return your estimate
}

Task 2

Run your code for nCoconuts = 1, 10, 100, 1000, 10000, 100000, and 1000000 and report the estimate for pi you get in each case, as well as the relative error. If e is your estimate, then the relative error can be computed as

abs( 1 - e/pi ),

In other words, it is the percent error relative to a perfect estimate where e is exactly equal to pi. (You should see this number decrease as you add more samples!)

Task 3

Does Monte Carlo seem like an efficient method for approximating the value of pi? What's a different algorithm (that we have studied in this class!) that you might use to estimate the fraction of a square covered by a circle?