APCS Problem Set 12: Arrays and ArrayLists

Michael Ferraro
mferraro@balstaff.org
Balboa High School
1 February 2016

1 Introduction

Many times so far in this course, ArrayList objects have been used as a means of holding unnamed (i.e., anonymous) objects. Sometimes the objects were BankAccounts and Strings. Other times, the objects were wrappers for primitives, like when we'd store $\fbox{{\tt new Integer( -3 )}}$ instead of the raw $\fbox{{\tt int -3}}$ . (This is because primitives aren't objects, and ArrayLists only hold objects.) And since the ArrayList class implements the List interface, it has lots of convenient methods for our use: size(), add(), set(), etc.

Unlike ArrayLists, Java arrays (which aren't really objects, though they make a length ``instance variable'' avaiable) can hold both primitives and objects. They can hold only one kind of primitive/object at a time, e.g., a set of ints or a set of Strings. One key difference: The capacity of an array is set at initialization unlike its more dynamic cousin, ArrayList, which can always be increased or decreased in size (without programmer intervention).

Arrays is a topic with which you should become very familiar for a few reasons:

they have many practical uses in real-world programming, and
the AP exam may include quite a few problems involving the analysis of algorithms involving arrays!

1.1 Objectives

By completing this problem set, students will learn to...

declare and initialize arrays and ArrayLists;
get and set elements in arrays;
effectively resize arrays;
get, set, and remove elements from ArrayLists; and
create and use two-dimensional arrays.

1.2 Due Date

This problem set is due before 5th Period on 17 February 2016.

2 Array Basics

When reading Litvin §9.1, make sure you know the vocabulary words relating to the individual items stored within an array and the location of items within an array.

2.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.1

3 One-Dimensional Arrays

3.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.2

3.2 Checking for Understanding

For the questions 1

3, examine the provided Java source below.

    public class CreditCardExpenses {
    
        public static void main(String[] args) {
    
            // track expenses
            double[] expenses = new double[3];
    
            expenses[0] = 2.38;
            expenses[1] = 15.03;
            expenses[2] = 9.92;
    
            for ( int i = 0 ; i < _________________________ ; i++ ) {
                System.out.println( expenses[i] );
            }
        }
    }

Provide the value that goes in the blank above so that the for() loop processes every value stored in the array, making sure that you write an expression that will work regardless of the array's current size (i.e., your answer must not require any modification if the size of double[] expenses were to change).
#INPUT:expenses_length#
What exception is generated if the numeric constant `4' is used in the blank above?
#INPUT:ArrayIndexOutOfBounds#
If the three lines in class CreditCardExpenses responsible for setting values in the array were commented out, what value would each location in the array hold?
#INPUT:unitialized_array_slots#
True/False: Once an array is declared and initialized, its size may never change.
#INPUT:may_array_size_change#

Consider this array example, in which instances of an object class are held:

        String[] words = new String[3];
        
        words[0] = "Hello there!";
        words[1] = "My name is Melvin.";
        // words[2] is not set here...
        
        System.out.println( words[0] + "\n" + words[1] );
        System.out.println( words[2] );

If an array holds objects, what is the default value held at any index that isn't specifically initialized?
#INPUT:default_slot_value_for_obj#

According to Litvin, arrays of objects hold what, specifically?
#INPUT:arrays_hold_references#

Consider the snippet below:

        StringBuffer[] funArr = new StringBuffer[3];
        // REMEMBER:  What makes Strings different from StringBuffers???

        funArr[0] = new StringBuffer("Ping...");
        funArr[1] = funArr[0];
        funArr[2] = funArr[1];

        funArr[0].append("pong!");

        for ( int i = 0 ; i < funArr.length ; i++ ) {
                System.out.println( funArr[i] );
        }

(a): What is the printed output of the statements above?
#INPUT:ping-pong#
(b): Explain why the final contents of funArr[2] have changed. (Drawing a diagram showing references to the StringBuffer object(s) may help you.)
#INPUT:sb_properties_and_multirefs#

As you read in Litvin §9.2, you can declare and initialize an array in one step, which ``autosizes'' the array, as in the example below.
```
        double[] bills = { 3.93, 18.01, 5, 1.30 };
        System.out.println( bills.length );
```
(a)

What is the printed output of the above example?
#INPUT:print_arr_length#

(b)

Create an array of Strings that will hold the following literal Strings using the one-step declare/initialize shortcut shown for double[] bills:
    "apples"
    "bananas"
    "cherries"
#INPUT:declare_init_shortcut#

4 `FortuneTeller` Lab

An earlier form of this lab (from a prior edition of the textbook) presented FortuneTeller as a Java applet, which is a Java program that runs inside a web page. For a web browser to download and run a Java applet, it would rely on a Java plugin in the browser. In 2016, Oracle decided to stop supporting their Java plugin, likely due to security risks associated with Java plugins and the presence of more modern web technologies (e.g., HTML5 + Javascript).

The FortuneTeller application you'll complete is a standard Java GUI application.

4.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.3

4.2 Finishing the `FortuneTeller` Class

Create a new project in workspace3 called PS12-FortuneTeller.
Download FortuneTeller.java from
http://feromax.com/apcs/problemsets/PS12/downloads/FortuneTeller/. (Ignore the Ding.wav file unless you'll be enabling sound support, which requires an additional JAR file from the Litvin student files pack.)
Finish the FortuneTeller class as per the instructions in Litvin §9.3.
#INPUT:FortuneTellerSignoff#

5 Book Questions #1

Litvin Ch. 9, #1a.
#INPUT:ch9_1#
Litvin Ch. 9, #2.

(a)

#INPUT:ch9_2a#
If false, reason: #INPUT:ch9_2a_reason#

(b)

#INPUT:ch9_2b#
If false, reason: #INPUT:ch9_2b_reason#

(c)

#INPUT:ch9_2c#
If false, reason: #INPUT:ch9_2c_reason#

(d)

#INPUT:ch9_2d#
If false, reason: #INPUT:ch9_2d_reason#
Litvin Ch. 9, #3.
#INPUT:ch9_3#
Litvin Ch. 9, #6. #INPUT:ch9_6#
Litvin Ch. 9, #10. Hint: You should figure out how to set the size of your return array first.

(a)

Create project PS12-AutoGraded in workspace3. Remember to be mindful of spelling and capitalization, especially when an autograder is involved!

(b)

Import PS12Auto.java from http://feromax.com/apcs/problemsets/PS12/downloads/.

(c)

From school, use github-push.sh to push project PS12-AutoGraded to GitHub.

(d)

Include your solution to the problem in PS12Auto.java. Make sure you adequately test it!

(e)

Commit your changes to GitHub using github-push.sh while at school (or via the web interface at https://github.com if not at school).

6 SCRABBLE $^{\textregistered }$

You are to write a class containing a method called computeScore(), as described in Litvin Ch. 9, #12.

Carefully read the question in the textbook. Note the provided hint.
To help you make better sense of the given hint, you can use a String like
```
     String alphabet = "ABCDEFG";
```
together with String.indexOf() to determine the location of the point value for each letter in an array of ints. (The array of ints would hold the point values shown in the book.)
In workspace3, create a new project called PS12-Scrabble.
Create class Scrabble with:
- public static int computeScore(String word), as per Litvin
- a suitable main() that will ask computeScore() to score each of the following words and show the words + scores on the screen.
  
  java
  
  Balboa¹
  
  senioritis
  
  pantomime
#INPUT:paperform_scrabble#

7 `ArrayList`s

7.1 Basics

7.1.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §§11.1-11.2

7.1.2 Motivating the Need for `ArrayList`s

Revisiting double[] bills: There is now a new bill for $8.39. Write code that would follow the array declaration/initialization below that would (a) effectively resize the array to accommodate the additional bill and (b) then include $8.39 as its final element.
```
        double[] bills = { 3.93, 18.01, 5, 1.30 };
        System.out.println( bills.length );
```
#INPUT:revisiting_double_bills#
Comparing/contrasting ArrayList with arrays:

(a)

What is one major advantage of ArrayLists?
#INPUT:advantage_of_arraylist#

(b)

According to the reading, what's one limitation of ArrayList (and ohter Java collections) when compared with a standard array?
#INPUT:shortcoming_of_arraylist#

7.2 `ArrayList` Methods

7.2.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §11.3

7.2.2 Old Friends

Below are ArrayList methods with which you should already be familiar. If you have questions about how any of these methods works, ask!

Method

boolean isEmpty()

int size()

void add(E obj)

E get(int idx)

Note that for void add(E obj), the method takes an object of type E, where E could be String or Integer, for example. Similarly, E get(int idx) returns an object of type E.

7.2.3 Innocuous New Friends

Make sure you read over the provided comments near each of these methods in Litvin Figure 11-2 and/or check the Java API to see what each one does before moving on to the next section.

Method

E set(i, E obj)

boolean contains(E obj)

int indexOf(E obj)

String toString()

7.2.4 Methods that Change Indices

These methods --

Method

void add(int idx, E obj)

E remove(int idx)

-- potentially change indices of the elements of an ArrayList. As a programmer, you need to exercise caution when using these methods, or else there may be runtime exceptions. Make sure you understand how these methods work before moving on to the next section.

7.3 Achtung! (German for ``watch out!'')

7.3.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §11.5

7.3.2 An Alternative Approach to Array Walking

There were a few potential bugs described in Litvin §11.5. Make sure you know the problem with each situation and ask questions if you're confused.

For the first two potential bugs, both involving the use of remove(), Litvin provides a solution. Analyze the solution on p326 and then compare to the one that follows.

    import java.util.ArrayList;
    
    public class PitfallA {
    
        public static void main(String[] args) {
            ArrayList<String> words = new ArrayList<String>();
            words.add("I"); words.add("like"); words.add("like");
            words.add("LOVE"); words.add("problem"); words.add("sets");
    
    
            for ( int i = words.size() - 1 ; i >= 0 ; i-- ) {
                if ( words.get(i).equals("like") ) {
                    words.remove(i);
                }
            }
            System.out.println( words );
        }
    }

How does the solution presented here sidestep (or avoid) the potential bug of missing a duplicate consecutive element (like)? (If uncertain, draw a diagram of the ArrayList and trace the execution of the for() loop to see how the ArrayList is modified.)
#INPUT:backward_traversal#

The approach provided below also sidesteps the potential bugs.

    import java.util.ArrayList;
    
    public class PitfallB {
    
        public static void main(String[] args) {
            ArrayList<String> words = new ArrayList<String>();
            words.add("I"); words.add("like"); words.add("like"); 
            words.add("LOVE"); words.add("problem"); words.add("sets");
    
            while ( words.indexOf("like") != -1 ) {
                words.remove( words.indexOf("like") );
            }
    
            System.out.println( words );
        }
    }

Discuss how this approach prevents IndexOutOfBounds exceptions.
#INPUT:indexof_approach#

8 Array Walks: `for()` vs. `for-each()`

8.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.6

8.2 Two Ways of Getting the Job Done

As explained in Litvin §9.6, for() and for-each() loops both have the ability to iterate through the elements of arrays and ArrayLists. Consider int[] numbers below.

        int[] numbers = { -23, 18, -1, 42, 918, 0 };

Using a standard for() loop, iterate through int[] numbers' elements -- from the 0 $^{\mbox{th}}$ to the last -- printing each element. Hint: Start with
```
     for( int i = 0 ; ... ; ... )
```
#INPUT:traditional_for_walk#
Using a for-each() loop, iterate through int[] numbers' elements -- from the 0 $^{\mbox{th}}$ to the last -- printing each element. Hint: Start with
```
     for( int val : ... )
```
#INPUT:for_each_walk#

8.3 All `for()`s Are Not Created Equal!

If coded correctly, the for-each() version in the last section was faster to write because, as the programmer, you didn't have to consider the size of int[] numbers, nor did you need to work with the element indices. For many instances where an array walk is needed, this alternative to the traditional for() (or even while()) loop is preferred. Now consider a different case:

        int[] numbers = { -23, 18, -1, 42, 918, 0 };
    
        //each negative value must be replaced with zero
        for ( int i = 0 ; i < numbers.length ; i++ ) {
            if ( numbers[i] < 0 ) { 
                numbers[i] = 0; 
            }
        }

Why is it not possible to replace this for() loop with an equivalent for-each() loop? (Think about what for-each() loops cannot do.)²
#INPUT:for_each_doesnt_give_indices#

When arrays (or ArrayLists) contain objects, a for-each() loop can be used to change the actual objects, as in this snippet:

        //refer to http://feromax.com/apcs/problemsets/PS09/downloads/Fraction.java
        //
        //     *** FOR THIS EXAMPLE, Fraction's "num" FIELD ***
        //     ***           HAS BEEN MADE public           ***
    
        Fraction[] frxns = new Fraction[3];
        frxns[0] = new Fraction(1,3); // 1/3
        frxns[1] = new Fraction(2,8); // reduces to 1/4
        frxns[2] = new Fraction(7);   // 7/1
    
        for ( Fraction f : frxns ) {
            if ( f.getValue() == .25 ) {
                f.num = 4;
            }
        }

How is the value of frxns[1] changed in this case? Connect your response to the answer you gave in #1.
#INPUT:dually_referenced#

Consider this last example:

        String[] triangles = { "ABC", "DEF", "GHI", "JKL" };
    
        for ( String s : triangles ) {
            if ( s.equals("GHI") ) {
                s = "ghi";
            }
         }

Why is the final value of triangles[2] ``GHI'' and not ``ghi''?
#INPUT:ending_val_of_triangles_2#

9 Book Questions #2

Litvin Ch. 11, #1:
(a) #INPUT:ch11_1a#
(b) #INPUT:ch11_1b#
(c) #INPUT:ch11_1c#
(d) #INPUT:ch11_1d#
(e) #INPUT:ch11_1e#
Litvin Ch. 11, #5.

(a)

Implement your solution in the appropriate place in PS12Auto.java.

(b)

Push your changes to GitHub via github-push.sh (or the web interface at https://github.com if not at school).
Litvin Ch. 11, #6.³

(a)

Implement your solution in the appropriate place in PS12Auto.java.

(b)

Push your changes to GitHub via github-push.sh (or the web interface at https://github.com if not at school).
Litvin Ch. 11, #8.

(a)

Below, show the code you wrote that attempts to create an ArrayListObject with an element that is a reference to the ArrayListObject itself.
#INPUT:ch11_8a#

(b)

Try compiling your answer to the last question. Does it compile successfully? If not, what error(s) do you get?
#INPUT:ch11_8b#

10 Array Removals and Insertions

10.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.7

10.2 Important Difference Between Arrays and `ArrayList`s

ArrayLists manage their capacities automatically. Additionally, they automatically handle reindexing elements when insert and remove operations, via add(pos, E) and remove(pos), respectively, are performed. For example, consider the following:

        ArrayList<Integer> listOfInts = new ArrayList<Integer>();
        listOfInts.add( new Integer(4) );
        listOfInts.add( new Integer(5) );

The current state of listOfInts is

Running this statement -- listOfInts.add( 1, new Integer(1) ); -- results in this new state:

In other words, the value ``5'' is reindexed when the insert is performed, from position 1 to position 2, to make room for the value ``1''.

None of that happens in arrays! Using arrays is a very manual proposition.

10.3 Prepare Eclipse

For the problems in this section, create a project called PS12-ArrayOps in workspace3.

10.4 Element Insertion

Easier Problem: Import EasyInsert.java from http://feromax.com/apcs/problemsets/PS12/downloads/ArrayOps/ into project PS12-ArrayOps. Modify the code to insert the value ``8'' so that the provided array's elements remain in increasing order. You may take advantage of the fact you know the value and index of each element.

#INPUT:paperform_eltinsert1#
Harder Problem: You have an array of ints for which you do not know the contained values. Assume that the array is at full capacity (as in the last problem) and insert the value ``8'' in a location so as to maintain the array's ascending order. Import TrickyInsert.java from the same URL as the last problem. Note: Since random values are used to initialize the array each time, you might be required to run the class a few times when demonstrating it to make sure you don't have any subtle bugs!

#INPUT:paperform_eltinsert2#

10.5 Element Removal

Write code to follow the given array declaration/initialization that removes the element at index 2, causing all elements afterward to shift left by one position. Your code need not use a loop; issuing a few statments, to be run only once, is sufficient. You should assume that it is correct behavior to have the value 0.0 inserted in a newly emptied slot.

        double[] dblArr = { 1.1, -3.6, 2.832, 0.998, 2.0 };

#INPUT:elt_removal#

11 Book Questions #3

Litvin Ch. 9, #22.
#INPUT:ch9_22#
Litvin Ch. 9, #23:
- Draw a few diagrams of arrays of doubles and see if there's a pattern you can take advantage of when the number sent to isMedian() really is the median.
- You cannot assume anything about the order of the array that is sent!
- You must demonstrate the method running for these values:
  
  $\star$
  
  { 1.0, 2.0, 3.0, 4.0, 5.0 }; is 3.0 the median?
  
  $\star$
  
  { 3.4, -2.9, 0.1, 9.3, 5.8 }; is 4.8 the median?
  
  $\star$
  
  { 3.4, -2.9, 0.1, 9.3, 5.8 }; is 3.4 the median?
#INPUT:paperform_ch9_23#

12 2D Arrays

A two-dimensional array is a useful data structure for maintaining multiple pieces of information about something. Whereas a 1D array can store a single student's test scores, a 2D array can store her scores and those of the rest of the class. Or consider an image on your screen: Each pixel has a location (measured along x and y axes) and a color value. A 2D array can be used to maintain this information, as you will soon see.

12.1 Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.4

12.2 Manipulating the Pixels of an Image

In an upcoming College Board lab, you'll have the opportunity to manipulate the pixels of an image, with the pixel data being stored in a 2D array.

13 `Chomp` Lab

13.1 Required Reading

The reading in Litvin §9.5 is dense, but make sure you can extract enough information to answer the following:

What is CharMatrix? For what reason was this class made separate from ChompGame?
What's the composition of the Location class?
Why do both ComputerPlayer and HumanPlayer implement the same interface, Player?

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.5

13.2 Previewing the Final Product

To see the way the app should work when finished, download Chomp.jar and chomp.wav from http://feromax.com/apcs/problemsets/PS12/downloads/Chomp/, saving them to the same directory (e.g., /tmp or Desktop). Then run the JAR file using java -jar Chomp.jar.

13.3 Preparing Eclipse for `Chomp`

Create a new project in workspace3 called PS12-Chomp.
Download ChompSources.jar from http://feromax.com/apcs/problemsets/PS12/downloads/Chomp/ and import into your project folder -- not src. Importing into PS12-Chomp/ instead of PS12-Chomp/src will ensure that the included sound file will be in the project folder, while the source files will reside in src.

13.4 Complete `CharMatrix.java`

Your job is to finish implementing CharMatrix.java. You might notice that the code you need to write for certain pairs of methods will be almost identical; see if there's a way to take advantage of this fact!

#INPUT:paperform_charmatrix#

14 Wrap-Up

To reinforce vocabulary and refresh your understanding of key concepts, read the Ch. 9 and Ch. 11 summary sections.

Required Reading

$\rightarrow$ Litvin & Litvin, Java Methods A & AB: §9.9 and §11.7

15 Book Questions #4

Litvin Ch. 9, #14.

(a)

Implement your solution in the appropriate place in PS12Auto.java.

(b)

Push your changes to GitHub via github-push.sh (or the web interface at https://github.com if not at school).
Litvin Ch. 9, #15: Download Checkerboard.java from http://feromax.com/apcs/problemsets/PS12/downloads/ and import into a new project, PS12-Checkerboard. Next, implement the fillCheckerboard() method. Here are a few important notes to help you:
- The data structure passed to fillCheckerboard() is a two-dimensional array of Color objects. Place, in each slot, a Color object. If you check the Java API, the Color class defines constructors that take numerical values representing amounts of red, green, and blue to mix to achieve a particular color. For common Colors, though, final static (constant) Color objects are predefined. So you need only have each slot in the 2D array point to one of these final static fields.
- The method needs to determine the dimensions of the incoming two-dimensional array so that you can write nested for() loops that iterate the correct number of times. Assume that you do not know the size of the two-dimensional array that is sent to the method!
#INPUT:paperform_ch9_15#

Footnotes

... Balboa ¹: In the real SCRABBLE, proper nouns aren't permitted! See http://en.wikipedia.org/wiki/Scrabble#Acceptable_words.
... do.)²: NB1: Make sure you take particular note of bold-faced blocks in Litvin! NB2: Assume that you are not allowed to create a second, temporary data structure, which would enable the use of a for-each() loop.
... \#6.³: If Integer provides compareTo(), then which Java interface does it likely implement?

Michael Ferraro 2016-01-31