10 Algorithms You’ll Need For The AP CSA Exam And Their Java Code
AP season has arrived and exhausted hundreds of thousands of high school students pining for the 5 that guarantees them college credit or possibly a boost to the college application. Although it is already late May, this year’s AP season hasn’t quite concluded due to the College Board’s extra testing dates created to accommodate impacts from COVID-19. Thus, I write this post to extend a helping hand from somebody who’s been through the testing process.
AP CSA was definitely my favourite subject, so I was particularly meticulous when studying for that exam. After trying numerous past written free-response questions, I noticed a common pattern in the “type” of questions that were asked. There were really only a couple of algorithms that were tested in the FRQs that involved algorithm design, but they were repeatedly included in the exams after being disguised with different contexts. Thus, I’ve compiled a list of these most common algorithms, at least one of which will almost certainly appear on your exam. I’ve also written the Java code for them and provided some written explanations for their logic. I hope that this master sheet can help somebody who’s having trouble with some of the algorithms. I use ArrayList in all my examples, but you can achieve the same results with arrays simply by indexing the data structure using list_name[i] instead of list_name.get().
1. Looping Through an ArrayList and Seeing if Your Object Matches
Example: We have a method to check if how many Strings in an ArrayList, StringList, is equal to a String passed into the parameters.
public int countSame(String check) {
int count = 0;
for(int i=0; i<StringList.size(); i++) {
if(StringList.get(i).equals(check) {
count++;
}
}
return(count);
}2. Looping Through an ArrayList and Compare Adjacent Values
Example: We have a method that checks and returns true if any adjacent Strings in an ArrayList, StringList, are equal (two of the same Strings one after another).
public boolean adjacentStrings() {
for(int i=0; i<StringList.size(); i++) {
if(StringList.get(i).equals(StringList.get(i-1)) {
return(true);
}
}
return(false);
}This algorithm goes through every list item except the first one, and checks if it is equal to the list item before it. If the program finds one that is equal, it returns true. If it goes through every item and doesn’t find any that are equal, it returns false. The loop starts at i=1 because it compares the second item (i=1) with the first one(i=0).
3. Looking Through a List and Removing an Object that Meets a Criteria
Example: We have an ArrayList of Dog objects. In the Dog class, you see that each Dog has a getBreed() method that returns a String of the Dog’s breed. This method will remove each Dog in an ArrayList of Dogs, dogList, that are the same breed as the one specified in the parameter.
public void removeDogBreed(String breedToRemove) {
for(int i=0;i<dogList.size();i++) {
if(dogList.get(i).getBreed().equals(breedToRemove) {
dogList.remove(i)
i-=1;
}
}
}i-=1 is necessary because when you remove a Dog, the list shifts, so you need to subtract one from i to make sure it doesn’t skip checking any Dogs.
4. Finding the Smallest or Largest Number Value in an ArrayList
Example: Let’s say you have an ArrayList of Dogs, dogList. The class documentation shows that the Dog class has a method getAge() which returns the age of the Dog. We have a method that returns the Dog that is the youngest. If there are two Dogs of the same age, return any.
public Dog getYoungestDog() {
int youngestAge = dogList.get(0).getAge();
Dog youngestDog = dogList.get(0);
for(int i=1; i<dogList.size();i++) {
if(dogList.get(i).getAge() < youngestAge) {
youngestAge = dogList.get(i).getAge();
youngestDog = dogList.get(i);
}
}
return(youngestDog);
}5. Question Where You Need to Manipulate Individual Digits in a Number
Example: a method that checks if the number passed through a parameter is one of the digits of an int num. Assuming that the number passed in cannot be 0.
→ If num is 1938 and the number passed in the parameter is 3, return true.
→ If num is 1938 and the number passed in the parameter is 4, return false.
public boolean isIn(int checkDigit) {
while(num>0) {
if(num%10==checkDigit) {
return(true);
}
num/=10;
}
return(false);
}This algorithm is useful if they want you to traverse a number without converting it to a String. To understand the logic behind it, pretend our number is 1938. num%10 is equal to 8, since % gives the remainder, and when 1938 is divided by 10, the remainder is 8. If num%10 is equal to checkDigit, return true. If it’s not, divide 1938 by 10 and set that equal to num. Since both are int types, the program will return an answer without the remainder. 1938/10 = 193. this is your new num. Repeat the loop. If 193%10 is equal to checkDigit, return true. Repeat the process, until you divide your last digit and end up with 0. If you are here, nothing returned true, so checkDigit is not in num. Now return false.
The College Board loves asking questions about digits in a number. Although they may not ask it in the same context as this question, understanding how to use % and / by 10 to check digits will be useful.
6. Checking if Numbers (Or Other Comparable Objects Such as Strings) are in Ascending Order
For putting Strings into ascending order, you can use String.compareTo() method instead of the < or > operators used for numbers.
Example: We have a method that returns false if an ArrayList, numList, is in strictly ascending order, and false otherwise.
public boolean isAscending() {
for(int i=1; i<numList.size(); i++) {
if(numList.get(i)<numList.get(i-1)) {
return(false);
}
}
return(true);
}In this example, we first loop through each item. If any of the items are smaller than the one before it, the ArrayList is not in ascending order, so return false. If you get through all the numbers without returning false, return true because it means everything is in ascending order.
7. Inserting a Number (Or Other Comparable Objects Such as Strings) in its Appropriate Place
Example: We have a method that needs to insert a number into an ArrayList, numList, into its appropriate place. The ArrayList is sorted by ascending order, so we want to put the number, num, into the ArrayList to keep the ascending order.
public void insertInPlace(int num) {
for(int i=0; i<numList.size();i++) {
if(num<numList.get(i)) {
numList.add(i,num);
return;
}
}
numList.add(num);
}In this example, we go through the list until you find a number that your num is smaller than, meaning your num belongs before it — the last numList.add() is to add the num in case your num is bigger than everything in the list.
8. Removing a Single Character from a String
Example: We have a method that will remove all instances of the String smallWord in a String word.
public void removeLetter(String smallWord) {
int start = word.indexOf(smallWord);
int l = smallWord.length();
while(start>-1) {
word = word.substring(0,start)+word.substring(start+l);
start = word.indexOf(smallWord);
}
}Here, we find the index of a word, and remove it from a String until it no longer exists. Note: this collapses a word, which may or may not be what you want.
9. Reversing a String
Example: We have a method that will take a String and return a reversed version.
public String reverse(String reverseMe) {
String reversed = “”;
for(int i=reverseMe.length()-1; i>=0; i--) {
reversed = reversed + reverseMe.substring(i, i+1);
}
return(reversed);
}Here, we loop through the string but from the end to the front, and add letters as we go.
10. Checking if a String Contains Numbers or Vowels (Or Anything You Want)
Example: We have a method that returns true if our String stringCheck has numbers in it and false if not. For example, “wilson” would return false, and “wilson10” would return true.
public boolean hasNum(String stringCheck) {
String numbers = “0123456789”;
for(int i=0; i<stringCheck.length(); i++) {
String letter = stringCheck.substring(i,i+1);
if(numbers.indexOf(letter)>-1) {
return(true);
}
}
return(false);
}Here, we loop through every character in stringCheck. Then, we check if the letter is contained in the String “0123456789”. If it is, then that “letter” is a number. Return true. If we finish checking and that doesn’t happen, return false.
And that’s it! It can often be difficult to keep track of what you learn and the important concepts whenever taking a course, so I hope this article has helped out in that aspect whether you’re reading just to review or to learn important algorithms.