Skip to main content

Section 2.5 Loop Algorithms

90 minutes
Quick Links: 2.5.1, 2.5.2, 2.5.3, 2.5.4, 2.5.5
In this lesson, we will practive developing and comparing algorithms using repetition and selection. We will learn some common algorithms and patterns using loops that can be used to solve problems, for example calculating the sum or average of a group of numbers or finding the maximum or minimum value in a group of numbers.

Subsection 2.5.1 Developing Algorithms

The building blocks of algorithms are sequencing, selection, and repetition. With these three control structures, almost any problem can be solved.
For example, in the last lesson, we saw an algorithm that printed out the even numbers from 0 up to 10. We can easily adapt that algorithm to print out the odd numbers from 0 up to 20 by changing the condition in the selection and iteration statements. Try it below.

Subsection 2.5.2 Common Algorithms

Subsubsection 2.5.2.1 Sum and Average Accumulator Algorithms

One common algorithm is to compute the sum or average of a set of numbers. This is called the accumulator pattern; it uses a loop and an accumulator variable to keep track of the running total as each number is added. The accumulator pattern has 4 steps:
  1. Initialize the accumulator variable before the loop.
  2. Loop through the values.
  3. Update the accumulator variable inside the loop.
  4. Print or use the accumulated value when the loop is done.
For example, this loop calculates the sum of 0 through 100 using range(101) since this generates numbers up to 101 but not including 101. The sum variable is the accumulator variable and number is added into the sum each time through the loop. Then, the average is calculated by dividing the sum by the number of values. 
sum = 0
for number in range(101):
    sum += number
print("The sum of 0 through 100 is", sum)
average = sum / 100
print("The average of 0 through 100 is", average)
Try the accumulator practice below.

Activity 2.5.2.

The following program has the correct code to return the average of 10 random numbers, but the code is mixed up. Drag the blocks from the left into the correct order on the right. You will be told if any of the blocks are in the wrong order or are indented incorrectly.

Activity 2.5.3.

Complete the code below to calculate the sum and average of 2 to 5 (including 5). Use the accumulator pattern to calculate the total, then calculate the average. Try Code Lens to see the variable values change as the program runs.

Activity 2.5.4.

The following code calculates the sum and average of numbers entered by the user. Input-controlled loops usually use while loops. Since we do not know how many numbers the user will enter, we will use -1 to end the loop and count the number of inputs.

Subsubsection 2.5.2.2 Minimum and Maximum

Another common algorithm is to find the minimum or maximum value in a group of numbers. This is a variation of the accumulator pattern where there is an if-statement inside the loop that tests each value being considered in the loop. To determine the minimum or maximum value, the algorithm uses a variable to store the current minimum or maximum value. The algorithm loops through the sequence of numbers and updates the minimum or maximum value if it finds a number that is lower or higher than the current minimum or maximum. This pattern can also be used to search for a specific value in a group of numbers. For example, this loop chooses 10 random numbers and finds the minimum value among them. Click on next to see each step.

Activity 2.5.5.

Click on Next to see each step of the loop!

Activity 2.5.6.

The following program has the correct code to find the maximum of positive numbers entered by the user, but the code is mixed up. Drag the blocks from the left into the correct order on the right. You will be told if any of the blocks are in the wrong order or are indented incorrectly.

Activity 2.5.7.

Run the following code to see the minimum algorithm in action. Then, change the code to find the maximum value instead of the minimum.

Subsubsection 2.5.2.3 Divisibility

Another common algorithm is to check whether a number is evenly divisible by another. The algorithm uses the mod operator (%) to determine whether the remainder of the division is zero. We’ve already used this to see if a number is even or odd by checking if the number is divisible by 2. But we can generalize this algorithm to check for divisibility by any number.

Activity 2.5.8.

Change the code below which checks whether a number is even to instead check if a number is divisible by 5. If it is, print "Divisible by 5", otherwise print "Not divisible by 5".

Subsection 2.5.3 Comparing Algorithms

A problem can be solved with different algorithms. A simple example is the problem of calculating the sum of a list of numbers. We can use for loop or a while loop which look very different to solve the same problem. Compare the two algorithms below. Do they produce the same output?

Activity 2.5.9.

Compare the two algorithms below. Do they produce the same output? Change each algorithm to calculate the sum of numbers from 1 to 10 instead of 1 to 5. Do they still produce the same output?

Activity 2.5.10.

The following for loop prints the numbers 0 to 6. Rewrite it as a while loop that does the same thing. Don’t forget the 3 steps of writing a while loop: initialize, test, and update the loop variable.

Activity 2.5.11.

Which Boolean expression is equivalent to the following conditional statement? 
if x < 5:
    small = True
else:
    small = False
  • small = x > 0
  • No. This expression is true for all positive values of x, but the original conditional statement is only true for values less than 5.
  • small = not x >= 5
  • Correct! An expression is equivalent if it always produces the same result. The expression not (x >= 5) is true exactly when x < 5.
  • small = not x > 5
  • No. This expression is true for values less than or equal to 5, but the original conditional statement is true for values less than 5.
  • small = x <= 5
  • No. This expression is true if x = 5, but the original conditional statement is false if x = 5.
Sometimes two algorithms may produce the same output but have different side effects. Side effects are anything an algorithm changes besides producing its main output, for example changing a variable’s value or changing something on the screen.

Activity 2.5.12.

As we saw above, the following two algorithms produce the same output. Which line of code is a side effect that one of the algorithms has that the other does not? 
# Algorithm A
total = 0
for number in range(1, 6):
    total += number
print(total)

# Algorithm B
total = 0
number = 1
while number <= 5:
    total += number
    number += 1
print(total)
  • total += number
  • No, both algorithms update the variable total.
  • while number <= 5:
  • Although only Algorithm B has a while loop, the program state doesn’t change here, so it’s not really a side effect.
  • total = 0
  • No, both algorithms initialize the variable total to 0.
  • print(total)
  • No, both algorithms print the value of the variable total.
Sometimes side effects are unintended and can cause problems. For example, if you are playing a game and finish a level, and you notice that your score was reset to 0 in the next level, that may be an unitended side effect or bad design.

Activity 2.5.13.

Given the two algorithms below, do they have the same outputs and side effects? 
# Algorithm A
for i in range(3):
    print("Hello")

# Algorithm B
count = 0
while count < 3:
    print("Hello")
    count += 1
  • Same outputs and same side effects
  • No, algorithm B has the additional side effect of updating the variable count.
  • Same outputs and different side effects
  • Yes, the two algorithms produce the same output (printing "Hello" 3 times) but have different side effects (Algorithm A doesn’t update any variables, while Algorithm B updates the variable count).
  • Different outputs and different side effects
  • No, both algorithms produce the same output (printing "Hello" 3 times).
  • Different outputs and same side effects
  • No, both algorithms produce the same output (printing "Hello" 3 times).

Subsection 2.5.4 Coding Challenge: Guessing Game

In the following coding challenge, you will code a guessing game where the computer picks a random number from 0-100 and the user has to guess it. After each guess, the computer will give clues like “Too high” or “Too low”. We encourage you to work in pairs on this challenge.
Before you start coding, play the guessing game a few times in pairs. One student should play the part of the computer and think of a random number between 0 and 100. The other student should try to guess the number. After each guess, the student playing the computer should give clues like “Too high” or “Too low” until the correct number is guessed. Count the number of guesses you took. Switch roles and play again.
What is a good guessing strategy for guessing a number between 0 and 100? What was your first guess? One great strategy is to always split the guessing space into two and eliminating half, so guessing 50 for the first guess. This is called a divide and conquer or binary search algorithm because it divides the search space in half with each guess. If your guess is between 0-100, you should be able to guess the number within 7 guesses.

Project 2.5.14. Guessing Game Coding Challenge.

Follow the pseudocode below to code the guessing game. Work in pairs. What’s the loop variable for this program? Can you identify the 3 steps of writing this loop with respect to the loop variable?
  1. Choose a random number from 0-100
  2. Get the first guess
  3. Loop while the guess does not equal the random number:
    • Increment a count of the number of guesses
    • If the guess is less than the random number, print out “Too low!”
    • If the guess is greater than the random number, print out “Too high!”
    • Get a new guess (save it into the same variable)
  4. When the loop ends (guess equals random number), print "You got it" and the number of guesses it took.
An ungraded extension to this challenge is to test whether the user got it in 7 guesses or less and provide feedback on how well they did.

Activity 2.5.15. Conditionals Reflection.

Consider the conditional (if) statements in your project code above. Identify the boolean expressions in the conditional statements by writing them below. Explain what happens if they are true or false. Instead of the two separate if statements, try rewriting it as a single if/else statement below. Would the program still work the same way? Explain why or why not.

Activity 2.5.16. Infinite Loop Reflection.

Consider the first iteration statement in your project code above (the while loop). Identify the loop variable by writing it below. Identify the number of times the body of your iteration statement will execute. Describe a condition or error that would cause your iteration statement to not terminate and cause an infinite loop. Explain how the loop condition could be modified to cause an infinite loop.

Activity 2.5.17. Comparing Algorithms Discussion.

Discuss the 3 algorithms below in pairs or groups. Do they produce the same output? Do they have the same side effects? Trace through them to determine what each prints out. 
# Alg A
total = 0
for number in range(1, 6):
    total += number
print(total)

# Alg B
total = 1
for number in range(2, 6):
    total += number
print(total)

# Alg C
total = 0
for number in range(5):
    total += number
print(total)

Subsection 2.5.5 Vocabulary Review

Activity 2.5.18.

You have attempted of activities on this page.
PrevTopNext