Algorithms with Selection and Repetition

Think about how you actually get ready for school. You do not follow the exact same list every day. If it is raining, you grab an umbrella; if it is not, you leave it. You brush your teeth until they feel clean, however long that takes. Your routine reacts to the situation.

Every algorithm you have seen so far could not do that. In Topic 1.1, an algorithm was a list of steps done one at a time, in order: sequencing. Every Java program in Unit 1 worked the same way: each statement ran exactly once, from top to bottom, no matter what. A pure sequence has no way to say “only sometimes” or “keep going until.”

Real algorithms need two more kinds of steps. Together with sequencing, they are the three building blocks of algorithms, the only pieces you need to describe any algorithm:

• Sequencing: steps are done one after another, in order.
• Selection: the algorithm makes a decision and chooses which step to do next. “If it is raining, take an umbrella” is selection. Another name for it is decision making.
• Repetition: a step, or a group of steps, is done again and again until a goal is reached. “Brush until your teeth are clean” is repetition. Another name for it is looping, and the repeated steps are called a loop.

Now change one thing: the day. On a sunny day, the umbrella step is skipped, so the routine does steps 1, 3, and 4. On a day when brushing takes longer, step 3 simply repeats more times. The written algorithm is the same on every day, but what actually happens changes with the situation. A pure sequence could never do that; it always does the same steps the same number of times.

Selection lets an algorithm handle different situations. But think back to Topic 1.1: a computer is a literal follower. It cannot weigh options or use judgment. So how can it “decide” anything?

The trick is to make every decision a question with exactly two possible answers: true or false. “Is it raining?” is either true or false. A literal follower can check it and then do what the algorithm says to do for that answer. Selection happens when the choice of how an algorithm continues is based on a true-or-false decision. The question being checked is called the condition.

In written language, selection usually looks like one of these two shapes:

• Do something, or skip it: “If condition, then do this step.” When the condition is false, the step is skipped and the algorithm moves on.
• Choose between two steps: “If condition, then do this step; otherwise, do that step.” Exactly one of the two steps happens.

Either way, after the decision is made, the algorithm continues with the next step in the sequence.

Now a decision you have already used without seeing it. Math.abs from Topic 1.11 returns a number’s absolute value: its distance from zero. You can describe the result it produces as an algorithm with a decision:

1. If the number is less than 0, the answer is the number with its sign flipped; otherwise, the answer is the number itself.

Test that description against the real method:

System.out.println(Math.abs(-7));
System.out.println(Math.abs(4));
System.out.println(Math.abs(0));

7
4
0

All three outputs match the written algorithm. We are not looking inside Math.abs here, only describing what it produces. The point is that a method you called in Unit 1 behaves like an algorithm with selection: its result depends on a true-or-false decision about its input.

Suppose you are saving up for $50 headphones, and you put $15 from your paycheck into savings each week. How many weeks will it take? You could work it out first and write that many steps. But if the price or the paycheck changes, the steps are wrong. In Unit 1, the only way to do something several times in Java was to write the statement several times, just like the “stir, stir, stir” recipe from 2.1.1.

Repetition means doing the same steps over and over until you get the result you were aiming for. Instead of guessing how many times, the algorithm states the goal and checks it: “Add $15 to savings until savings is at least $50.” The steps that repeat form a loop. Each time through the loop, the follower does the repeated steps and then checks whether the goal has been reached. If not, it goes around again. If so, the loop ends and the algorithm moves on to the next step.

Look closely at that check: “Is savings at least $50?” It is a true-or-false question, just like the condition in a selection. Every loop contains a decision about whether to keep going.

Now vary the starting point. Suppose you already have $20 when you begin, so step 1 says “Set savings to $20.” The first pass brings savings to $35 (false), and the second brings it to $50 (true; $50 is at least $50). The loop stops after only 2 passes. Same loop, same goal, different situation, different number of passes. That is exactly what repetition is for.

Sometimes the goal is a count. “Do 10 jumping jacks” can be written as a loop that keeps track of how many are done: (1) Set count to 0. (2) Repeat: do a jumping jack, then add 1 to count, until count is 10. The goal “count is 10” is reached after exactly 10 passes.

1. Set savings to $0.
2. Repeat: spend $5 from savings, until savings is at least $50.

In Topic 1.1 you represented algorithms in two ways: as numbered written steps and as a flowchart, where each step is a box and the arrows show the order. Those flowcharts were straight lines: one arrow in, one arrow out, from Start to Stop. A decision breaks that pattern, because after it the algorithm can go two different ways. How do you show that?

In a flowchart, a decision is drawn as a diamond, called a decision diamond. The condition is written inside it, and two arrows leave it: one labeled true and one labeled false. In the diagrams below, the diamond is drawn with pointed ends like < this >, regular steps are in square brackets, and Start and Stop are in parentheses. Here is the umbrella step from 2.1.1:

         ( Start )
             |
             v
    < Is it raining? >
      |            |
     true        false
      |            |
      v            |
 [Take umbrella]   |
      |            |
      v            v
     [Walk to school]
             |
             v
         ( Stop )

Follow it on a rainy day: the condition is true, so take the left arrow to “Take umbrella,” then continue to “Walk to school.” On a dry day, take the false arrow, which goes straight to “Walk to school,” skipping the umbrella. Both paths come back together, because after the decision the algorithm continues in sequence.

A loop is shown with an arrow that points back up to an earlier step. The decision diamond checks the goal: one arrow leaves the loop, and the other goes back around. Here is the savings algorithm from 2.1.3:

        ( Start )
            |
            v
   [Set savings to $0]
            |
            v
        [Add $15] <------+
            |            |
            v            | false
 < Savings at least $50? >
            |
            | true
            v
        ( Stop )

The false arrow leaves the right side of the diamond and climbs back to “Add $15.” That backward arrow is the repetition. When the condition is finally true, the downward arrow leads out of the loop.

In written language, you have already seen “If …, then …; otherwise, …” and “Repeat … until ….” A third way, which matches a flowchart arrow for arrow, writes the backward arrow as a “go back” instruction:

1. Set savings to $0.
2. Add $15 to savings.
3. If savings is less than $50, go back to step 2.
4. Stop.

         ( Start )
             |
             v
 [Take one step forward] <---+
             |               |
             v               | false
   < Are you at the door? >--+
             |
             | true
             v
      [Open the door]
             |
             v
         ( Stop )

Back in Topic 1.1, you saw that the same steps in a different order can give a different result: socks before shoes, not after. That was about sequencing alone. Now an algorithm can have decisions and loops too, and the question becomes: does it matter where they go?

It does. Where you place each step, each decision, and each loop helps decide what the algorithm produces. A decision checks the situation at the moment it is made, so a step placed before the decision can change the answer. A loop’s check can come before or after the repeated steps, and that changes how many times they run.

Now vary the building block: move a loop’s check. Compare two ways to water a plant:

• Check after: Repeat: pour a cup of water, until the soil is wet.
• Check first: Check whether the soil is wet; if it is not, pour a cup of water and check again.

When the soil starts out dry, both pour until it is wet. But suppose it rained last night and the soil is already wet. The check-after version pours a cup anyway, because it does the repeated step before it ever checks. The check-first version pours zero cups. Placing the check before or after the repeated step changes the outcome in exactly this kind of edge case.

Order matters in Java too. Even in Unit 1 programs, which only use sequencing, swapping two statements can change the result. These two snippets use the compound assignment operators from Topic 1.6 on the same starting value:

int points = 10;
points += 5;
points *= 2;
System.out.println("Points: " + points);

Points: 30

int points = 10;
points *= 2;
points += 5;
System.out.println("Points: " + points);

Points: 25

In the first snippet, points goes 10 → 15 → 30: the bonus of 5 is added and then doubled along with everything else. In the second, points goes 10 → 20 → 25: the bonus is added after doubling, so it counts only once. Neither is wrong; they are different algorithms, and the order you choose must match what you want to happen.

int score = 100;
score += 50;
score *= 2;
System.out.println("Final score: " + score);

int score = 100;
score *= 2;
score += 50;
System.out.println("Final score: " + score);

Real algorithms usually combine all three building blocks, often with a decision inside a loop. Here is one you already know the result of: finding where a letter first appears in a word, which is what indexOf from Topic 1.15 reports.

To find the first "p" in "hopper":

1. Set position to 0.
2. Repeat these steps until the search is done:
   • If position is past the last letter, the answer is -1 and the search is done.
   • Otherwise, if the letter at position is "p", the answer is position and the search is done.
   • Otherwise, add 1 to position.

The building blocks: step 1 then step 2 is sequencing; step 2 is repetition; and each pass makes decisions (first “is position past the end?”, then “is this letter a p?”). Recall that the letters of "hopper" sit at indices 0 through 5:

index:  0 1 2 3 4 5
letter: h o p p e r

Trace it:

The search stops at position 2, the first "p", and never looks at the second "p" at index 3. Searching for "z" would find no match at positions 0 through 5; then position becomes 6, which is past the last letter, so the answer is -1.

Order matters here as well. The “past the last letter?” decision comes first in each pass for a reason: if the algorithm tried to look at the letter at position 6 first, there would be no letter there to look at. In Java, asking for a character that does not exist causes a run-time error, as you saw with substring in Topic 1.15.

Now check the written algorithm against Java:

String word = "hopper";
System.out.println(word.indexOf("p"));
System.out.println(word.indexOf("z"));

2
-1

Both results match the trace. We are not claiming this is exactly how Java’s indexOf is written inside; the point is that its behavior is described by an algorithm that uses sequencing, selection, and repetition together. Later in this unit, you will learn the Java statements that let you write decisions and loops like these yourself.

• Every algorithm is built from three building blocks: sequencing (steps in order), selection (decision making), and repetition (looping).
• Selection chooses how an algorithm continues based on a condition, a question that is either true or false. Test decisions with a value right at the edge.
• Repetition repeats a process until a desired outcome is reached; a true-or-false check after each pass decides whether to go around again. If the repeated steps never move toward the goal, the loop never ends.
• Decisions and loops can be written in words (“if … otherwise …,” “repeat … until …,” “go back to step …”) or drawn in a flowchart with decision diamonds and backward arrows.
• The order of sequencing, selection, and repetition affects the outcome, because a decision only sees what has happened before it is checked.

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can name the three building blocks of algorithms and find each one in an everyday algorithm. Reread
• I can explain how selection uses a true-or-false condition and trace a decision, including an edge value. Reread
• I can trace a loop pass by pass and explain why a loop might never end. Reread
• I can show decisions and loops in written steps and in a flowchart with decision diamonds. Reread
• I can predict how changing the order of steps, decisions, and loops changes the result. Reread