CS 101 (Spring 2000)
Lab 5: Slices of PI

Lab Assigned
Design Due
(In class)

10 AM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
10 AM
15 Feb 18 Feb 22-33 Feb 29-30 Feb 03 Mar

Click here for the class-sponsored design

Overview:

Iteration is another technique for repetitive computations. In this lab, you will use recursion to draw a circle and iteration to throw darts at the circle, which is circumscribed in a square.

Goals:

By the end of this lab, you should This lab contains two parts, design and implementation, due as shown at the beginning of this document. The Monday after your design is due, a sample design will be handed out in class. We may choose one of your designs for this honor; or, we may write one up on our own. Remember, there is no right or wrong design, but each design may have its own strengths and weaknesses.


Before starting:

[[[ Download PC zip ]]]
Zip includes:

Recall that the following lines should appear at the top of any files that use the terminal or canvas classes.

import terminal.*;
import canvas.*;

Problem description: Slices of PI

Design and implement the class PI.java that does the following.


Design Strategy


Monte Carlo methods and PI

Algorithms that involve randomness are often said to use Monte Carlo technqiues---the term is named after the famous casino. Randomness is often employed to lend a sense of realism to games and other simulations.

In this case, we wish to throw darts at a board. The board is square, with each side having length S. How do we simulate a random dart throw? Unlike real life, we do want to be sure that it lands somewhere in the square. We can decompose the problem into picking an x and a y coordinate, each chosen randomly so that the dart lands in the square.

For example, if we say the square is addressed from (0,0) to (S-1,S-1), then we can use:

   int randX = (int) (Math.random() * S);
   int randY = (int) (Math.random() * S);
to obtain a random x and y coordinate.

Next, we care whether the dart lands inside the circle. By this, we mean that the distance of the dart from the center of the circle is no greater than the circle's radius.

Why do we care? If we throw darts randomly at the square, some will land in the circle, and some will land outside the circle. If the darts are thrown uniformly, without bias, then we expect the darts to land in the circle at a rate proportional to the circle's area with respect to the square.

The circle's area is


                        ___     ___ 2
 circle area =   PI x   |    S    |
                        |   ---   |
                        |    2    |
                        ---     ---
while the square's area is
                          2
 square area =          S 

Dividing these two yields the probability of a dart landing in the circle, namely PI/4. Thus, if we throw darts, counting the number that land inside the circle and the number that we throw, the ratio of those two numbers should approach PI/4.

Looking forward to implementation

( class-sponsored design)
  1. Implement the PI problem.
  2. Complete a code cover sheet.
  3. Provide printouts of any files you created or modified for this assignment.
  4. Provide transcripts of your runs showing the required statistics (as computed by your program, not by you!).


Last modified 09:31:43 CST 18 February 2000 by Ron K. Cytron