Task 1: Rolling Dice

We'll begin by simulating rolling a six-sided die. In your LoopsLap project, create a new class named RollingDice, which will contain your main method. Add code to your class so that it is the same as shown below:

import java.util.Random; //find it

public class RollingDice {

    public static void main(String[] args) {
        int numSides = 6;
        Random ranGen = new Random(); //make random number generator
        System.out.println(ranGen.nextInt(numSides) + 1); //use it
    }
}

We'll be using Java's Random class make your program's execution unpredictable. To use this class you must:

1. tell the compiler where to find it using an import statement,
2. make it by constructing a Random software object, and then
3. use it to generate a pseudo-random numbers.

Run your program several times. Does it work the way it is supposed to? Do you get a different number each time the program is run? What is the maximum number of times you'd need to run your program to to get a number that repeats?

We use the nextInt method to generate a random integer. Each time the nextInt method is executed another random integer is generated in the range from zero up to but not including the specified maximum. For ranGen.nextInt(6) we're specifying 6 is the maximum resulting in a range of possible integers of 0 to 5 inclusive. To get the range of 1 to 6 for a six-sided die, we also must add 1 to the generated number as shown in the code above.

Now, let's roll the die many times and see how often a number repeats. Modify your code by adding a loop so that it rolls the die 100 times and only prints a message when a 3 has been rolled. How many times would you expect 3 to repeat when the die is rolled 100 times? Is this close to what your program produces?

Next, modify your program to count how many 3's have been rolled and print that count only after the loop has ended. You'll need a variable to store the count. Be careful to declare it at the beginning of your main method.

If your indenting gets messed up remember the tip from lab 2 - highlight the code to fix and enter "control-i".

Rolling a Die 1000 Times

Now that you have a program that simulates rolling a die 100 times, counts the number of times a 3 is rolled, and prints out that count, run it several times, but now each time rolling the die 1000 times. Are the results what you expected? Does the simulation agree with your intuition? Show your results to your Lab TA when you have a working solution.

Task 2: The Birthday Paradox

Switch so that your partner is in control of the keyboard

Let's use what we've learned so far to write another short program to verify the Birthday Paradox. This program should be easy to write given what you've learned in the task above. Create a new class named BDayParadox. What is this paradox? Answer this question - How many people do you need in a room to have, on average, at least two people with the same birthday (same month and same day)? You might think that you'd need 100 or more, but you'll only need 24 people! This is known as the Birthday Paradox. It takes, on average, only a room of 24 people to get two with the same birthday!

We can verify the birthday paradox by rolling a 365-sided die with each number representing one day of the year (for non-leap years). On the average it takes 24 rolls of a 365 sided die to observe a number that repeats. Create a program to roll a 365 die 24 times and display the value of each roll. When you run your program, do you see in the output one or more duplicates displayed? Show your program to your Lab TA when you believe it verifies the paradox.

Task 3: The Collatz Conjecture

Description

The next task we'll work on a bit more challenging algorithm that explores a conjecture in the field of discrete math that is currently unsolved and is being researched. Consider the following algorithm where n is an integer:

Repeat until n equals 1

• If n is even, set n to n/2
• If n is odd, set n to 3n + 1

The Collatz conjecture postulates that this algorithm terminates for all positive integers. This hasn't been proven, but we can show that it works for certain numbers by writing a program.

Implement the Collatz Algorithm.

Create a new class in your project named Collatz with a main method that implements the above algorithm for an integer n that the user enters. To implement this algorithm, you'll need to loop until n is equal to 1. In the loop's body, you'll need to recalculate the value of n depending on whether n is even or odd. Recall the remainder operator, %, can be used to determine this. If n is even then the new value of n is half of the original (make sure to use integer division). If n is odd then the new value of n is one more than three times n.

Test your program by having it print out the sequence of values for n. Run your program for each of the following starting values: 24, 25, 27, and 160. For 24, your program should generate: 12,6,3,10,5,16,8,4,2,1.

Verify the Collatz Conjecture over a Small Range.

Now, modify your program to verify that the Collatz conjecture for all integers from 1 to 5. Here are a few helpful hints:

• Keep your loop that implements the Collatz algorithm on n.
• Remove the user input and replace it with a loop that tests the values of n for the specified range.
• Use different variables in your two loops or else your program won't correctly go through the range of values.
• Add output that says "Testing X:" where X is the current value of n being tested.

If you've done things correctly, your output will look similar to:

Testing 1: 
Testing 2: 1,
Testing 3: 10,5,16,8,4,2,1,
Testing 4: 2,1,
Testing 5: 16,8,4,2,1,

Verify the Collatz Conjecture over a Large Range.

Now, modify your program to verify the Collatz conjecture for all integers from 1 to 10,000. Modify your output statement(s) so that it only displays "Testing X:". If your program terminates (and is correctly coded), what can you conclude about the Collatz conjecture for this range of numbers?

Share your result with your Lab TA.

Task 4: Debugging Practice

Switch again so that your partner is in control of the keyboard

Take about 20 minutes on this task.

Writing programs using loops typically requires a bit of debugging to get them working the way you desire. We've created a simple program called the Guess game that will give you some practice debugging common problems with loops. Download Guess.java and add it to your LoopsLab project folder (right click on the link and choose "Save Link As" and navigate to your project folder, hit "F5" to refresh the project window).

The Guess game has already been written, but we've put a few bugs in it. Failure to follow naming conventions should be noted, but strictly speaking, failing to follow convention is not a bug that prohibits the game from working as desired. The bugs require you to make two minor changes and two additions to our program! The program should play by the rules but, because of the bugs, it doesn't. Without the bugs the game plays five rounds and during each round the user is given three chances to guess a number between 1 and 6 inclusive. During each round, the program generates a random number in the same way we did above. If the user guesses correctly, then s/he wins a point, otherwise the computer wins a point. At the end of five rounds, whoever has the most points wins the game.

Your goal is to make the Guess class run correctly and to handle a wide variety of user inputs. You may assume that the user will always input integer values when asked for a number; however, you will need to make sure the Guess game behaves appropriately if the integer entered by the user is not within the valid range.

Before looking at the code, run the Guess program to see what it does. It is vital when debugging a program, to collect evidence before making ANY changes to the code. In fact, a good debugger will know for certain what is wrong with their program before they change their code. This is done by carefully tracing the code with the input sequence that causes an error in order to discover the code that is incorrect OR MISSING.

Another important concept when dealing with Random generators, is to seed the generator when it is constructed so that it produces the exact same sequence of numbers each time the program is run. This makes it much easier to debug programs with this kind of randomness. How do you seed the generator? Change the code that constructs the generator to include a number as shown below:

Random ranGen = new Random(11); //11 is a seed value

Do this now to make the execution of the Guess program repeatable for debugging.

After you have identified one or more incorrect behaviors, take a look at the Guess class code and try to figure out what has gone wrong, correct the problem, and run the program again. Did you fix it? If yes, are there other problems? When debugging it is important to focus on one problem at a time. Once you are satisfied you've corrected that problem, then run the program again to identify the next problem. Continue in this way until you are satisfied that the program plays by the rules. As you correct the code, it is a good idea to include a comment on each line or section of code that you correct saying what you've changed (and why). This helps you keep track of the changes, which is particularly useful if you need to undo a change later if you discover that it wasn't the cause of the problem.

After about 20 minutes, tell your Lab TA which errors you've discovered. Everyone should be able to find at least four errors.

Challenge Tasks

In the time remaining (or after the lab if you wish), give these challenges a try. You can do them in any order. If you are able to complete a challenge during lab, check your answer with your Lab TA.

Challenge 1

How many rolls do you think it will take for a die to get a run of eight 3's (i.e., roll a 3 eight times in a row)? Modify your program in Task 1 to figure this out. Do this incrementally. First add code to display each time there is a run of two 3s. Then modify your code to display when there is a run of eight 3s. Finally add code to count and display the number of rolls it takes to get to a run of eight 3s.

Now modify your program to determine, on average, how many times it take to get the run? (Hint: do several trials and average the results.)

Challenge 2

For the Collatz conjecture code in Task 3, modify your code to determine which initial value (in the range from 1 to 10000) takes the most steps (i.e., repetitions) until convergence.

Challenge 3

For the Collatz conjecture code in Task 3, modify your code to determine which initial value (in the range from 1 to 10000) reaches the largest number during the algorithm.

Challenge 4

The Collatz conjecture in Task 3 makes no claims on non-positive numbers. Try inputs of -2, -5, and -17. Do you notice a pattern in those values? Attempt to modify your code to catch an input where the Collatz conjecture does not hold? What do you think would be necessary to detect when the conjecture doesn't hold more generally? For example consider a starting value of -80.