The Big Takeaway Of This Unit

Exam Weighting

• 17.5-22.5% of the test

• Roughly 7 to 9 multiple-choice questions

• A part of FRQ #1, which tests your ability to write methods using control structures, including loops.

Enduring Understanding

Now that we have finished branching and conditionals, it's time to add the final element to our algorithm toolbox: iteration. Iteration is a way to simplify code that would otherwise be repeated many times in succession. Using loops, we can finally implement complex algorithms and solutions to common problems that we weren't able to before. In this unit, we will learn about two types of loops: the while loop and the for loop.

Building Computational Thinking

When we code, we need to make sure that our loops run exactly the number of times that they are supposed to, or else, it may just throw you for a loop! We can do this by checking the loop conditions and the incrementation inside our loops.

Loops can face other problems, such as having no end (an infinite loop) or returning the wrong result. We will be learning a method that may help us in making sure our loop works! Combining these with the branching methods we learned in the last unit, we can make many complex algorithms.

Main Ideas for This Unit

• While Loops

• For Loops

• String Traversals

• String Algorithms

• Nested Iterations

• Tracing

4.1 While Loops

A while loop tells the computer to keep running a section of code while the condition being checked is still true. The condition is being checked at the beginning of the loop and must evaluate to a boolean value (true or false). Once the condition is false, the code inside the loop will stop executing, and the code after the body of the loop will execute. In order to avoid creating an infinite loop, the condition of the while loop must be modified inside the loop so the condition can be false in the future. Here is an example:

int i = 0;

while (i < 5) {

System.out.print(i);

i++;

}

The output is 01234.

Let's understand this code line by line. In line 1, a new variable i was created and the value 0 was assigned to it. In line two, we created our while loop and put the condition in parentheses. This line tells the computer to execute the while loop while the value of i is less than 5. The body of the loop is enclosed in the curly brackets {}. Line 3 prints the value of the variable i, but not on a new line. Line 4 is a critical element of the while loop: the modifier. This line modifies the condition of the while loop -- in this case, the value of the variable i -- so that in the future, the condition will be false. The value of the variable i is incremented so the new value is 1.

Here's the cool part about loops: After line 4 executes, the computer goes back to line 2 and checks the condition again. Since i is now 1 and 1 is less than 5, the body of the loop will execute again. MCQ questions will often ask you what the output of the while loop is, and it can be hard to keep track of all this information in your head, so you can use a tracing table to help you trace the code. This is a tracing table for the loop above:

We make a new row for each iteration, write down the value of i, then check if it meets the condition of the while loop. Since 5 is not less than 5, the while loop will stop at the fifth iteration. This tracing table is very simple, but as your loops get more complex, the tracing table becomes essential to your success with multiple-choice questions.

One important note about while loops: if the condition evaluates to false to begin with, the body of the loop will never execute. Always double-check your conditions!

You already know that a return statement stops a method immediately. If you put a return statement inside a while loop, the loop will also stop executing immediately, regardless of if the condition is still true.

These are the most common uses of while loops that you'll learn about this unit:

• Identify the individual digits of an integer

• Determine a minimum or maximum value

• Compute a sum, average, or mode

4.2 For Loops

Another type of loop is the for loop. This loop is similar to the while loop, but the functionality is slightly different. The basic structure for a for loop in Java is:

for (initialization; condition; iteration) {

// code to be executed

}

The initialization statement is executed only once before the first iteration of the loop, and is usually used to initialize a loop counter variable. In the while loop above, we initialized the variable i before the loop, but with a for loop, we can do it on the same line. The condition is a boolean expression that is evaluated at the beginning of each iteration of the loop. If the condition is true, the code inside the loop (the body of the loop) is executed. If the condition is false, the loop is terminated and the code after the loop block will execute. The iteration statement is executed at the end of each iteration, and is usually used to update the loop counter variable. In the while loop, we added an i++; statement at the end of the loop, but we can easily add it to the first line with a for loop. A for loop needs all three of these parts to run properly.

This for loop performs the same task as the while loop above so you can compare the two easily:

for (int i = 0; i < 5; i++) {

System.out.print(i);

}

The output of this loop is 01234. As you can see, the for loop accomplished in 2 lines what the while loop accomplished in 4, so it is the more efficient loop. All for loops can be converted to while loops and vice versa.

4.3 Developing Algorithms Using Strings

Using loops with strings is one application of the for loops and while loops, and a very important topic in AP CSA. You already know about some string methods, like .length() and .substring(int index), and now it's time to use them in loops.

With string methods and for loops, you can count how many times a letter appears in a certain String. Here is an example with the string "computer science":

String str = "computer science";

int count = 0;

for (int i = 0; i < str.length(); i++) {

if (str.substring(i, i+1).equals("e")) {

count++;

}

}

System.out.println(count);

The output of the print statement at the end will be 3 because there are three "e"s in "computer science." In line 1, we initialize a String variable and create the string we want to iterate through, which is "computer science." In line 2, a counter variable is created to count the number of "e"s. In line 3, we create the for loop and initialize the loop counter variable, make sure we only iterate for each letter of the string, and increment our loop counter variable. This loop counter variable is different than the count variable because this variable dictates how many times the loop should run, while the count variable keeps track of the number of "e"s.

In line 4, we enter the body of the loop. We start with an if statement that uses the .substring(int startIndex, int endIndex) method to separate out the current letter in the string. If i is 0, then i+1 will be 1, and the substring(0, 1) method will return the first letter in the string "computer science." The first letter is then compared to the string "e" using the equals(String string) method, which returns a boolean. Since "c" is not equal to "e," the method returns false, we don't enter the body of the if statement, and the loop goes back to line 3 to run again.

If we were to enter into the body of the if statement in line 5, however, we would increment the count variable by 1 to track that we have found an "e" in "computer science." After the loop has run for each letter in str, the print statement at the end prints out the new value of count, which is 3 because there are three "e"s in "computer science."

There are many other uses of String methods and loops. Here are some of the important ones covered in the 4.3 study guide that you need to know for AP CSA:

• Reversing a String

• Finding if one or more substrings has a particular property

• Check for a specific substring

All of these uses are variations of the method we wrote above. For this topic, tracing tables can really help to keep track of the iterations of the loop. The more you practice with this topic, the better you will become at tracing, analyzing, and writing these loops.

4.4 Nested Iteration

In Unit 3, you learned about nested if statements. Now, you will learn about how to trace through nested for loops. A nested for loop is a for loop inside another for loop and is very useful when traversing 2D Arrays, which you will learn about later in the course. The inner loop must complete all its iterations before the outer loop can move on to its next iteration. Here is an example of a nested for loop:

int rows = 5;

for (int i = 1; i <= rows; i++) {

for (int j = 1; j <= i; j++) {

System.out.print("*");

}

System.out.println();

}

The output of this nested for loop is

*

**

***

****

*****

Let's analyze how we created this pyramid of asterisks. The first line declares an integer variable called rows and initializes it to the value 5. This variable determines the number of rows in the pyramid. Line 2 declares an integer variable i and initializes it to 1. It also starts a for loop that will continue to execute as long as i is less than or equal to rows (5). This outer for loop will iterate rows number of times. Line 3 declares an integer variable j and initializes it to 1. It also starts a nested for loop that will continue to execute as long as j is less than or equal to i. The inner for loop will iterate i number of times for each iteration of the outer loop. This means the inner loop will iterate i number of times, five times, since the outer loop will iterate five times.

Line 4 prints out a "*" (asterisk) character to the console each time the inner loop iterates. For the first iteration of the outer loop, j is equal to 1 and i is equal to 1, so the inner loop only runs once and only one asterisk is printed. Line 5 closes the inner for loop with a curly bracket. Line 6 creates a new row using the println() function, and runs only for the outer loop. After line 7, the outer loop is run again, this time with i being 2, and the whole process starts over, and this time the inner loop runs twice, so two asterisks are printed. It is highly recommended to use a tracing table for a nested for loop because there is a lot of information to keep track of.