Self Check 7.16

• Answer:

  for (int i = 0; i < values.length; i++)
  {
     System.out.print(values[i]);
     if (i < values.length - 1)
     {
        System.out.print(" | ");
     }
  }

  Now you know why we set up the loop the other way.

Self Check 7.17

System.out.print(values[0]);
for (int i = 1; i < values.length; i++)
{
   System.out.print(", " + values[i]);
}

• Answer: If the array has no elements, then the program terminates with an exception.

Self Check 7.18

for (pos = 0; pos < values.length && !found; pos++)
{
   if (values[pos] > 100)
   {
      found = true;
   }
}

• Answer: If there is a match, then pos is incremented before the loop exits.

Self Check 7.19

for (int i = pos; i < currentSize - 1; i++)
{
   values[i + 1] = values[i];
}

• Answer: This loop sets all elements to values[pos].

Problem Solving: Adapting Algorithms

• By combining fundamental algorithms, you can solve complex programming tasks.
• Problem: Compute the final quiz score by dropping the lowest and finding the sum of all the remaining scores.
• Related algorithms:
  • Calculating the sum
  • Finding the minimum value
  • Removing an element
• A plan of attack

  Find the minimum.
  Remove it from the array.
  Calculate the sum.

• Try it out. The minimum is 4
  
• We need to use a linear search to find the position of the minimum.

Problem Solving: Adapting Algorithms - continued

• Revise the plan of attack

  Find the minimum value.
  Find its position.
  Remove that position from the array.
  Calculate the sum.

• Try it out
  • Find the minimum value of 4. Linear search tells us that the value 4 occurs at position 5.
    
  • Remove it
    
• Compute the sum: 8 + 7 + 8.5 + 9.5 + 7 + 10 = 50.
• This walk-through demonstrates that our strategy works.

Problem Solving: Adapting Algorithms - continued

• Inefficient to find the minimum and then make another pass through the array to obtain its position.
• Modify minimum algorithm to remember the position of the smallest element

  int smallestPosition = 0;
  for (int i = 1; i < values.length; i++)
  {
     if (values[i] < values[smallestPosition])
     {
        smallestPosition = i;
     }
  }

• Final Strategy

  Find the position of the minimum.
  Remove it from the array.
  Calculate the sum.

Self Check 7.20

• Answer: Use the first algorithm. The order of elements does not matter when computing the sum.

Self Check 7.21

• Answer:

  Find the minimum value.
  Calculate the sum.
  Subtract the minimum value.

Self Check 7.22

• Answer: Use the algorithm for counting matches (Section 6.7.2) twice, once for counting the positive values and once for counting the negative values.

Self Check 7.23

• Answer: You need to modify the algorithm in Section 7.3.4.

  boolean first = true;
  for (int i = 0; i < values.length; i++)
  {
     if (values[i] > 0))
     {
        if (first) { first = false; }
        else { System.out.print(", "); }
     }
     System.out.print(values[i]);
  }

  Note that you can no longer use i > 0 as the criterion for printing a separator.

Self Check 7.24

for (int i = 0; i < values.length; i++)
{
   if (values[i] fulfills the condition)
   {
      matches[matchesSize] = values[i];
      matchesSize++;
   }
}

• Answer: Use the algorithm to collect all positive elements in an array, then use the algorithm in Section 7.3.4 to print the array of matches.

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

• Manipulating physical objects can give you ideas for discovering algorithms.
  
• The Problem: You are given an array whose size is an even number, and you are to switch the first and the second half.
• Example
  • This array
    
  • will become
    

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

• Use a sequence of coins, playing cards, or toys to visualize an array of values.
• Original line of coins
  
• Removal of an array element
  
• Insertion of an array element
  

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

• Swapping array elements
  
• Swap the coins in positions 0 and 4:
  
• Swap the coins in positions 1 and 5:
  

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

• Two more swaps
  
• The pseudocode

  i = 0
  j = size / 2
  While (i < size / 2)
     Swap elements at positions i and j
     i++
     j++

Self Check 7.25

• Answer: The paperclip for i assumes positions 0, 1, 2, 3. When i is incremented to 4, the condition i < size / 2 becomes false, and the loop ends. Similarly, the paperclip for j assumes positions 4, 5, 6, 7, which are the valid positions for the second half of the array.
  
  

Self Check 7.26

i = 0
j = size - 1
While (i < j)
   Swap elements at positions i and j
   i++
   j--

• Answer: It reverses the elements in the array.

Self Check 7.27

1 4 14 2 1 3 5 6 23

4 2 14 6 1 5 3 23 1

• Answer: Here is one solution. The basic idea is to move all odd elements to the end. Put one paper clip at the beginning of the array and one at the end. If the element at the first paper clip is odd, swap it with the one at the other paper clip and move that paper clip to the left. Otherwise, move the first paper clip to the right. Stop when the two paper clips meet. Here is the pseudocode:

  i = 0
  j = size - 1
  While (i < j)
     If (a[i] is odd)
        Swap elements at positions i and j.
        j--
     Else
        i++

Self Check 7.28

• Answer: Here is one solution. The idea is to remove all odd elements and move them to the end. The trick is to know when to stop. Nothing is gained by moving odd elements into the area that already contains moved elements, so we want to mark that area with another paper clip.

  i = 0
  moved = size
  While (i < moved)
     If (a[i] is odd)
        Remove the element at position i and add it at the end.
     moved--

Self Check 7.29

Consider the algorithm in Section 6.7.5 that finds the largest element in a sequence of inputs—not the largest element in an array. Why is this algorithm better visualized by picking playing cards from a deck rather than arranging toy soldiers in a sequence?

• Answer: When you read inputs, you get to see values one at a time, and you can’t peek ahead. Picking cards one at a time from a deck of cards simulates this process better than looking at a sequence of items, all of which are revealed.

Two-Dimensional Arrays

• An arrangement consisting of rows and columns of values
  • Also called a matrix.
• Example: medal counts of the figure skating competitions at the 2010 Winter Olympics.


Figure 13 Figure Skating Medal counts

• Use a two-dimensional array to store tabular data.
• When constructing a two-dimensional array, specify how many rows and columns are needed:

  final int COUNTRIES = 7;
  final int MEDALS = 3;
  int[][] counts = new int[COUNTRIES][MEDALS];

Two-Dimensional Arrays

• You can declare and initialize the array by grouping each row:

  int[][] counts =
  {
     { 1, 0, 1 },
     { 1, 1, 0 },
     { 0, 0, 1 },
     { 1, 0, 0 },
     { 0, 1, 1 },
     { 0, 1, 1 },
     { 1, 1, 0 }
  };

• You cannot change the size of a two-dimensional array once it has been declared.

Syntax 7.3 Two-Dimensional Array Declaration

Accessing Elements

• Access by using two index values, array[i][j]

  int medalCount = counts[3][1];

• Use nested loops to access all elements in a two-dimensional array.
• Example: print all the elements of the counts array
  

  for (int i = 0; i < COUNTRIES; i++)
  {
     // Process the ith row
     for (int j = 0; j < MEDALS; j++)
     {
        // Process the jth column in the ith row
        System.out.printf("%8d", counts[i][j]);
     }
     System.out.println(); // Start a new line at the end of the row
  }



Figure 14 Accessing an Element in a Two-Dimensional Array

Accessing Elements

• Number of rows: counts.length
• Number of columns: counts[0].length
• Example: print all the elements of the counts array

  for (int i = 0; i < counts.length; i++)
  {
     for (int j = 0; j < counts[0].length; j++)
     {
        System.out.printf("%8d", counts[i][j]);
     }
     System.out.println();
  }

Locating Neighboring Elements

Figure 15 Neighboring Locations in a Two-Dimensional Array

• Watch out for elements at the boundary array
  • counts[0][1] does not have a neighbor to the top

Accessing Rows and Columns

• Problem: To find the number of medals won by a country
  • Find the sum of the elements in a row
• To find the sum of the i^th row
  • compute the sum of counts[i][j], where j ranges from 0 to MEDALS - 1.
    
    
    
• Loop to compute the sum of the i^th row

  int total = 0;
  for (int j = 0; j < MEDALS; j++)
  {
     total = total + counts[i][j];
  }

Accessing Rows and Columns

• To find the sum of the j^th column
  • Form the sum of counts[i][j], where i ranges from 0 to COUNTRIES - 1
  
  

  int total = 0;
  for (int i = 0; i < COUNTRIES; i++)
  {
     total = total + counts[i][j];
  }

• 

section_6/Medals.java

•         Country    Gold  Silver  Bronze   Total
           Canada       1       0       1       2
            China       1       1       0       2
          Germany       0       0       1       1
            Korea       1       0       0       1
            Japan       0       1       1       2
           Russia       0       1       1       2
    United States       1       1       0       2

Self Check 7.30

• Answer: You get the total number of gold, silver, and bronze medals in the competition. In our example, there are four of each.

Self Check 7.31

int[][] board = new int[8][8];

• Answer:

  for (int i = 0; i < 8; i++)
  {
     for (int j = 0; j < 8; j++)
     {
        board[i][j] = (i + j) % 2;
     }
  }

Self Check 7.32

• Answer: String[][] board = new String[3][3];

Self Check 7.33

• Answer: board[0][2] = "x";

Self Check 7.34

• Answer: board[0][0], board[1][1], board[2][2]

Array Lists

• An array list stores a sequence of values whose size can change.
• An array list can grow and shrink as needed.
• ArrayList class supplies methods for many common tasks, such as inserting and removing elements.
• An array list expands to hold as many elements as needed.
  

Syntax 7.4 Array Lists

Declaring and Using Array Lists

• To declare an array list of strings

  ArrayList<String> names = new ArrayList<String>();
      

• To use an array list

  import java.util.ArrayList;

• ArrayList is a generic class
• Angle brackets denote a type parameter
  • Replace String with any other class to get a different array list type

Declaring and Using Array Lists

• ArrayList<String> is first constructed, it has size 0
• Use the add method to add an object to the end of the array list:

  names.add("Emily"); // Now names has size 1 and element "Emily"
  names.add("Bob"); // Now names has size 2 and elements "Emily", "Bob"
  names.add("Cindy"); // names has size 3 and elements "Emily", "Bob", and "Cindy"

• The size method gives the current size of the array list.
  • Size is now 3


Figure 17 Adding an Array List Element with add

Declaring and Using Array Lists

• To obtain an array list element, use the get method
  • Index starts at 0
• To retrieve the name with index 2:

  String name = names.get(2); // Gets the third element of the array list

• The last valid index is names.size() - 1
  • A common bounds error:

  int i = names.size();
  name = names.get(i); // Error

• To set an array list element to a new value, use the set method:

  names.set(2, "Carolyn");

Declaring and Using Array Lists

• An array list has methods for adding and removing elements in the middle.
  
• This statement adds a new element at position 1 and moves all elements with index 1 or larger by one position.

  names.add(1, "Ann")

• The remove method,
  • removes the element at a given position
  • moves all elements after the removed element down by one position
  • and reduces the size of the array list by 1.

  names.remove(1);

• To print an array list:

  System.out.println(names); // Prints [Emily, Bob, Carolyn]

Declaring and Using Array Lists

Figure 18 Adding and Removing Elements in the Middle of an Array List

Using the Enhanced for Loop with Array Lists

• You can use the enhanced for loop to visit all the elements of an array list

  ArrayList<String> names = . . . ;
  for (String name : names)
  {
     System.out.println(name);
  }

• This is equivalent to:

  for (int i = 0; i < names.size(); i++)
  {
     String name = names.get(i);
     System.out.println(name);
  }

Copying Array Lists

• Copying an array list reference yields two references to the same array list.
• After the code below is executed
  • Both names and friends reference the same array list to which the string "Harry" was added.

  ArrayList<String> friends = names;
  friends.add("Harry");



Figure 19 Copying an Array List Reference



• To make a copy of an array list, construct the copy and pass the original list into the constructor:

  ArrayList<String> newNames = new ArrayList<String>(names);

Working with Array Lists

ArrayList<String> names =
   new ArrayList<String>();

names.add("Ann");
names.add("Cindy");

System.out.println(names);

names.add(1, "Bob");

names.remove(0);

names.set(0, "Bill");

String name = names.get(i);

String last =
   names.get(names.size() - 1);

ArrayList<Integer> squares =
   new ArrayList<Integer>();
for (int i = 0; i < 10; i++)
{
   squares.add(i * i);
}

Wrapper Classes

• You cannot directly insert primitive type values into array lists.
• Like truffles that must be in a wrapper to be sold, a number must be placed in a wrapper to be stored in an array list.
  
  
• Use the matching wrapper class.
  
  

Wrapper Classes

• To collect double values in an array list, you use an ArrayList<Double>.
• if you assign a double value to a Double variable, the number is automatically “put into a box”
• Called auto-boxing:
  • Automatic conversion between primitive types and the corresponding wrapper classes:

  Double wrapper = 29.95; 

  • Wrapper values are automatically “unboxed” to primitive types

  double x = wrapper;
     



Figure 20 A Wrapper Class Variable




 

Using Array Algorithms with Array Lists

• The array algorithms can be converted to array lists simply by using the array list methods instead of the array syntax.
• Code to find the largest element in an array:

  double largest = values[0];
  for (int i = 1; i < values.length; i++)
  {
     if (values[i] > largest)
     {
        largest = values[i];
     }
  }

• Code to find the largest element in an array list

  double largest = values.get(0);
  for (int i = 1; i < values.size(); i++)
  {
     if (values.get(i) > largest)
     {
         largest = values.get(i);
     }
  }

Storing Input Values in an Array List

• To collect an unknown number of inputs, array lists are much easier to use than arrays.
• Simply read the inputs and add them to an array list:

  ArrayList<Double> inputs = new ArrayList<Double>();
  while (in.hasNextDouble())
  {
     inputs.add(in.nextDouble());
  }

Removing Matches

• To remove elements from an array list, call the remove method.
• Error: skips the element after the moved element

  ArrayList<String> words = ...;
  for (int i = 0; i < words.size(); i++)
  {
     String word = words.get(i);
     if (word.length() < 4)
     {
        Remove the element at index i.
     }
  }

• Concrete example
  
• Should not increment i when an element is removed

Removing Matches

• Pseudocode
  

  If the element at index i matches the condition
  Remove the element.
  Else
  Increment i.

• Use a while loop, not a for loop

  int i = 0;
  while (i < words.size())
  {
     String word = words.get(i);
     if (word.length() < 4)
     {
        words.remove(i);
     }
     else
     {
        i++;
     }
  }

Choosing Between Array Lists and Arrays

• For most programming tasks, array lists are easier to use than arrays
  • Array lists can grow and shrink.
  • Arrays have a nicer syntax.
• Recommendations
  • If the size of a collection never changes, use an array.
  • If you collect a long sequence of primitive type values and you are concerned about efficiency, use an array.
  • Otherwise, use an array list.

Choosing Between Array Lists and Arrays

section_7/LargestInArrayList.java

• Please enter values, Q to quit:
  35 80 115 44.5 Q
  35
  80
  115 <== largest value
  44.5
  

Self Check 7.35

• Answer:

  ArrayList<Integer> primes = new ArrayList<Integer>();
  primes.add(2);
  primes.add(3);
  primes.add(5);
  primes.add(7);
  primes.add(11);

Self Check 7.36

• Answer:

  for (int i = primes.size() - 1; i >= 0; i--)
  {
     System.out.println(primes.get(i));
  }

Self Check 7.37

ArrayList<String> names = new ArrayList<String>;
names.add("Bob");
names.add(0, "Ann");
names.remove(1);
names.add("Cal");

• Answer: "Ann", "Cal"

Self Check 7.38

ArrayList<String> names;
names.add(Bob);

• Answer: The names variable has not been initialized.

Self Check 7.39

public void append(ArrayList<String> target, ArrayList<String> source)
{
   for (int i = 0; i < source.size(); i++)
   {
      target.add(source.get(i));
   }
}

ArrayList<String> names1 = new ArrayList<String>();
names1.add("Emily");
names1.add("Bob");
names1.add("Cindy");
ArrayList<String> names2 = new ArrayList<String>();
names2.add("Dave");
append(names1, names2);

• Answer: names1 contains "Emily", "Bob", "Cindy", "Dave"; names2 contains "Dave"

Self Check 7.40

• Answer: Because the number of weekdays doesn’t change, there is no disadvantage to using an array, and it is easier to initialize:

  String[] weekdayNames = { "Monday", "Tuesday", "Wednesday", "Thursday", “Friday”,
      "Saturday", "Sunday" };

Self Check 7.41

• Answer: Reading inputs into an array list is much easier.

Regression Testing

• Test suite: a set of tests for repeated testing
• Cycling: bug that is fixed but reappears in later versions
• Regression testing: involves repeating previously run tests to ensure that known failures of prior versions do not appear in new versions

Regression Testing - Two Approaches

• Organize a suite of test with multiple tester classes: ScoreTester1, ScoreTester2, ...

  public class ScoreTester1
  {
     public static void main(String[] args)
     {
        Student fred = new Student(100);
        fred.addScore(10);
        fred.addScore(20);
        fred.addScore(5);
        System.out.println("Final score: " + fred.finalScore());
        System.out.println("Expected: 30");
     }
  }
      

• Provide a generic tester, and feed it inputs from multiple files.

section_8/ScoreTester.java

Generic tester:

Input and Output Redirection

Section_8/input1.txt

30
10
20
5

• Type the following command into a shell window
  • Input redirection

  java ScoreTester < input1.txt

• Program Run:

  Final score: 30
  Expected: 30

• Output redirection:

  java ScoreTester < input1.txt > output1.txt