AP CS A - Galton Board Application

Used during 2006/2007 School Year

Prerequisite Knowledge

Project is great after students have learned about single dimension arrays and understand what factorials are in mathematics. A basic understanding of Pascals Triangle and the Combination Formula (i.e. n C r) is recommended; however, it could be explained up front before assignment.

Premise / Development

A Galton Board is much like the famous Price is Right game titled Plinko. You drop a ball at the very top and watch it until it lands in a specific location (I will call them containers). A great animation can be seen here. Depending on the number rows in the Galton Board, the number of containers is always rows + 1 because there is always the outside of the beginning and end post that create the need for an extra container

As a class, we then figure out how many different balls we should drop depending on the number of posts. We figure the following.

1 Row - Ball can go either left or right therefore we drop 2 balls in 2 containers.
2 Rows - Ball can go LL, LR, RL, and RR therefore we drop 4 balls in 3 containers.
3 Rows - Ball can go LLL, LLR, LRL, LRR, RLL, RLR, RRL, RRR therefore we drop 8 balls in 4 containers.
...
n Rows - Ball has 2 to the nth power combinations therefore we drop 2 to the nth power balls in n + 1 containers.

Next, as a class we develop the idea of flipping a Coin to decide if the ball goes left or right at each obstacle/post.

We decide that if we create a Coin Class which automatically flips a Coin ands gives a method that allows us to identify it as HEADS or TAILS that we would have a great way of determining the random nature of the ball. Our Coin Class has the following methods...

public Coin( ); - Constructor used to make a coin that can be flipped
public void flip( ); - Flips the coin that has been created (uses random 0 or 1 to represent "Heads" or "Tails")
public boolean isHeads( ); - Returns true if the coin is heads (False assumes a coin that is tails)

Many textbooks have some sort of coin class that could fall as a substitute for this one; however, I would think this is essentially the barebones of a Coin Class.

Next, as a class how we know what the theoritical numbers of balls that land in each container is based on the number of rows.

We figure out how many balls should land in each containers given a certain number of rows.

1 Row - 2 Containers - 1 1 (C1: L, C2: R)
2 Rows - 3 Containers - 1 2 1 (C1: LL, C2: LR, RL, C3: RR)
3 Rows - 4 Containers - 1 3 3 1 (C1: LLL, C2: LLR, LRL, RLL, C3: RRL, RLR, LRR, C4: RRR)
...
n Rows - n + 1 Containers - nth row of Pascals Triangle.

So we can figure out the theoretical number of balls based on the number of rows using Pascals Triangle.

I then introduce the formula used to calculate each positions of the Pascals Triangle.

If we are on the nth row (Start labeling at 0 for the row with only one post) and we are in the rth position (positions start with 0 on the far left). Then the formula used to calculate the position is number = n! / ( r! * (n - r)! ). The formula is published on this page. I then assign homework for the students to complete a static method named "nCr" which takes the parameter n (rows) and r (position) and returns the value of that position on Pascals Triangle. They are expected to also complete a "factorial" method which allows them to take the factorial of a specific number. We want to use double for LARGE values which can be easily reached by factorials.

Skeleton Code for this section is...

public static double nCr ( int n, int r )
{
double rows = n;
double pos = r;
double final_total = factoral(rows)/(factoral(pos)*factoral(rows - position)));
return final_total;
}

public static double factorial(double n )
{
// Find the value for the factorial of n
}

Next, as a class we discuss how the ball is going to actually move down the board.

We are going to represent the containers through the use of an array with rows + 1 number of positions. Flipping a coin is going to determine eventually which position it falls in by flipping a coin as many times as rows. The diagram below will show you how we will where the coin lands (which container) and how and then we can discuss how we are going to track this in an array.




This now gives us a formula for each position of the containers and allows us to easily flips a coin the same number of times as rows and keep count of the +1 and -1 using Tails or Heads values. The sum of these is going end up being a number (rows * -1) + 2x where x = { 0, 1, 2, ..., rows}.

But, what if I want to put this in an array and simply increment that position of the array if a coin lands there to give a quick and clean count after the 2 to the nth power coins have dropped down the Galton Board?

Notice that at each position / container that the sum is always (rows * -1) + 2x where x = { 0, 1, 2, ..., rows}, if we always create an array that is rows + 1 in size then we have enough positions. Ask the students this question, how are we going to go from sums of coin flipping down to positions in an array. Make sure to mention AGAIN that positions are 0 to length - 1 in an array. Here is what we can up with during class.



So, given a coin sum (based on all flips of the coin), we can match that up with an array position.
Now I am ready to give the students there Galton Board Project

Assignment Parameters

1. Students are to create a program which uses the coin class and flips the coin the same number of times as rows. There should be 2 to the nth power total flips to properly match the theortecial distribution.
2. Students should create it so that the program displays as follows...
   
3. The output contains the theoretical probability on the left and the number of times in container based on the coin flips on the right.
4. The number of errors is calculated by taking the difference between EACH theoretical total and the trial total. We then take the total number of erros and divide it by the total number of coins.

Teacher to Teacher

This process took about one full day of class and then I gave the students the weekend to finish the project. They seemed very happy and understood EXACTLY how to relate the number of rows, coin flips, total coin flips, and storing them in an array.