Lab 4: Loops and Algorithms

Introduction

In this lab, you'll get some more experience with loops and will build a program from an algorithm. This lab is based on labs by David Eck, Scotty Orr, and Stina Bridgeman.

Setup

Create a lab04 directory for this week's lab files in your cs124 directory (~/cs124/) and change to that directory (review lab #1 if you don't remember how to do this.). Copy the provided files from the directory /classes/s07/cs124/labs/lab04 to your new lab04 directory. You can copy them one at a time, or you can use a wildcard pattern to copy everything at once:

 cp /classes/s07/cs124/labs/lab04/*.java ~/cs124/labs/lab04/

"*" is a special symbol which matches anything. Using it as part of a longer pattern like /classes/s07/cs124/labs/lab04/*.java means that it will match any file whose name starts with /classes/s07/cs124/labs/lab04/ and ends with .java - i.e. all the .java files in the /classes/s07/cs124/labs/lab04/ directory.

Important: this should only be done one time, otherwise, you will overwrite the files that are already there.

The rest of this lab assumes you are in your lab04 directory.

Exercises

Here are the exercises for this week's lab, due next Thursday. But don't wait until just before it is due to do it all! You should continue to follow the good programming style rules from lab #2. Rember to indent statements contained in 'if' statements and loops. Also, remember to comment your code. Note: points will be taken off for poor indentation or uncommented code.

Here are the exercises for this week's lab, due next Thursday. You should continue to follow the good programming style rules from lab #2. Remember to indent statements contained in 'if' statements and 'while' loops.

One round of the game of craps is played as follows:
- The player rolls two dice.
- If the sum is 7 or 11, the player wins immediately.
- If the sum is 2, 3, or 12, the player loses immediately.
- If the sum is anything else (4, 5, 6, 8, 9, 10), the player keeps rolling until she repeats the initial sum (she wins) or rolls a 7 (she loses).
Write a program, called Craps.java, that figures out the odds of winning at craps. The program should play a sufficiently high number of rounds (e.g. 10,000), and the program should report the percentage of rounds the player wins.
Write a program, called CountDivisors.java, that computes the integer between 1 and 10,000 that has the largest number of divisors, and the number of divisors that it has. It is possible that multiple integers in this range have the same, maximum number of divisors. Your program only has to print out one of them. For help on computing divisors see Subsection 3.4.2 of the textbook.

Hint: to find a maximum value, keep track of the largest number of divisors that you have seen so far, as well as the integer that had that largest number of divisors.
Write a program, called FindMin.java, which reads a series of numbers from the user, stopping when a negative number is entered, and then displays the smallest number entered (not including the negative number used to end the program).
You're a contestant on a game show, and you have been given the choice of three numbered doors (#1, #2, or #3). One door hides a prize, while the others conceal goats. You pick a door, but before your door is opened, the host (who knows what is behind each door) opens a different door, revealing a goat. The host then gives you the option to stay with your original choice or switch to the other unopened door. Will switching doors increase your odds of winning the prize?

This is a famous problem known as the Monty Hall Dilemma, and has generated a lot of controversy among people trying to work out the correct answer mathematically - some argue that it doesn't matter if you switch because after the host opens a door, you know that the prize is either behind your original door or the third one so you have a 50-50 chance of winning either way, while others claim that you should switch because your original choice only had a 1-in-3 chance of winning so the third door must have a 2-in-3 chance because you know the prize isn't behind the opened door. Still others question the assumptions, like whether or not the host always opens a door and gives you a chance to switch.

Your task is to write a program, called MonteHall.java, to simulate the playing of a large number of games, and to determine whether you should switch or not in order to win. Since the program will carry out the game many times, it won't be interactive beyond asking the user for number of games to carry out - instead, the computer will simulate the contestant by randomly picking a door each time. It should carry out the algorithm described below. By comparing the fraction of times you'd win by switching with the fraction of times you'd win by not switching, you'll be able to answer the question of whether or not you should switch doors. We'll assume that the host always gives the contestant the chance to switch, and that the host - knowing what is behind each door - never opens the door concealing the prize.

The algorithm:
```
prompt the user for how many times to repeat the game
wait for a response
let the number of wins without switching be 0
let the number of wins with switching be 0
while the game hasn't been repeated enough times
   randomly pick one of the three doors to be the one with the prize
   randomly pick one of the three doors as the player's pick
   if the user's pick is the door with the prize
      increment the number of wins without switching (because the
       player will win only if she doesn't switch doors)
   else
      increment the number of wins with switching (because the player
       has picked an incorrect door and the host won't reveal the door
       with the prize, so switching is a guaranteed win)
display the probabilities of winning without switching and of winning with
 switching 
```
Use your program to answer the question - will switching doors increase your odds of winning the prize? Does the number of times the game is repeated affect your answer? Try running the program with different numbers of repetitions, including some small numbers (like five or 10) and some large numbers (like a million or more). Try each number of repetitions several times. (e.g. run it three times using 5 repetitions each time, then run it three times using a thousand repetitions each time) What do you notice? Create a new file, called MonteHall.txt, to hold your answers for these questions.

Handin

Handin: Verify that your lab04 folder contains all of the files you created or modified for this lab, then copy your entire lab04 folder to the handin directory~mcorliss/handin/124/username (where username is replaced with your username). For example, if you're working directory is ~/cs124/lab04/ then you could do the following:

  cp -r ~/cs124/lab04 ~mcorliss/handin/124/username

where username is replaced with your particular username (e.g., mcorliss).