5 Steps to a 5 AP Computer Science A 2017 (2016)
STEP 4
Review the Knowledge You Need to Score High
CONCEPT 6
Algorithms (Basic Version)
IN THIS CONCEPT
Summary: Software developers use algorithms extensively to write the code that will automate a process in a computer program. The algorithms described in this concept are some of the fundamental algorithms that you should know for the AP Computer Science A Exam.
Key Ideas
An algorithm is a set of steps that when followed complete a task.
Pseudocode is a hybrid between an algorithm and actual Java code.
Efficient code performs a task in the fastest way.
The swap algorithm exchanges the values of two variables.
The copy algorithm makes a duplicate of a data structure.
The sequential search algorithm finds a value in a list.
The accumulate algorithm traverses a list, adding each value to a total.
The find-highest algorithm traverses and compares each value in the list to determine which one is the largest.
How We Use Algorithms
In our daily lives, we develop and use algorithms all the time without realizing that we are doing it. For example, suppose your grandma calls you because she wants to watch Game of Thrones using the HBO GO app on her smart TV, but she can’t figure out how to do it. You would respond to her by saying, “Hi, Grandma, well, the first thing you have to do is turn your TV on,” then yada, yada, yada until finally you say, “Press play.”
What you have just done is developed a process for how to solve a problem. Now, if she insists that you write the steps down on a notecard so she can follow it anytime she wants to, then, you will be writing the algorithm for “How to watch Game of Thrones on grandma’s smart TV.”
Give a man a fish and he will eat for a day; teach a man to fish and he will eat for a lifetime.
—Chinese proverb
Why Algorithms Are Important
The word algorithm can be simply defined as “a process to be followed to solve a problem.” Computer programmers use algorithms to teach the computer how to automate a process.
The number of algorithms to learn is infinite, so rather than attempting to learn all possible algorithms, my goal is to teach you how to write an algorithm . This will be handy on the AP Computer Science A Exam when you have to either analyze or generate code to accomplish something you’ve never done before. The two algorithm concepts in this book teach you how to think like a software developer.
Give developers a line of code and they will smile for a day; teach developers to write their own algorithms and they will smile for a lifetime.
—Coding proverb
Algorithm Versus Pseudocode Versus Real Java Code
Algorithms are great as directions for how to do something; however, they can’t be typed into a computer as a real Java program. The integrated development environment (IDE) needs to have the correct syntax so that the compiler can interpret your code properly. Can you imagine typing in the directions for Grandma as lines of code?
So, to solve this problem, programmers translate algorithms into pseudocode , which is a code-like language. This pseudocode is then translated into real code that the computer will understand.
This process is really powerful because as programming languages change, the algorithms can stay the same. In the examples that follow, I’ve written the code in Java, but it could’ve easily been written in C++, Python, etc.
Turning Your Ideas into Code
Pseudocode is an inner step when turning your ideas into code. It is code-like but does not use the syntax of any programming language.
The Swap Algorithm
Swapping is the concept of switching the values that are stored in two different variables. The ability to swap values is essential for sorting algorithms (explained in Concept 12). To complete a swap, you need to use a temporary variable to store one of the values.
Problem: Swap the values inside two integer variables. For example, if a = 6 and b = 8, then make a = 8 and b = 6.
Algorithm:
Step 1: Let a = 6 and b = 8
Step 2: Create a temporary variable called c
Step 3: Assign c the value of a
Step 4: Assign a the value of b
Step 5: Assign b the value of c
Step 6: Now, the value of a is 8 and b is now 6
Pseudocode:
set a = 6
set b = 8
c = a
a = b
b = c
Java Code:
int a = 6;
int b = 8;
int c;
c = a;
a = b;
b = c;
The Copy Algorithm for the Array and ArrayList
Making a copy of an array (or ArrayList) means to create a brand-new object that is a duplicate of the original. This is different from creating a new array variable (or ArrayList variable) that references the original array (or ArrayList). That was called making an alias. It is easy for new programmers to make the mistake of thinking that these two are the same.
Problem: Suppose you have an array of integers. Make a new array object that is a copy of this array. The two arrays should contain the same exact values but not be the same object. Then, modify your code to work with an ArrayList of numbers.
Algorithm:
Step 1: Create an array that is the same length as the original
Step 2: Look at each of the values in the original array one at a time
Step 3: Assign the value in the copy to be the corresponding value in the original
Step 4: Continue until you reach the last index of the original array
Pseudocode:
create an array called duplicate that has the same length as the original array
for (iterate through each element in the original array)
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)
Copying an Array Reference Versus Copying an Array
The following code demonstrates a common mistake when attempting to copy an array.
This code makes the reference variable copy refer to the same object that original refers to. This means that if you change a value in copy, it also changes the value in original. This code does not create a new object that is a duplicate of the original. This code makes both reference variables refer to the same object (the object that original refers to).
The Sequential Search Algorithm
When you search iTunes for a song, how does it actually find what you are looking for? It may use a sequential search to find the name of a song. A sequential search is the process of looking at each of the elements in a list, one at a time, until you find what you are looking for.
General Problem: Search for “Sweet Caroline” in a list of song titles.
Refined Problem: Write a method that allows you to search an array of song titles for a specific song title.
Final Problem: Write a method called searchForTitle that has two parameters: a string array and a string that represents the search target. The method should return the index of the target string if it is found and -1 if it does not find the target String. Note: I provide two solutions to solve this problem and compare their efficiency afterward.
The Search Target
When you search for a specific item in a list, the item you are looking for is often referred to as the search target.
Solution 1: Look at every item in the list.
Algorithm 1:
Step 1: Create a variable called foundIndex and set it equal to -1
Step 2: Look at each of the titles in the array one at a time
Step 3: Compare each title to the target title
Step 4: If the title is equal to the target title, then assign foundIndex to value of the current index
Step 5: Continue looking until you reach the end of the list
Step 6: Return the value of foundIndex
Pseudocode 1:
Java Code 1:
Solution 2: Stop looking if you find the search target.
Algorithm 2:
Step 1: Look at each of the titles in the array one at a time
Step 2: Compare the target title to each of the titles
Step 3: If the title is equal to the target title, then stop looking and return the current index
Step 4: Continue looking until you reach the end of the list
Step 5: Return -1
Pseudocode 2:
Java Code 2:
Efficiency
Analyze the two solutions that searched for the title of a song.
The second algorithm is more efficient than the first because the method stops looking for the title as soon as it finds it. The first algorithm is less efficient than the second because it continues to compare each of the titles in the list against the search target even though it may have already found the search target.
Efficiency
An efficient algorithm does its job in the fastest way it can. Efficient programs are optimized to reduce CPU (central processing unit) time and memory usage.
The Accumulate Algorithm
Suppose you have a list of all the baseball players on a team and you want to find the total number of hits that the team had. As humans, we can do this quite easily. Just add them up. But how do you teach a computer to add up all of the hits?
General Problem: Add up all of the hits for a baseball team.
Refined Problem: Write a method that finds the sum of all of the hits in an array of hits.
Final Problem: Write a method called findSum that has one parameter: an int array. The method should return the sum of all of the elements in the array. Then, modify your code to work with a 2-D array of int values and also an ArrayList of integers.
Algorithm:
Step 1: Create a variable called sum and set it equal to zero
Step 2: Look at each of the elements in the list
Step 3: Add the element to the sum
Step 4: Continue until you reach the end of the list
Step 5: Return the sum
Pseudocode:
Code 1: Java code using an array ( for-each loop)
Code 2: Java code using an array ( for loop)
Code 3: Java code using a 2-D array (Row-Major order)
Code 4: Java code using an ArrayList ( for-each loop)
Code 5: Java code using an ArrayList ( for loop)
The Find-Highest Algorithm
What is the highest score on your favorite video game? As more people play a game, how does the computer figure out what is the highest score in the list?
General Problem: Find the highest score out of all the scores for a video game.
Refined Problem: Write a method that finds the highest score in a list of scores.
Final Problem: Write a method called findHigh that has one parameter: an int array. The method should return the largest value in the array. Then, modify your code to work with a 2-D array of int values and also an ArrayList of Integers.
Solution 1: Let the highest be the first element in the list.
Algorithm:
Step 1: Create a variable called high and set it to the first element in the list
Step 2: Look at each of the scores in the list
Step 3: If the score is greater than the high score, then make it be the new high score
Step 4: Continue until you reach the end of the list
Step 5: Return the high score
Pseudocode:
Code 1: Java code using an array ( for loop)
Code 2: Java code using an array ( for-each loop)
Code 3: Java code using a 2-D array (Row-Major order)
Code 4: Java code using an ArrayList (for-each loop)
Code 5: Java code using an ArrayList (for loop)
Solution 2: Let the highest be an extremely low value.
There is an alternative solution to the high/low problem that you should know. To execute this alternative, we modify the first step in the previous algorithm.
Step 1: Create a variable called high and set it to a really, really small number .
This algorithm works as long as the really, really small number is guaranteed to be smaller than at least one of the numbers in the list. In Java, we can use the public fields from the Integer class to solve this problem.
Likewise, to solve the find-lowest problem, you could set the low to be a really, really big number.
Searching for the Smallest Item in a List
If we changed the previous example to find the lowest score in the list, then the comparator in the if-statement would be changed to less than, <, instead of greater than, >.
Rapid Review
Algorithms and Pseudocode
- This purpose of this concept is to teach you how to translate an idea into code.
- An algorithm is a sequence of steps that, when followed, produces a specific result.
- Algorithms are an extremely important component of software development since you are teaching the computer how to do something all by itself.
- There are an infinite number of algorithms.
- Pseudocode is a hybrid between an algorithm and real code.
- Pseudocode does not use correct syntax and is not typed into an IDE.
- Pseudocode helps you translate an algorithm into real code since it is code-like and more refined than an algorithm.
- Programmers translate algorithms into pseudocode and then translate pseudocode into real code.
Swap Algorithm
- The swap algorithm allows you to switch the values in two different variables.
- To swap the values in two different variables, you must create a temporary variable to store one of the original variables.
- To swap num1 and num2, set temp = num1, let num1 = num2, and then let num2 = temp.
Copy Algorithm
- The copy algorithm is used to create a duplicate version of a data structure.
- It looks at each element in the original list and assigns it to the duplicate list.
- The duplicate is not an alias of the original; it is a new object that contains all of the same values as the original.
Sequential Search Algorithm
- The sequential search algorithm searches a list to find a search target.
- It looks at each element in the list one at a time comparing the element to the search target.
Accumulate Algorithm
- The accumulate algorithm finds the sum of all the items in a list.
- It looks at each element in the list one at a time, adding the value to a total.
Find-Highest Algorithm
- The find-highest algorithm finds the largest value in a list.
- It looks at each element in the list one at a time, comparing the value to the current high value.
- Common ways to implement this algorithm include initializing the highest value with the first value in the list or to an extremely small negative number.
- The find-highest algorithm can be modified to find the lowest item in a list.
Review Questions
- Replace only highs and lows.
Write a method that replaces the highest values and the lowest values in a list. The method takes one parameter: an int array. The range of the numbers is 0–1000 (inclusive). If a value in the array is greater than 750, replace the value with 1000. If a value in the array is less than 250, replace it with 0. The method should return an int array of the same length as the parameter array and leave the original array untouched.
The array passed to the method:
The array returned by the method:
- Determine if the numbers in anArrayList are always increasing.
Write a method that determines if the values in an ArrayList are always increasing. The method takes one parameter: an ArrayList of Integer. The method returns true if the elements in the array are continually increasing and false if the elements are not continually increasing.
The ArrayList passed to the method:
- Find all the songs that contain the word “Love” in the title.
One of the most popular themes in music lyrics is love. Suppose a compilation of thousands of songs is stored in a grid. Count the number of songs that contain the word “Love” in the title.
Write a method that counts the number of song titles that contains a certain string in the title. The method has two parameters: a 2-D array of String objects and a target string. The method should return an integer that represents the number of strings in the 2-D array that contains the target string.
The 2-D array passed to the method:
- Determine the relative strength index of a stock.
The relative strength index (RSI) of a stock determines if the stock is overpriced or underpriced. The range of the RSI is from 0 to 100 (inclusive). If the value of the RSI is greater than or equal to 70, then the stock is determined to be overpriced and should be sold.
Write a method that takes an array of RSI values for a specific stock and determines when the stock is overpriced. The method has one parameter: a double array. The method should return a new array of the same length as the parameter array. If the value in the RSI array is greater than 70, set the value in the overpriced array to 1. If the RSI value is less than or equal to 70, set the value in the overpriced array to 0.
The RSI array that is sent to the method:
The overpriced array that is returned by the method:
- Fill an array with even numbers.
Write a method that fills an array with random even numbers. The method takes two parameters: the number of elements in the array and the range of the random numbers (0–number inclusive).
result contains the following (results will change each time program is run):
- Determine if the rate is increasing.
If a stock price is increasing, that means the value of it is going up. If the rate that the stock price is increasing is increasing, it means that the price is rising at a faster rate than it was the day before. Write a method that determines if the rate at which a stock price increases is increasing. The method has one parameter: an ArrayList of Double values that represent the stock prices. Return true if the rate that the stock is increasing is increasing, and false if the rate is not increasing.
stockPrices contains the following:
Answers and Explanations
- Replace only highs and lows.
Algorithm:
Step 1: Create a new array called temp that is the same length as the original
Step 2: Look at each of the scores in the list
Step 3: If the score is greater than 750, then store 1000 in the temp array
Step 4: If the score is less than 250, then store 0 in the temp array
Step 5: If the score is between 250 and 750, then store the score in the temp array
Step 6: Continue until you reach the end of the list
Step 7: Return the temp array
Pseudocode:
Java code:
- Determine if the numbers in anArrayList are always increasing.
Algorithm:
Step 1: Look at each of the scores in the list starting at the second element
Step 2: If the first score is less than or equal to the second score, then return false
Step 3: Advance to the next element and continue until you reach the end of the list
Step 4: Return true
Pseudocode:
Java code:
- Find all the songs that contain the word “Love” in the title.
Algorithm:
Step 1: Initialize a count variable to zero
Step 2: Look at each of the scores in the 2-D array (using Row-Major order)
Step 3: If the song title contains the target String, then increment the count
Step 4: Continue until you reach the end of the list
Step 5: Return count
Pseudocode:
Java code:
- Determine the relative strength index of a stock.
Algorithm:
Step 1: Create an array called temp that is the same length as the parameter array
Step 2: Look at each of the scores in the array
Step 3: If the score > 70, then set the corresponding element of the temp array to 1; otherwise set it to 0
Step 4: Continue until you reach the end of the list
Step 5: Return temp
Pseudocode:
create an integer array called temp that is the same length as the parameter array for (iterate through all the elements in the parameter array)
Java code:
- Fill an array with randomly chosen even numbers. There are several ways to do this. Here is one.
Algorithm:
Step 1: Create an array called temp that is the same length as the parameter array
Step 2: Loop as many times as the length of the parameter array
Step 3: Generate a random number in the appropriate range
Step 4: While the random number is not even, generate a random number in the appropriate range
Step 5: Put the random number in the list
Step 6: Continue until you complete the correct number of iterations
Step 7: Return temp
Pseudocode:
create an integer array called temp that is the same length as the parameter array for (iterate as many times as the length of the parameter array)
Java code:
- Determine if the rate is increasing.
Algorithm:
Step 1: Iterate through the parameter array starting at the 3rd element
Step 2: If (the third element minus the second element) is less than or equal to the (second element minus the first element), then return false
Step 3: Move onto the next element and go to Step 2 (and adjust the elements #s)
Step 4: If you get this far without returning, return true
Pseudocode:
for (iterate through the parameter array starting with the third element (index 2))
Java code:....