L.4 & L.5: NESTED ITERATION & LOOP ANALYSIS

OBJECTIVES

I can:

• represent nested iterative processes

• compute statement execution counts of iterative statements

• compute informal run-time comparison of iterative statements

A nested loop has one loop inside of another. 

These are typically used for working with two dimensions, for example, the following code will print * in rows (horizontal) and columns (vertical). 

Notice that the inner loop (columns) runs as many times inside the outer loop (rows).

In other words, for each iteration of the outer loop, the inner loop will be re-started and must finish all of its iterations before the outer loop can continue to its next iteration.

QUESTION: How could we modify the code above to print a rectangle with 10 rows and 8 columns of *?

ANSWER: Change the header of the outer loop to for (int row = 1; row <= 10; row++) and the header of the inner loop to for (int col = 1; col <= 8; col++).

TRACING LOOPS

It is important to practice tracing through loops and analyzing them to determine how many times they run.

Remember to make a tracing table to keep track of all the variables, the iterations, and the output.

Let's see how a trace table could be used to predict what the code will do when we run it:

Remember that for your trace tables, iteration 0 is used to record the initial values before the loop begins.

COUNTING LOOP ITERATIONS

Loops can also be analyzed to determine how many times they run.  

This is called run-time analysis or statement execution count. 

How many *'s are printed out in the following loop? 

How many times does the loop run?

If the loop uses counter < limit, limit - 1 is the largest value that allows the loop to run.

If the loop uses counter <= limit, limit is the largest value.

So, in the example above, the largest value that allows the loop to run is 6 (largest value - 1) and the smallest value that allows the loop to run is 3 so this loop runs 6 - 3 + 1 = 4 times.

If you want to practice (optional), click "Loops" in the String-Thing game below. I don't recommend using the timer (at first), but clicking the options for "Backwards" and "Nested" is a good idea.

SUMMARY

• Nested iteration statements are iteration statements that appear in the body of another iteration statement.

• When a loop is nested inside another loop, the inner loop must complete all its iterations before the outer loop can continue.

• A trace table can be used to keep track of the variables and their values throughout each iteration of the loop.

• We can determine the number of times a code segment will execute with a statement execution count. This is called run-time analysis.

• The number of times a loop executes can be calculated using largestValue - smallestValue + 1 where these are the largest and smallest values of the loop counter variable possible in the body of the loop.

• The number of times a nested for-loop runs is the number of times the outer loop runs multiplied by the number of times the inner loop runs.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

L.4 & L.5 Evidence 

2) MC Exam Practice: This lesson has additional practice problems which can be found on the MC Exam Practice page with an answer key! Use ctrl + f to search for different objectives throughout the year. You could look at these questions now, or, save these practice questions for later and use them to review! The choice is yours.