This chapter is from the book
This chapter is from the book
This chapter is from the book
Creative Exercises
2.2.15 Sicherman dice. Suppose that you have two six-sided dice, one with faces labeled 1, 3, 4, 5, 6, and 8 and the other with faces labeled 1, 2, 2, 3, 3, and 4. Compare the probabilities of occurrence of each of the values of the sum of the dice with those for a standard pair of dice. Use StdRandom and StdStats.
2.2.16 Craps. The following are the rules for a pass bet in the game of craps. Roll two six-sided dice, and let x be their sum.
If x is 7 or 11, you win.
If x is 2, 3, or 12, you lose.
Otherwise, repeatedly roll the two dice until their sum is either x or 7.
If their sum is x, you win.
If their sum is 7, you lose.
Write a modular program to estimate the probability of winning a pass bet. Modify your program to handle loaded dice, where the probability of a die landing on 1 is taken from the command line, the probability of landing on 6 is 1/6 minus that probability, and 2–5 are assumed equally likely. Hint: Use StdRandom.discrete().
2.2.17 Gaussian random values. Implement the no-argument gaussian() function in StdRandom (PROGRAM 2.2.1) using the Box–Muller formula (see EXERCISE 1.2.27). Next, consider an alternative approach, known as Marsaglia’s method, which is based on generating a random point in the unit circle and using a form of the Box–Muller formula (see the discussion of do-while at the end of SECTION 1.3).
public static double gaussian()
{
double r, x, y;
do
{
x = uniform(-1.0, 1.0);
y = uniform(-1.0, 1.0);
r = x*x + y*y;
} while (r >= 1 || r == 0);
return x * Math.sqrt(-2 * Math.log(r) / r);
}For each approach, generate 10 million random values from the Gaussian distribution, and measure which is faster.
2.2.18 Dynamic histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer n and two double values lo and hi from the command line and uses StdStats to plot a histogram of the count of the numbers in the standard input stream that fall in each of the n intervals defined by dividing (lo, hi) into n equal-sized intervals. Use your program to add code to your solution to EXERCISE 2.2.3 to plot a histogram of the distribution of the numbers produced by each method, taking n from the command line.
2.2.19 Stress test. Develop a client that does stress testing for StdStats. Work with a classmate, with one person writing code and the other testing it.
2.2.20 Gambler’s ruin. Develop a StdRandom client to study the gambler’s ruin problem (see PROGRAM 1.3.8 and EXERCISE 1.3.24–25). Note: Defining a static method for the experiment is more difficult than for Bernoulli because you cannot return two values.
2.2.21 IFS. Experiment with various inputs to IFS to create patterns of your own design like the Sierpinski triangle, the Barnsley fern, or the other examples in the table in the text. You might begin by experimenting with minor modifications to the given inputs.
2.2.22 IFS matrix implementation. Write a version of IFS that uses the static method multiply() from Matrix (see EXERCISE 2.2.12) instead of the equations that compute the new values of x0 and y0.
2.2.23 Library for properties of integers. Develop a library based on the functions that we have considered in this book for computing properties of integers. Include functions for determining whether a given integer is prime; determining whether two integers are relatively prime; computing all the factors of a given integer; computing the greatest common divisor and least common multiple of two integers; Euler’s totient function (EXERCISE 2.1.26); and any other functions that you think might be useful. Include overloaded implementations for long values. Create an API, a client that performs stress testing, and clients that solve several of the exercises earlier in this book.
2.2.24 Music library. Develop a library based on the functions in PlayThatTune (PROGRAM 2.1.4) that you can use to write client programs to create and manipulate songs.
2.2.25 Voting machines. Develop a StdRandom client (with appropriate static methods of its own) to study the following problem: Suppose that in a population of 100 million voters, 51% vote for candidate A and 49% vote for candidate B. However, the voting machines are prone to make mistakes, and 5% of the time they produce the wrong answer. Assuming the errors are made independently and at random, is a 5% error rate enough to invalidate the results of a close election? What error rate can be tolerated?
2.2.26 Poker analysis. Write a StdRandom and StdStats client (with appropriate static methods of its own) to estimate the probabilities of getting one pair, two pair, three of a kind, a full house, and a flush in a five-card poker hand via simulation. Divide your program into appropriate static methods and defend your design decisions. Extra credit: Add straight and straight flush to the list of possibilities.
2.2.27 Animated plots. Write a program that takes a command-line argument m and produces a bar graph of the m most recent double values on standard input. Use the same animation technique that we used for BouncingBall (PROGRAM 1.5.6): erase, redraw, show, and wait briefly. Each time your program reads a new number, it should redraw the whole bar graph. Since most of the picture does not change as it is redrawn slightly to the left, your program will produce the effect of a fixed-size window dynamically sliding over the input values. Use your program to plot a huge time-variant data file, such as stock prices.
2.2.28 Array plot library. Develop your own plot methods that improve upon those in StdStats. Be creative! Try to make a plotting library that you think will be useful for some application in the future.