CSE 131 Module 3: Iteration

Studio

Review studio procedures before starting.

Feel free to participate in a different group than last time. This is totally up to you, but try to find a group that makes it easy for you to participate.

By the end of this session, a TA will have completed a Studio Observation form for your group. You will have to attach your team's observations so keep track and type things in as you go along for printing by the end of studio.

Be careful how you use the web. You are required to develop solutions as a group by thinking not by finding solutions that have been thought out by others. You must be able to explain anything that you have done.

Warmup

Problem 1: Computing Pi by throwing darts

Computer scientists often use simulation as a means of modeling, understanding, and predicting real-world phenomena.

Your group is auditioning for Lost by proving your group's ability to compute Pi using only the materials at hand, as follows:

  1. As a group, develop an approach for computing Pi based on the above materials.
  2. Implement your approach using iteration. You can start with the following Pi.java file that you can paste into a new Java class in one of your lab projects.
    This may be the first new Class you have developed, but eclipse makes it easy:
    • Right-click on the package name in which you want to define the new class. In this case, use studio3.
    • Click New...
    • Choose Class
    • Pick the name Pi for this class, since the code you will paste is for class Pi. Java style dictates that its classes should begin with a capital letter!
    • When the editor opens for your new class, copy and paste the code from Pi.java into the class.

    You will need to simulate a random dart thrower. The function math.random() will help, as it returns a nonnegative double less than 1.0. You may also find the Math.sqrt() function to be helpful.

  3. Investigate and discuss how well your technique computes Pi.

Problem 2: loop invariants

Fill in the following iterative method for computing the sum of the square of the first n positive integers: 

  // do this on paper, no need to code this

  int sumSquared(int n) {

     // Initialization

     int ans =  ??,
          i   = ??;

     while ( i != n  )   {
        //  place A
        i = i + 1;
        ans = ans + ??
        //  place B
     }

     return ans;
  }
  1. What is the termination condition for the loop?
  2. What loop invariant will help you prove that the loop computes 
             ans == 1*1 + 2*2 + 3*3 + ... + n*n ?
  3. Complete the initialization so your loop invariant holds before the loop executes.
  4. Write a proof that the loop body preserves the loop invariant. You want to show the following:
    if prior to the loop body (place A), the following holds: 
         ans == 1*1 + 2*2 + ... +  i*i
    then at place B the following holds: 
         ans' == 1*1 + 2*2 + ... +  i'*i'
    where ans' and i' are the new values computed by the loop body.

Further investigations

If you have time, pick one or both of the following:

  1. Investigate the fairness of the math.random() method.
    1. What normative criteria should a random number possess?
    2. How can you measure the fairness of a random number generator?
    3. Implement some tests and discuss your results amongst yourselves and other groups.
  2. There are other ways of computing Pi. Try some of these and study their effectiveness in terms of the number of iterations you use.

Submitting your work (read carefully)


Last modified 22:14:02 CST 11 November 2009 by Ron K. Cytron