IN THIS CONCEPT

Summary: In the previous Algorithms section (Concept 6), you learned basic algorithms for swapping, copying, searching, accumulating, and finding the highest or lowest value in a list. What if the information being processed is buried in some complex data structure that is also buried in a class hierarchy? Or what if you are asked to solve a problem that you’ve never seen before? This concept focuses on algorithms that require you to access information that is more in depth and models how to write algorithms for different situations.

Key Ideas

   The process of developing an original algorithm requires concentration and analytical thought.

   Accessing data that is buried within a class hierarchy requires the programmer to use the methods that belong to the class.

The Accumulate Advanced Algorithm

You have been hired by the high school baseball team to write a program that calculates statistics for the players on the team. You decide to have a class called BaseballPlayer. Every BaseballPlayer has a name, a numberOfHits, and a numberOfAtBats. The BaseballRunner has an array of BaseballPlayer objects called roster. Your goal is to find the team batting average.

General Problem: Given a roster of baseball players, find the team’s batting average.

Refined Problem: You are given a list of baseball players. Every baseball player knows his number of hits and number of at-bats. The team average is found by first computing the sum of the at-bats and the sum of the hits and then dividing the total hits by the total at-bats. Write a method that computes the team batting average.

Final Problem: Write a method called findTeamAverage that has one parameter: a BaseballPlayer array. The method should return a double that is the team’s batting average. Compute the team average by dividing the total hits by the total at-bats. Make sure a player exists before processing him. Also, perform a check against zero before computing the team average. If the team total at-bats is 0, return a team batting average of 0.0. Finally, adapt your algorithm to work with an ArrayList of BaseballPlayer objects.

Algorithm:

Step 1: Create a variable called totalHits and set it equal to 0

Step 2: Create a variable called totalAtBats and set it equal to 0

Step 3: Look at each player on the roster

Step 4: Get the number of hits for the player and add it to totalHits

Step 5: Get the number of atBats for the player and add it to totalAtBats

Step 6: Continue until you reach the end of the list

Step 7: Compute the teamBattingAverage by dividing the totalHits by the totalAtBats

Step 8: Return the teamBattingAverage

Pseudocode:

set totalHits = 0

set totalAtBats = 0

for (iterate through all the players in the roster)

Java Code 1: Java code using an array (for loop)

Java Code 2: Java code using an array (for-each loop)

Java Code 3: Java code using an ArrayList (for loop)

Java Code 4: Java code using an ArrayList (for-each loop)

The Find-Highest Advanced Algorithm

General Problem: Given a roster of baseball players, find the name of the player that has the highest batting average.

Refined Problem: You are given a list of baseball players. Every baseball player has a name and knows how to calculate his batting average. Write a method that gets the batting average for every player in the list, and find the name of the player that has the highest batting average.

Final Problem: Write a method called findBestPlayer that has one parameter: a BaseballPlayer array. The method should return a String that is the name of the player that has the highest batting average. Make sure a player exists before processing him. If two players have the same high average, only select the first player. Also, adapt your algorithm to work with an ArrayList of BaseballPlayer objects.

Note: We will use the BaseballPlayer class from the previous example.

Algorithm:

Step 1: Create a variable called highestAverage and assign it a really small number

Step 2: Create a variable called bestPlayer and assign it the empty String

Step 3: Look at each of the players in the roster

Step 4: If the batting average of the player is greater than highestAverage, then set the highestAverage to be that player’s average and set bestPlayer to be the name of the player

Step 5: Continue until you reach the end of the list

Step 6: Return the name of bestPlayer

Pseudocode:

set highestAverage = the smallest available number in Java

set bestPlayer = ""

for (iterate through all the players in the list)

Java Code 1: Java code using an array (for loop)

Java Code 2: Java code using an array (for-each loop)

Java Code 3: Java code using an ArrayList (for loop)

Java Code 4: Java code using an ArrayList (for-each loop)

The Connect-Four Advanced Algorithm

Connect Four is a two-player game played on a grid of six rows and seven columns. Players take turns inserting disks into the grid in hopes of connecting four disks in a row to win the game. You have been hired to work on the app version of the game, and it is your responsibility to determine whether a player has won the game.

General Problem: Determine if a player has won the game of Connect Four.

Refined Problem: The Connect Four app version uses a 2-D array that is 6 × 7. After a player makes a move, determine if he or she has won by checking all possible ways to win. If four of the same color disks are found in a line, then the game is over. Decide who won the game (player one or player two). A way to win can be vertical, horizontal, diagonally downward, or diagonally upward.

Final Problem: Write a method called checkForWinner that has one parameter: a 2-D array of int. The 2-D array consists of 1s and 2s to represent a move by player one or player two. Cells that do not contain a move have a value of 0. This method checks all four directions to win (vertical, horizontal, diagonally downward, and diagonally upward). The method should return the number of the player who won or return 0 if nobody has won.

Algorithm (for vertical win):

Note: There are a total of 21 ways to win vertically. Start with the top left cell and move in Row-Major order.

Step 1: Start with row 0 and end with row 2 (row 2 is four less than the number of rows)

Step 2: Start with column 0 and end with column 6 (use every column)

Step 3: If current cell value is not equal to 0 and the current cell = cell below it = cell below it = cell below it, then a player has won

Step 4: Continue until you reach the end of row 2

Step 5: Return the player who won or zero

Pseudocode (for vertical win):

Algorithm (for diagonal downward win):

Note: There are a total of 12 ways to win diagonally downward. Start with the top left cell and go in Row-Major order.

Step 1: Start with row 0 and end with row 2 (row 2 is four less than the number of rows)

Step 2: Start with column 0 and end with column 3 (column 3 is four less than the number of columns)

Step 3: If current cell value is not equal to 0 and the cell below and to the right = cell below and to the right = cell below and to the right, then a player has won

Step 4: Continue until you reach the end of row 2

Step 5: Return the player who won or zero

Pseudocode (for diagonal downward win):

Note: I have provided the algorithm and pseudocode for only the vertical win and the diagonal downward win. The code for these, as well as the horizontal win and the diagonal upward win, are provided in the Java code below.

Java Code: Java code using a 2-D array and nested for loops (includes all four ways to win):

The Twitter-Sentiment-Analysis Advanced Algorithm

Twitter has become very popular and Twitter Sentiment Analysis has grown in popularity. The idea behind Twitter Sentiment is to pull emotions and/or draw conclusions from the tweets. A large collections of tweets can be used to make general conclusions of how people feel about something. The important words in the tweet are analyzed against a library of words to give a tweet a sentiment score.

One of the first steps in processing a tweet is to remove all of the words that don’t add any real value to the tweet. These words are called stop words, and this step is typically part of a phase called preprocessing . For this problem, your job is to remove all the stop words from the tweet. There are many different ways to find meaningless words, but for our example, the stop words will be all words that are three characters long or less.

General Problem: Given a tweet, remove all of the meaningless words.

Refined Problem: You are given a tweet as a list of words. Find all of the words in the list that are greater than three characters and add them to a new list. Leave the original tweet unchanged. The new list will contain all the words that are not stop words.

Final Problem: Write a method called removeStopWords that has one parameter: an ArrayList of Strings. The method should return a new ArrayList of Strings that contains only the words from the original list that are greater than three characters long. Do not modify the original ArrayList. Also, modify the code to work on a String array.

Solution 1: Using an ArrayList

Algorithm 1:

Step 1: Create a list called longWords

Step 2: Look at each word in the original list

Step 3: If the word is greater than three characters, add that word to longWords

Step 4: Continue until you reach the end of the original list

Step 5: Return longWords

Pseudocode 1:

Java Code 1: Using an ArrayList (for-each loop)

Solution 2: Using an Array

This solution requires more work than the ArrayList solution. Since we don’t know how big to make the array, we need to count how many words are greater than three characters before creating it.

Algorithm 2:

Step 1: Create a counter and set it to zero

Step 2: Look at each word in the original list

Step 3: If the length of the word is greater than three characters, add one to the counter

Step 4: Continue until you reach the end of the list

Step 5: Create an array called longWords that has a length of counter

Step 6: Create a variable that will be used as an index for longWords and set it to zero

Step 7: Look at each word in the original list

Step 8: If the length of the word is greater than three characters, add the word to longWords and also add one to the index that is used for longWords

Step 9: Continue until you reach the end of the list

Step 10: Return the longWords array

Pseudocode 2:

Java Code 2: Using an array (using a for-each loop and a for loop)

 Rapid Review

• The process of developing an original algorithm requires concentration and analytical thought.
• Accessing data buried within a class hierarchy requires the programmer to use the methods that belong to the class.

 Review Questions

1 .   Count the empty lockers.

A high school has a specific number of lockers so students can store their belongings. The office staff wants to know how many of the lockers are empty so they can assign these lockers to new students. Consider the following classes and complete the implementation for the countEmptyLockers method.

2 .    Find the total revenue for the school lunch program.

A high school lunch program serves lunch to students. When the student checks out, the lunch person enters the cost of the meal. You have been hired to write the method that calculates the total amount of money received for every lunch order for all the days of the school year.

The following classes are used in the software for the lunch program. Complete the implementation for the method getTotalOfOrders .

 Answers and Explanations

1 .    Count the empty lockers.

Algorithm:

Step 1: Create a variable called total and set it to zero

Step 2: Look at each of the lockers in the list

Step 3: If the locker is not in use, increment the total

Step 4: Continue until you reach the end of the list

Step 5: Return the total

Pseudocode:

Java Code: Java code using an array (for-each loop)

2 .    Find the total revenue for the school lunch program.

Algorithm:

Step 1: Create a variable called total and set it to zero

Step 2: Look at each Day in the list of Days

Step 3: Look at each Order in the list of Orders for each Day

Step 4: Add the current order amount to the total

Step 5: Continue until you reach the end of the list of Orders

Step 6: Continue until you reach the end of the list of Days

Step 7: Return the total

Pseudocode:

Java Code: Java code using an ArrayList (2 for-each loops)