## CSE 131 Module 3: Arrays

Important!

Before beginning any work, do a Team...Pull in your repository.

## Extension 1: Pascal's Triangle (3 points):

Authors
• Robert Sedgewick (book)
Take a look at the Wikipedia page on Pascal's Triangle. We will implement this using a two-dimensional array, so it may be easier to imagine the entries left-justified rather than in triangular form:
```        column
0  1  2  3  4
row
0       1
1       1  1
2       1  2  1
3       1  3  3  1
4       1  4  6  4  1
.
.
.
```
Viewed as a two-dimensional array, the computation is specified as follows, for each entry at row r and column c:
• If c is 0, then the entry is 1.
• If c==r, then the entry is 1.
• If r<0 or c<0 or c>r, then the entry is 0 and is not shown.
• Everywhere else, the entry is computed as the sum of the entries at:
• r-1, c
• r-1, c-1

#### Procedure

1. Open the PascalsTriangle class, found in the arrays package of the extensions folder.
2. Insert code to obtain from the user the value N which is the number of rows you should compute of the triangle.
3. Instantiate the two-dimensional array needed to hold the results.
Java lets you do this as a ragged array, where each row can be of a different length.

You are welcome to instantiate the array that way, but it is simpler and equally acceptable to instantiate the array with the same number of columns in each row. Java syntax for that is much simpler. An example of this appears in SelfAvoidingWalk, found in the book.ch1 package of the coursesupport source folder in your repositories.

4. Compute the triangle as a two-dimensional array and print the results left-justified as shown above.
5. For extra fun, try to print the triangle centered as shown on the Wikipedia page.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.1
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.1
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 2: Birthday Problem (5 points):

#### Procedure

To make things simple, let's assume that all months have 31 days.
1. Open the Birthday class, found in the arrays package of the extensions folder.
2. Insert code to obtain from the user the number of people N that will enter the room.
3. For each person, randomly generate a month and day on which that person was born.
4. Using a two-dimensional array that is indexed by month and by day, keep track of the number of people born on that month and day.
For example, perhaps you randomly decide the person was born in month 4 and day 28.
5. After processing all of the N people, iterate over your array to compute:
• For each month, the fraction (or percentage) of people born in that month.
• The average of the 12 values you computed for the above.
• For each day, the fraction (or percentage) of people born on that day, whether in the same or in a different month.
• The average of the 31 values you computed for the above.
• The fraction (or percentage) of people born on exactly the same day.
Be careful! A 1 entry means just one person was born on that particular day. You are looking for the fraction of people who share a birthday with at least one other person.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.2
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.2
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 3: GC Content (2 points):

Authors
Computer science plays a large role in modern biology. BioJava is a framework for working with biological data. It provides a framework for using sequences and performing common biology functions. In this extension you will be reading in a DNA sequence and computing its GC-Content.

#### Notes

• You can find the Java files for this extension in the extensions source folder.
Locate the following files in the biojavagc package:
• GCContent.java is the file you complete. When you run it, analysis is performed on four genomes and the results are printed as output.
• GCContentTest.java is a unit test for your work. You will receive credit for this extension only if this test passes.
• You can do this extension by following the instructions below. However, you might want to take some time to familiarize yourself with the BioJava website. Of special importance is the BioJava Cookbook. The cookbook has information and examples for performing common tasks. You may also find the BioJava API helpful.

• You will be working with some DNA sequences, represented in the FASTA format, which you can find in the genomes folder of the datafiles folder of your workspace:
• NC_002677.fasta
• mysterya.fasta
• mysteryb.fasta
• mysteryc.fasta
As you might guess from their names, there is an air of mystery surrounding some of these genomes.

Consider a bacterium and a phage that might be hosted by that bacterium. It turns out that the DNA of the host and of the phage often need to be similar in terms of their GC content for the bacterium to play host to the phage:

Most bacteriophage and other bacteria are lower in GC content than Salmonella and its relatives, so invading DNA is an obvious target for H-NS. "It's like a primitive immune system," says Fang. "Reduce their expression, and the foreign genes can be tolerated."
From http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2064161/
In other words, if the GC content in the bacterium and phage is dissimilar, the bacterium may be immune to infection by the phage.

#### Procedure

1. Complete the method percentGC in GCContent.
Note: BioJava already has a function to get the GC-count (number of G and C nucleotides) of a sequence.

Do not use this function.

Instead, devise a way to iterate through the array of characters (representing nucleotides) yourself.

2. Run the unit test GCContentTest and make sure it passes.
Most students' code fails when given a string with no DNA in it whatsover (an empty string or "". Its GC content is 0%.
3. Run GCContent as a Java Application and be prepared to answer questions by the TA at the demo.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.3
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.3
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 4: Reading Frame of a Sequence (10 points):

Authors
Sequences of nucleotides can be read as sequences of nucleotide triplets, known as codons. This means there are 3 different ways of reading a nucleotide sequence. One starts with the first nucleotide in the sequence, one starts with the second, and one starting with the third, as shown below:

Image from https://wikispaces.psu.edu/display/Biol230WFall09/Protein+Translation

• The sequences shown above are RNA. The corresponding DNA sequences would have a T everywhere you see a U.
• Reading frame 1 begins at the first nucleotide. Interpreting AGT using the genetic code, Serine would be generated as the first amino acid of the resulting protein, if this is the proper reading frame.
• However, if the reading frame should start one base later, then the first DNA triple is GTC, which encodes Valine.
• Finally, if the reading frame should start two bases later, then the first DNA triple is TCT, which encodes Serine. While this protein begins with the same amino acid as in reading frame 1, the next amino acid is different, as shown in the above figure.
• There is no other reading frame of interest. If we considered a reading frame that begins at the fourth nucleotide, that is the same as if the frame began at the first nucleotide.

• Important: In the picture above, the reading frames are denoted 1, 2, or 3. Keeping with computer science custom, you must compute these as 0, 1, or 2. The unit test will not work if you fail to follow this convention!
How do we determine which reading frame is correct? Our approach is based on the following observations, which are somewhat simplified to suit our purposes. The interested student is encouraged to take Bio 2960 for a much more thorough and revealing treatment of this material.
• Protein translation is initiated only by a special sequence of 3 nucleotides called a start codon.
• Translation continues until a stop codon is encountered, which is also a specially designated sequence of 3 DNA nucleotides.
Note that it is the first stop codon that ends the translation. While the translated region could contain other start codons, which translate as the amino acid methionine, any stop codon encounered after the start codon ends the translation process.
• If we scan random DNA, we expect each of the four bases (A, T, C, G) to occur with probability 1 in 4.
• If we look for two specific bases, one after the other, in random DNA, scanning pairs a time, we expect the two bases to occur with probability 1 in 16 (1 in 4 times 1 in 4).
• If we scan DNA looking for a specific triplet, moving 3 bases each time we look, we expect that given triplet to occur with probability 1 in 64 (1 in 4 times 1 in 4 times 1 in 4).

For example, we expect the start codon to occur with probability 1 in 64.

• Because there are three possible stop codons, the probability in random DNA that a given triplet is one of the three stop codons is 3 in 64, which is approximately 1 in 20.
• This means that if DNA is random, a protein sequence would be about 20 amino acids in length, once its start codon is found.
• It turns out that proteins are much longer than that, say at least 60 amino acids in length.
• If we start in the wrong reading frame, the DNA should appear to us as random, and we should obtain very short amino acid chains by translation.
Thus, the best reading frame for a sequence of DNA is the offset at which translation would produce the longest chain of amino acids. The DNA sequence that produces that chain begins with the start codon. The start codon and all subsequent codons are interpreted in groups of 3 bases. The sequence contains no stop codon until the end of the translated region. In other words, the translated region may contain multiple start codons in the middle (which are translated as the amino acid methionine), but the region contains no stop codons in the middle.

Your task in this extension is to analyze a sequence of DNA to determine its best reading frame.

#### Notes

• You can find the Java files for this extension in the extensions source folder.
Locate the following files in the biofindframe package:
• FindTheFrame.java is the file you complete.
• FindTheFrameTest.java is a unit test for your work. You will receive credit for this extension if this test (usually) passes.
• You will be working with some DNA sequences, represented in the FASTA format, which you can find in the genomes folder of the datafiles folder of your workspace.

#### Procedure

1. The code given to you prompts the user for a genome DNA file, and then reads that file into a char array using methods provided by bioJava.

If you are uncertain about char arrays, this would be a good time to review the relevant material in your text and in the lecture notes.

2. Your work takes place in the method bestReadingFrame. Open that file now and take a look at what is provided.

There are comments in that file to direct your work, which consists of the steps described below.

You should read these instructions and the comments carefully before you begin. Solutions that fail to follow the instructions will receive no credit!
3. First, define 3 char arrays, one for each of the possible stop codons: ochre, amber, and opal.
4. Next, define a char array named methionine for the start codon.
The most common start codon is Methionine, which is encoded by the DNA sequence AUG. For the purposes of this extension, Methionine is the only start codon you will consider.

5. The rest of the code you write will attempt to read the DNA in each of the possible 3 reading frames. Find the best reading frame and return the index at which that best reading frame occurs. Thus, your method will return a value as follows:
• 0, if reading frame 1 is the right answer. That frame begins at index 0 of the dna array you are given.
• 1, if reading frame 2 is the right answer. That frame begins at index 1 of the dna array you are given.
• 2, if reading frame 3 is the right answer. That frame begins at index 2 of the dna array you are given.
• -1 if no reading frame exists at all
Hint: Scan the DNA one base a time, looking for the longest coding sequence that begins at that base. A coding sequence begins with a start codon and ends at the next stop codon that is found by scanning triplets.

Based on the index at which the longest coding sequence occurs, compute the corresponding reading frame (0, 1, or 2). That is the value you want to return.

When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.4
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.4
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 5: Data Sorting and Analysis (5 points):

Authors
• Brennan Morell
• Jarett Gross
Open sorting class in arrays folder... Do we want all extensions and assignments to have a class and folder already?
A big part of Computer Science revolves around finding ways to sort data to be organized in a useful manner. There are many different algorithms that computer scientists use to sort information. You can learn about a few popular ones below:
For the purposes of this assignment, we will implement our sorting using a naive process of repeatedly selecting the smallest value from a data set of type int[], and swapping it to the front of the collection. A naive process is the solution that seems must obvious but might not be the most efficient solution. The algorithm in this assignment is called Selection Sort .

#### Procedure

1. Open the Sorting class, found in the arrays package of the extensions folder.
2. Prompt the user for the size of the collection
If the user enters a negative number, continue to prompt them with a useful message until they enter a positive number.
3. After collecting the size of the array, prompt the user for integers one at a time, using an array to store the input data.
4. After processing all of the numbers entered, the data will be sorted using the following naive algorithm:
• Create an int sortCount to keep track of the number of times you've scanned the data
• Create an outer loop to limit the number of scans to be equal to the size of the collection (while(sortCount < size))
• Create an inner loop to iterate over the unsorted portion of the array, each time selecting the minimum value (keep track of this value and its index in the array)
The unsorted portion will always be the sub-array with indexes sortCount to size inclusive.
• Swap this minimum value with the value currently at the head of the unsorted portion of the array
• At this point, sortCount should be incremented to reflect the new unsorted portion of the array.
5. After the sorting the data, we will take advantage of its useful organization to compute the following statistics:
Mean
The simple average of the data.
Median
The middle value in the ordered dataset (Note: How does this computation vary for even and odd sized datasets?)
Min
The smallest value in the ordered dataset.
Max
The largest value in the ordered dataset.
Range
The difference between the maximum and minimum values of the data set.
6. Finally, arrange for your output to display the sorted dataset and accompanying statistics in the following manner:
1 2 3 4 5
Mean: 3.0
Median: 3.0
Min: 1
Max: 5
Range: 4
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.5
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.5
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 6: Blackjack! (7 points):

Authors
• Nathan Vogt

#### Introduction

In this assignment, we create the game blackjack, the most widely played casino banking game in the world. In blackjack, each player plays against the dealer, not the other players. The goal of blackjack is to beat the dealer by attaining a score (the sum of the values of your cards) higher than the dealer's score without exceeding 21. Also, many casinos use an 8 deck shoe (meaning eight 52 card decks shuffled together). This practice prevents players from counting cards.

#### Background

• For this implementation, there is a dealer, one human player, and p autonomous players.
• Everyone is initially dealt a two card hand
• All players' cards are visible to all players and the dealer. The dealer, however, has only the dealer's second-dealt card showing at this point.
• The value of a hand is the sum of that hand's cards' values. A card's value is determined as follows:
• If the card's rank is between 2 and 9, then the card's value is its rank. Thus, the 4 of Diamonds is worth 4 points.
• A face card is worth 10 points. Thus, the King of Spades is worth 10 points.
• An ace is worth 11 points. Thus, the Ace of Hearts is worth 11 points.
• After the initial deal is complete, the dealer turns to the first player (which will be you, the human), and asks if you want to hit or stand.
hit
means that you take one more card. The value of that card is then added to the value of your hand.
• If you still have 21 points or fewer, the dealer will continue to ask if you want to hit. The dealer will not move on to another player until you stand or have busted.
• If by hitting you have exceeded 21 points, you have busted and you have lost your bet to the dealer. The dealer moves on to the next player.
stand
means that you do not want any more cards. Your play in this round is complete. The dealer moves on to the next player.
• The dealer then moves to the next player using the above protocol.
• When the last player has finished interacting with the dealer, the dealer then performs the following steps:
• The dealer's hidden card is revealed.
• The dealer continues to hit until the dealer's hand's value is 17 or higher, or the dealer has busted.
• If the dealer busted, then all players who did not previously bust win against the dealer.
• If the dealer did not bust, then all players whose hands have value in excess of the dealer's hand's value win against the dealer.
• All players whose hands have value less than the dealer's hand's value lose to the dealer.
• A player whose hand's value equals the dealer's hand's value has pushed, and has neither won nor lost money.

#### Procedure

1. In the blackjack package of the extensions folder, create a new class BlackJack and make sure it has the public static void main(String[] args) {…} method in it.
2. Prompt the user for how many autonomous players, p, to have at the table, and how many games to play.
3. Create a new array to keep track of everyone's scores, including yourself and the dealer.
4. Construct a loop that will simulate the number of games to be played. Hint: We will have to reset each player's score between games.
5. Next, create a mechanism that simulates the initial deal of two cards to each player. We must simulate drawing a random card. Because the suit of the card is not important for this game, we can think of the deck as only 13 possible cards with equal likelihood of being drawn. Use randomness to draw a card and then calculate its value.
Remember that cards 2-9 will count as their number, 10-King all count as 10, and Aces count as 11.
6. Verify that the array stores each player's score correctly. A player's score must be the sum of both cards drawn.
7. Now we've reached the decision moment in blackjack. Each player decides whether to hit or stand. Start with the human player.
Prompt the human player for their move. In order to make this decision, the human player should be able to see their score and the dealer's face-up card. In addition, after each hit, the human player should see their updated score.
8. Once the human player is finished (either by stand, bust, or blackjack), simulate the autonomous players and then the dealer. The dealer follows the casino rule to hit until his score equals 17 or higher and then stand. Let's assume that the autonomous players follow the same rule. You can copy and paste the same game mechanics you used earlier to draw cards.
9. After the dealer finishes his turn, print out the results of that game. Reminder: if a player busts, then they lose. If the dealer busts, all the players that did not bust win. If neither busts, players with a higher score than the dealer win and players with a lower score lose. If a player's score equals the dealer's (non-bust), then it is a tie, called a push.
• What was the final score of each player and the dealer?
• Which players won?
• Which players busted?
• Did any players get a blackjack?
• Did any players push?
10. After all the games have ended, print out the percentage of the games that the human won.
11. Here is a sample solution. In this implementation, player 0 is the dealer, player 1 is the human player, and players 2 and 3 are autonomous players. Notice that the human player got three blackjacks out of four games! This is very rare.
```You chose to play 4 games
There are 2 autonomous players playing.

Game 1
The dealer's face-up card has the value of 10
The players' scores are:
21 18 12
The Dealer's face-up card has the value of 10. And your current count is 21
You chose to stand!

Player 0 got 20
Player 1 got Blackjack! (21)
Player 1 beats the dealer!
Player 2 got 18
Player 3 got 20
Player 3 pushed with 20

Game 2
The dealer's face-up card has the value of 8
The players' scores are:
15 17 16
The Dealer's face-up card has the value of 8. And your current count is 15
You hit!

Player 0 got 19
Player 1 Busts! 26
Player 2 got 17
Player 3 Busts! 23

Game 3
The dealer's face-up card has the value of 9
The players' scores are:
15 14 15
The Dealer's face-up card has the value of 9. And your current count is 15
You hit!
The Dealer's face-up card has the value of 9. And your current count is 21
Would you like to hit?
You chose to stand!

Player 0 got 17
Player 1 got Blackjack! (21)
Player 1 beats the dealer!
Player 2 Busts! 24
Player 3 Busts! 22

Game 4
The dealer's face-up card has the value of 11
The players' scores are:
14 19 7
The Dealer's face-up card has the value of 11. And your current count is 14
You hit!
The Dealer's face-up card has the value of 11. And your current count is 21
Would you like to hit?
You chose to stand!

Player 0 got Blackjack! (21)
Player 1 got Blackjack! (21)
Player 1 pushed with 21
Player 2 got 19
Player 3 got 17

The fraction of human wins was 0.5
```
• Create a different prescribed formula for the autonomous players, perhaps involving an element of randomness.
• Create a betting system (perhaps similar to gambler's ruin) where you can win or lose money each game. Getting a blackjack wins you 150% of your bet!
• Alter the game mechanics so that aces can be counted as 1 or 11.
• Implement another human decision such as split or double down.
• Instead of copy and pasting the game dynamics, create a method for the game mechanics. (This task would satisfy extension 5.1 Methodize It)
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.6
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.6
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 7: Minesweeper (8 points):

Authors
• Ron Cytron

#### Workspace Update

• Update by right-clicking (control-click on Mac) the main project in the package explorer, drag down to Team... and click Update.
• You should see a minesweeper package in the extensions source folder.

Note and warning: It is very easy to find a solution to this problem in the Internet. This course does not have as one of its goals making you an expert on finding solutions on the Internet. The goal is to teach you the basic concepts of computer science and programming.

You are not allowed to copy any code for your solution to this problem! The solution takes some 30 lines of code, so we are not asking you to write an air-traffic controller.

However, even these 30 lines may be difficult for you to write at first. So, get help from a TA or the professor, come to office and TA hours, but do this work on your own so that you learn the material.

Be assured that you will not do well on the exam if you do not understand this material.

### MineSweeper

• This assignment is described in the book, exercise 1.4.30, on page 118. Begin by reading that exercise to make sure you understand the task assigned to you for this lab.
You may find the exercise online here, as Creative Exercise 30.
• The file you will modify for this assignment is MineSweeper.java. It is already in the respository.
• That file already prompts for the number of columns, rows, and the probability of a bomb.
Do not change that part of the file. The file is very clear about where you are to insert your code.
• Create the output as prescribed in the book's exercise.
You must use the * and . characters as shown in the book. Otherwise, the visual version of this game (described below) will not work correctly.

Your output must include both the left and right parts of each line as described below.

The example given in the book is reproduced below:
```
* * . . .    * * 1 0 0
. . . . .    3 3 2 0 0
. * . . .    1 * 1 0 0

```
You must produce output that matches the form you see above:
• Each line's left part displays the locations of the bombs (denoted by *) and the non-bombs (denoted by .).
• Each line's right part reports a * where there is a bomb and the count of bombs that border that cell where there is not a bomb.

For example:

• The leftmost entry of the second row has no bomb. In the left part of the second row, a dot is shown. Its corresponding entry in the right part of the second row shows the number 3, which is the sum of the bombs found on that cell's eight neighbors. Becasue this cell is left-most in the grid, some of its neighbors do not exist, but they are thus assumed to have no bombs.
• The mine field's central entry also has no bomb and shows a 2 in the right part of the output. Those two bombs can be found in the upper-left and lower-left cells with respect to that center cell's eight neighbors.
The book provides a nice hint about an implementation that eliminates special cases around the edges of the field.
• Run MineSweeper as a Java Application and be sure your results look correct before you demo.
Test on very small (say, 3x2) mine fields at first. Enlarge the fields and test again, making certain the output is correct.

Are you sure your output is correct?

Make sure it includes both the left and right parts of each line as described above.

• When your program is complete (or, actualy, even prior to that), you can run a visual version of your game by running Game as a Java Application.
• Our Game program runs your MineSweeper code, but hijacks the output for its own use.
The output you produce is therefore the interface between:
• Your code that computes the maze, in particular, the location of bombs, and
• The class-provided code that runs the visual version of the game.
That class-provided code has tried to be tolerant of the output you might produce. If it is not working for you, let us know.
• It builds a visual board based on your output.
• It also shows the output you produced in the console window.
To play the visual version of the game:
• Right-click on squares where you think there is a bomb.
• Left-click on a square that has no bomb to show you the count of the number of bombs that border that square.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.7
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.7
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 8: Linear Regression (4 points):

Authors
• Brandon Mendez

#### Overview

Machine learning is an area of study in computer science that falls within the larger area of study known as artificial intelligence. Here, we are trying to teach a computer to reason about a problem based on data we provide.

One such simple task to consider is learning a geometric line, as characterized by its slope and y-intercept. Where two properties are related linearly, the line that characterizes their relationship can be used to predict the relationship between values that have not yet been seen. How many points must be provided to learn the implied line? We need only see two points that differ in their first coordinate to learn a line.

In the real world, two properties are sometimes approximately but not exactly linear. In this assignment we consider the square footage of a house (one parameter) and that house's cost (the other parameter). If we assume that these two properties are linearly related, then we should be able to

• learn the line that predicts their relationship by analyzing some actual examples of sales prices for houses and the area (in square feet) of those houses, and
• predict the sales price of any house using that learned line.

The simple example of machine learning that we study here is linear regression. This technique allows us to take many data points with two known variables, learn the line that best fits their relationship, and then predict the value of one variable when given the other. In this assignment you will learn a line given the actual selling prices and square footages of thousands of houses in the Broward County, Florida area. When your line is computed, you can then predict the price of a house of any square footage.

#### Procedure

1. In the extensions folder, find the regression package. You will write your code in the LinearRegression class.
In this extension, you'll be working with slope and intercept, class variables that can be accessed from any method in the class. While we included these to make testing your code easier, they serve also as an introduction to instance variables, which you learn later in this course. The slope and intercept variables are
public
meaning they can be accessed outside of the class declaring them, and
static
a word which here means that they are available to all static methods in the class. Moreover, they will retain their values between calls to such methods. Feel free to ask a TA for more details if anything remains unclear.
2. Finish the code for the learn() method.
• This will require you to implement the simple linear regression formula included below.
• More information on how the formula should be used can be found in this Khan Academy video.
• You'll find the method StdIn.readDoubles() useful here to take in the data we provide for you in datafiles/housing/pricesarea.csv.
• Note that you can only read from StdIn once in your entire program. If you want to access the values you read in more than one place, you will have to find a way to save and pass the values to wherever you need them.

• In this assignment, x would be the square footage of a house, and y would be its selling price.
• The notation x means the average of all of the x values.
• The notation xy means the average of the products formed by multiplying each point's x and y values.
3. Once you finish implementing the formula and getting a reasonable regression line equation, make sure you pass the testSlopeIntercept JUnit test before moving on.
4. Finish the code for the predictPrice() method. This method should allow a user to pass in a square footage, and return an estimated price for a house of that size. The code for this method is very short; think of how the variables you just solved for relate to the price and area of a home. Make sure you pass the testPredictions JUnit test.
5. When you finish, you can try using the RegressionGrapher class to see a graph of the data and your line. This is provided for you.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.8
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.8
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 9: k Nearest Neighbors (4 points):

Authors
• Brandon Mendez

#### Overview

This assignment incorporates principles of Machine learning, which is an area of study in computer science that falls within the larger area of study known as artificial intelligence. Here, we are trying to teach a computer to reason about a problem based on data we provide.

One such simple task to consider is learning the value of a function at some position in two-dimensional (say, x and y) space. The value of this function may not have an obvious relationship with its x or y coordinates. Moreover, we can't use linear regression to represent the function by a line, because the function's values depend on two inputs. We could try to generalize linear regression to use a plane to represent this function. Unfortunately, the problem we consider here is not amenable to accurate representation using a plane, but the data does possess one feature that suggests using a particular approach to approximate the function's values.

The data we consider here is literally comprised of neighborhoods, such that points within a physical neighborhoods behave similarly. For the sake of this problem, we do not know the physical boundaries of any neighborhood. However, if we can impose neighborhoods of our own choosing over the data and use those implied neighborhoods to approximate the value of point within that neighborhood.

In particular, we can approximate a position's value using this sample data by taking the k nearest points (neighbors) to the position of interest and averaging the neighbors' values, where k is an integer greater than 0.

For any chosen value of k and any position of interest, that position's k nearest neighbors occur within some radius from the position. The value of k thus determines the circular neighborhood imposed at the position of interest, with the assumption that points within that circular area behave similarly. Where known data points are dense, the radius will be smaller; where known data points are sparse, the radius is adaptively larger, so that in any computation, k points participate in determining the value at a position of interest.

But what exactly should k be? How many points must be provided to learn the implied value? As an example, consider computing some aspect of the weather (temperature, wind speed, etc.) at a point of interest based on averaging the aspect's value at the k neighbors nearest to the point of interest. If k is too large, then we will be computing an average value that holds over a large area, but probably does not hold at the specific point of interest. If k is too small, we may not have enough data to compute the point's value accurately.

Thus, the choice of k is itself of interest in solving this problem.

In this assignment we consider the location of a house (its position in space) and that house's cost (its value). If we assume that these two properties are related, then we should be able to predict the sales price of a house in any location by analyzing some actual examples of sales prices for houses and the location (latitude and longitude) of those houses.

The simple example of machine learning that we study here is called k Nearest Neighbors. This technique allows us to take many data points with two known variables, plot them, and then predict the value of one variable when given the other. In this assignment you will approximate the values of hypothetical homes given the actual selling prices and locations of thousands of houses in the Broward County, Florida area. When your algorithm reads the given data, you can predict the price of a house at any location.

#### Procedure

1. In the extensions folder, find the neighbors package. You will write your code in the kNearestNeighbors class.
2. Finish the code for the predictPrice() method.
• This method takes in the x and y positions of a hypothetical home, along with an array containing the price, x, and y locations of actual homes. It also takes in a value for k so that we can test your code in different situations. Your method needs to be able to:
• Calculate the distance of the house in question to each of the actual homes.
• Use those distances to find the k nearest homes to the given house.
• Average the values of those k nearest homes to predict the price of the house we are looking for.
3. Once you finish implementing the algorithm, you can run NeighborhoodGraph to see it in action. This draws a real map of Broward County, with the housing data points on top of it. You can see that as houses get more expensive they show up as darker red, and as they get more affordable they show as a lighter yellow. If you click on the map, your prediction will show up in the Eclipse console. Make sure each area on the map corresponds to the appropriate price range relative to the other areas. If you are getting inconsistent results, make sure you are calculating distance properly, and storing the prices of the closest houses properly as well.
4. Make sure that your code passes the testPrediction Unit test in the TestNeighbors class.
When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.9
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.9
• The student has committed and pushed the work, and verified that it appears at bitbucket.

## Extension 10: Apartment Hunting (4 points):

Authors
• Dotun Taiwo
Adaptation of the famous Secretary Problem

#### The Problem

Imagine you want to choose the best apartment out of n apartments each with a rating from 0 to 1. The apartment hunting is done in a random order. When you are surveying an apartment, you can evaluate that apartment based on the ones you have seen so far, but you are oblivious to the quality of apartments you have not seen. If the decision to sign a lease for an apartment can be made at the end, this could be solved by simply tracking the maximum rating (and which apartment complex achieved it) and selecting the overall maximum. The difficulty is that the decision must be made immediately due to the high demand of apartments in the market. Once you reject an apartment choice it can not be renounced because it is likely that someone else bought it. The question is finding an optimal strategy that maximizes the probability of the best apartment being chosen.

Such a strategy is the stopping rule. For example, consider the first k of n apartments, retaining the highest rating, but rejecting all. Continue from k+1 to n and select the first apartment who has a rating equal to or greater than the one computed for the first k, choosing the last apartment if it comes to it.

In this extension, your job is to experiment and find the value of k that chooses the best apartment the most times.

#### Procedure

1. Create a class in the apartment package of the extensions folder
2. Prompt the user for N apartment choices
3. Create an array of N random doubles each ranging from 0 to 1 (utilize Math.random).
4. Implement the stopping rule:
• Iterate over the first k values of the array preserving the max then record the next highest number from the k+1 to N portion.
• Record the maximum of the entire array.
• The best secretary is picked when the max calculated using the stopping rule equals the overall max
5. To experiment effectively, you should run multiple simulations for each value of k to see how many times the best aparment was picked.
6. Calculate the optimal point-the k where the best apartment was picked the most times
7. After the experimentation, print:
• The calculated optimal point for the given number of apartments
• The percentage of times the best apartment was picked
This value per the optimal stopping rule should be approximately 37%. You may have to adjust the number of simulations to produce a more accurate output.
8. Demo your results to a TA
9. When you are done with this extension, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 3.10
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity

 You must select one of the options below The work submitted here was performed in accordance with this course's policy on collaboration. On your honor, you have neither given nor received any unauthorized aid on this assignment. However, the following TAs, students, or professors were supportive in completing this assignment. Their help was also in accordance with course policies. Thanks to (leave blank if appropriate): In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment. You would like to be contacted by an instructor to facilitate staying on track in this course. Comments about this: You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment. You would like to be contacted by an intructor to faciliate staying on track in this course. Comments about this:

TAs double check!
• This demo box is for extension 3.10
• The student has committed and pushed the work, and verified that it appears at bitbucket.