CSE 131 Module 3: Arrays

Extensions

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

Authors
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:

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 done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 1


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:
When you done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 2


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


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 done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 3


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

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.
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

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.

    More information about start and stop codons can be found here.

  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:
    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 done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 4


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

Authors
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:
  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 done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 5


Extension 6: Blackjack! (7 points):

Authors

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

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.
  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
    
  12. Optional tasks:
When you done with this extension, you must be cleared by the TA to receive credit.

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:


TA: Password:

End of extension 6


Extension 7: Minesweeper (8 points):

Authors

Workspace Update

  • Update your eclipse workspace:

    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

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

    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:


    TA: Password:

    End of extension 7