CSE 131 Module 2: Choice & Iteration

Extensions

Extension 1: Image Processor With Iteration (6 points):

Authors

Manipulating an Image Raster

Directions: In the imagetransforms package, modify the provided Transforms Java program to implement the methods as described below. Your methods will use iteration (either while loops or for loops) to operate on the pixels of a picture.

Notes


Instructions

Each of the methods described below is found in the Transforms class.

  1. The provided method flipHoriz(Picture source, Picture target) flips the image horizontally.

    Look at the code given to you for this example carefully. It is broken into simple steps and the comments help explain why the pixel indexing works.

  2. Complete the method flipVert(Picture source, Picture target) that flips the image vertically.
  3. Complete the method flipHorizLeftHalf(Picture source, Picture target) that flips the left half of the image horizontally.
    The left half of the target image should be same as the source, but the right half of the target image should be the mirror of the left half of the source.

  4. Complete the method flipVertBotHalf(Picture source, Picture target) that flips the bottom half of the image vertically.
  5. Complete the method gradient(Picture target) that takes a single Picture as a parameter. Your code should create a color gradient by computing the following for each pixel: Thus, each pixel will have a different color depending on its position. For example, the pixel at the top left will have red=0, green=0, and blue=128. The pixel about 1/4 of the way down on the right edge will have red=255, green=64, and blue=128.
    Develop an expression for the amount of red and green in each pixel, given the x and y position of that pixel and the width and height of the image:
       int amountRed   = .....
       int amountGreen = ....
    
    Then set the pixel at (x,y) to a color based on those computations:
        target.set(x, y, new Color(amountRed, amountGreen, 128));
    


Note There are other methods in the Transform class, but they are the subject of other extensions. Once you have completed the above work, demo and you are done with this extension.
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.1
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 1


Extension 2: Loop Invariants (7 points):

Authors
Loop invariants are a tool for proving that a loop computes some useful result. This topic is covered in a discrete math course, but you can try your hand at some loop invariant proofs in this extension.

However, you must agree to the following:

Warm Up

Loops can be used to execute many simple operations. For instance:
For some a and b:
		int ans = 0;
		int i = 0;
		
		while(i != b){
		   i = i + 1;
		   ans = ans + a;
		}
This code computes the product of a and b.
We have discussed this in this video, and you can find the code in the loopinvariants package of the extensions folder. You are encouraged but not required to create other classes in that package to help you with your work below.

Part 1

Consider the following examples:
  1. 		int ans = a;
    		int i = 0;
    		
    		while(i != b){
    		   i = i + 1;
    		   ans = ans + 1;
    		}
    
    The above code computes the sum of a and b.
  2. 		int ans = 1;
    		int i = b;
    		
    		while (i != 0){
    		   i = i-1;
    		   ans = ans * a;
    		}
    
    The above code computes a to the power of b
  3. 		int ans = 0;
    		int i =   a; 
    		
    		while (i >= b) { 
    		   i   =   i - b;
    		   ans = ans + 1;
    		}
    
    The above code computes a divided by b using integer arithmetic.
  1. Find the Loop Invariants of these three loops. Once you have found them, talk to the professor to make sure that they are correct.
  2. Sketch a mathematical proof to show that these loops actually return what we say that they return. You will not need to turn this in to the professor, but it will be good practice for Part 2.

Part 2

Consider the following code:
		int power = 0;
		int i     = a;

		while (i%2 == 0) {  
  		   i = i/2;
		   power = power + 1;
		}
  1. Create a table of values for a, i, and p for a couple of initial values of a. Use this table to find the relationship between a, i and p. Hint: a is a function of i and p.
  2. This relationship is the Loop Invariant of this code. Write a mathematical proof that the loop invariant stays constant throughout the iterations. Every step must proceed from what came before it, with no gaps in logic. Any flaw will cause your submission to be rejected, but you can continue revising your proof until the end of the semester when extensions are finally due.
  3. What does this relationship say about the natural numbers (your values of a)? The fact that this relationship is true for all numbers is actually a mathematical theorem.
    That theorem is used in the Miller–Rabin primality test, which is a fast probabilistic algorithm for testing the primality of an integer:
    • If that test says no, then the integer in question is definitely not prime.
    • If that test says yes, the the integer in question might be prime.
    The uncertainty can be reduced arbitrarily by more testing.

To Demo

You must
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.2
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 2


Extension 3: One-Rep Max Weight Calculator (3 points):

Authors
Disclaimer: The authors of this extension and all personnel involved with this course are not licensed medical care providers; they represent that they have no exepertise in diagnosing, examining, or treating medical conditions of any kind, nor in determining the effects of any specific exercise. The data computed by this exercise are for informational and instructional purposes only.

Overview

In weight training, the volume of work completed in one exercise (often called a set) is typically specified as a given weight that is moved a specified number of times. These are respectively called the weight and reps (abbreviates repetitions) of that set.

In this extension, you will create a one-rep max calculator. This calculator hypothetically calculates a weight that a subject could move for one repetition, given that the same subject can successfully complete r reps (in the range of 2…12) at a lighter weight.

While a person may never attempt that one-rep max movement, the one-rep max weight is canonical, in that it can then be used to compute lighter weights that should be feasible for the subject at a desired number of reps.

Your solution will compute and print:

Example

Consider a subject who can successfully bench 225 pounds 10 times before failure.
Input
  • Successful weight: 225 pounds
  • Successful reps: 10
  • Desired reps: 5
Output
One-rep max: 300
Weight for 5 reps: 255
95% 1 RM: 285
90% 1 RM: 270
85% 1 RM: 255
80% 1 RM: 240
75% 1 RM: 225
70% 1 RM: 210
65% 1 RM: 195
60% 1 RM: 180
55% 1 RM: 165
50% 1 RM: 150

Procedure

When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.3
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 3


Extension 4: The Game of Nim (0 points):

Authors

Overview

Nim is a game of strategy in which two players take turns removing sticks from a common pile. There are many variations of Nim but for the purposes of this assignment, we will stick with a simple and common implementation. On each turn, a player must remove either 1 or 2 sticks from the pile. The goal of the game is to be the player who removes the last stick.

In this assignment, you will design a game in which one human player is competing against a computer. The human player should also be able to decide if he or she wants to play the first or second move.

It's important to note that while there is a winning strategy for this game, you are required only to implement a computer player which employs random moves.
Example game:
User Computer Pile
x x 7
1 x 6
x 2 4
1 x 3
x 1 2
2 x 0
You win! You lose! 0

Implementation

In order to receive credit for this extension, your implementation must:
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.4
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 4


Extension 5: Bank Interest Calculator (0 points):

Authors

Background

In this assignment, you have a balance in your bank account and you randomly either deposit or withdraw money from your account every day for one month (30 days). At the end of the month, you receive interest on your balance.

Procedure

  1. You start with $4000 in your bank account and earn 2% interest at the end of the month.
  2. Each day, you always withdraw or deposit money. Half of the time you withdraw $100.00 and the other half of the time you deposit $200.50.
    How would you use random numbers to determine whether you withdraw or deposit money?
  3. After withdrawing or depositing money, calculate your new balance. Then print the following: Day, Type, Amount, Balance in a cleanly formatted table.
    Since the cent is the lowest denomination in U.S. currency, round your withdrawals, deposits, and balance to the nearest cent.
  4. Finally, after the 30th day, calculate and print the amount of interest you earned and your final balance.
Your final output should look similar to this:
Day	Type		Amount		Balance
1	Deposit 	$200.50		$4200.50
2	Withdraw	$100.00		$4100.50
3	Deposit 	$200.50		$4301.00
4	Deposit 	$200.50		$4501.50
5	Withdraw	$100.00		$4401.50
6	Deposit 	$200.50		$4602.00
7	Withdraw	$100.00		$4502.00
8	Deposit 	$200.50		$4702.50
9	Withdraw	$100.00		$4602.50
10	Withdraw	$100.00		$4502.50
11	Deposit 	$200.50		$4703.00
12	Deposit 	$200.50		$4903.50
13	Deposit 	$200.50		$5104.00
14	Withdraw	$100.00		$5004.00
15	Withdraw	$100.00		$4904.00
16	Withdraw	$100.00		$4804.00
17	Deposit 	$200.50		$5004.50
18	Deposit 	$200.50		$5205.00
19	Deposit 	$200.50		$5405.50
20	Deposit 	$200.50		$5606.00
21	Withdraw	$100.00		$5506.00
22	Deposit 	$200.50		$5706.50
23	Deposit 	$200.50		$5907.00
24	Withdraw	$100.00		$5807.00
25	Deposit 	$200.50		$6007.50
26	Deposit 	$200.50		$6208.00
27	Deposit 	$200.50		$6408.50
28	Withdraw	$100.00		$6308.50
29	Withdraw	$100.00		$6208.50
30	Withdraw	$100.00		$6108.50

Interest earned: 122.17
Money after one month's interest: 6230.67
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.5
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 5


Extension 6: Mario (0 points):

Authors

Mario, created in 1981 by Nintendo, is a classic video game starring the fiction Italian character Mario. In the assignment, loops printing hashtags will be used to build the block mountains as seen in the picture.

  1. Create Mountain Blocks in Mario using loops,

    Ex.

                #
              ##
            ###
          ####
        #####
      ######
    #######

    Hint: You many want to use underscores for spacing the blocks correctly before substituting spaces.

  2. After the program can run 10 rows successfully, create a mario mountain of 50 or more rows.
  3. Instead of increasing to the right, alter the code so that the mountain slopes downwards.
  4. Next, alter the code so that the original mountain is flipped upside down.
  5. And finally upside down the other direction.
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.6
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 6


Extension 7: Gambler's Ruin (0 points):

Authors

Background

In this assignment, you will simulate the Gambler's Ruin problem. The problem is as follows: you are a gambler given some initial amount of money, and each time you gamble, you either win or lose $1 based on your win probability. You have some goal in mind, that once reached, you stop gambling, or if you lose all of your money, you also stop gambling. What is the probability that you lose all of your money?

Procedure

  1. Have your program accept the following inputs:
    startAmount
    The amount of money that you start with
    winChance
    The probability that you win a gamble
    winAmount
    If you reach this amount of money, then you won
    totalPlays
    The number of times you simulate the problem
  2. Next, calculate the chance that you ruin.
    if (lossChance != winChance) Ruin = (lossChance/winChance)startAmount - (lossChance/winChance)winAmount / (1 - (lossChance/winChance)winAmount

    if (lossChance == winChance)
    Ruin = 1 - startAmount / winAmount
  3. Simulate the Gambler's Ruin totalPlays times. For each simulation, continue gambling until you either reach your goal or you ruin. For each simulation, print the simulation number, the number of rounds that simulation played for, and whether you won or lost.
  4. Finally, print the total number of losses, simulations, your actual ruin rate, and your expected ruin rate.

Given this input:
startAmount 12
winChance 0.25
winAmount 15
totalPlays 31
Your final output should look similar to this:
Simulation 1: 22 rounds  	LOSE
Simulation 2: 18 rounds  	LOSE
Simulation 3: 20 rounds  	LOSE
Simulation 4: 42 rounds  	LOSE
Simulation 5: 24 rounds  	LOSE
Simulation 6: 22 rounds  	LOSE
Simulation 7: 24 rounds  	LOSE
Simulation 8: 48 rounds  	LOSE
Simulation 9: 16 rounds  	LOSE
Simulation 10: 26 rounds  	LOSE
Simulation 11: 32 rounds  	LOSE
Simulation 12: 18 rounds  	LOSE
Simulation 13: 22 rounds  	LOSE
Simulation 14: 24 rounds  	LOSE
Simulation 15: 18 rounds  	LOSE
Simulation 16: 18 rounds  	LOSE
Simulation 17: 26 rounds  	LOSE
Simulation 18: 18 rounds  	LOSE
Simulation 19: 34 rounds  	LOSE
Simulation 20: 22 rounds  	LOSE
Simulation 21: 48 rounds  	LOSE
Simulation 22: 26 rounds  	LOSE
Simulation 23: 40 rounds  	LOSE
Simulation 24: 18 rounds  	LOSE
Simulation 25: 20 rounds  	LOSE
Simulation 26: 20 rounds  	LOSE
Simulation 27: 34 rounds  	LOSE
Simulation 28: 22 rounds  	LOSE
Simulation 29: 22 rounds  	LOSE
Simulation 30: 3 rounds  	WIN
Simulation 31: 24 rounds  	LOSE

Losses: 30  Simulations: 31
Actual Ruin Rate: 0.967741935483871  Expected Ruin Rate: 0.9629630300735122
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.7
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 7


Extension 100: Rock-Paper-Scissors (C++) (6 points):

Authors
Issues: Under development. Do not do this yet!

Rock-paper-scissors

The game of Rock-Paper-Scissors (hereafter, RPS) is a two-player game that can be used to avoid boredom and to settle disputes.

In this extension you will rewrite the lab from Module 2 in C++.

Procedure

Update your workspace as usual, and find the Module 2 package in the extensions source folder. Create a new source file rps there, and you are ready to begin your development.

It is suggested that you develop code in small steps, so that you can proceed from confidence to confidence, and not have a big pile of untested code to debug at the end.

To help motivate this approach, the TAs will not help you unless you have shown progress based on these steps. Ask for help as soon as you need it, but please follow the steps below so that you can gain confidence.

The steps you might consider are as follows:

  1. What inputs does your program need? First, get your program to accept those inputs and print them out so you can see they are set properly.
    This means that you should type in the code to prompt the user for the input(s), print out the values of those inputs, and that's all for now. Run your program at this point and make sure it is behaving as you want.

    What inputs do you need? There's no reason to ask for more than is necessary. At a minimum, you have to know how many rounds of RPS to play before printing the resulting statistics.

  2. Next, create a loop that simply iterates the desired number of times.
    Again, run your program. You may want to print something out in your loop so you can verify that the loop works correctly.
  3. You next can make the concept of the random player real. This means declaring a variable name of a suitable type to represent this concept, establishing the variable's initial value.
    What is the concept of the player? There are many details about the player that appear unnecessary: the player's name, address, cell phone number.

    On the other hand, if we are going to play RPS, we need to know what move the player has made. This is the important concept.

    How do we represent the choice of rock, paper, or scissors? This is left up to you, so try for something simple. It may help to recall how Paul Revere was (poetically) told of how the British were coming: one if by land, two if by sea.

    In otherwords, an int encoded the manner of invasion.

    If there were only two choices, why didn't Paul use a boolean? Sadly, Bool was not yet born.
  4. In your loop, you should modify this variable's value to reflect the associated player choosing randomly among rock, paper, and scissors each iteration.
    You've seen how to use the random number generator to pick between two outcomes. Now you must pick between three.
  5. Run your program and verify that the player is choosing randomly.
  6. OK, now for the other player. This player must cycle among rock, paper, and scissors. Let's make this player real by declaring a variable name of a suitable type and establishing its initial value.
    In the interest of consistency and simplicity, you should use the same encoding for this player in terms of what value means rock, what value means paper, what value means scissors.
  7. In your loop, arrange for this player to choose its next move based on its previous move. If the move used to be rock, it's now paper. If the move used to be paper, it's now scissors. If the move was scissors, it's now rock.
  8. Run your program again and make sure the cycling player is behaving properly.
    To verify the cycling player's behavior, you will probably want to print out the values representing that player's move each iteration.

    It won't take many iterations to see if this is working or not: 10 should do.

  9. Each player has made a move; now let's see who won. First, pick a name, type, and initial value for the number of wins a player has. Do the same for the other player.
    Why do we need a variable to keep track of each player's wins? Why not keep track of only one player's wins and assume the other player won the other rounds?
  10. In the loop, determine who won based on the current value of each player's move.
    Use the rules of RPS to adjudicate the winner, and credit the win count properly.
  11. After the loop completes, report the fraction of wins awarded to each of the two players.
  12. Test your code by trying it with just one iteration, two iterations, and three iterations. Make sure it's working before you set it loose.
  13. Run your code several times, each on 1000 iterations.
  14. Based on what you see, did one player tend to win more often than the other?
When you done with this extension, you must be cleared by the TA to receive credit.

This demo box is for extension 2.100
Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others

TA: Password:

End of extension 100