📓2.1: Selection & Repetition Algorithms

Table of Contents

📖 This page is a condensed version of CSAwesome Topic 2.1

Algorithms with Control Structures

Every algorithm consists of a sequence of steps. Up until now, we have been writing code instructions one line at a time, which then gets executed by the computer in that sequential order by default. However, we can create more complex algorithms that do not follow the default sequential order.

🧱 Control structures are the building blocks of all algorithms: sequencing, selection/branching, and repetition/iteration.

image-small

In fact, it’s been proven that all problems that can be solved on a computer can be constructed by using just these three control structures!

Algorithms can implement control structures that:

  • 🔀 Branch the code execution into different paths using SELECTION

    Conditional decision-making (if, else if, else)

  • 🔁 Repeat a block of code using ITERATION

    Loops (while, for, for each)

Selection (Branching)

Selection
When a choice of how a process will proceed is based on a true or false decision.

🔀 In programming, an algorithm may take different paths (run different lines of code) depending on certain conditions.

🔎 Identify all the selection (decision/branching) phrases in the following algorithm:

  1. Wake up.
  2. Check your phone and the weather.
  3. If there is a text from your bestie, answer it.
  4. Brush teeth and shower.
  5. If it’s below 50 degrees, wear a sweater over your polo.
  6. Otherwise, pack the sweater in your bag just in case.
  7. Check if you have homework due. If so, pack it in your bag.
  8. Put on your sunglasses if it’s sunny.
  9. Leave for school.

HINT: Selections are made based on a true or false decision. Look out for the word "if", and sometimes "otherwise", to identify selections.

Repetition (Iteration)

Repetition
When a process repeats itself, or iterates, until a specified condition is met.

🔁 In programming, repetition is achieved through loops, which are code blocks that execute again and again until a desired outcome is reached.

🔎 Identify all the repetition (iteration) phrases in the following algorithm:

  1. Wake up.
  2. Snooze for 5 more minutes. Repeat waking up and snoozing for the next 15 minutes.
  3. If there is a text from your friend, answer it. Do this for all of your texts.
  4. Brush teeth and shower.
  5. Check if you have homework due. If so, pack it in your bag.
  6. Keep packing items until your bag is ready.
  7. Leave for school.

HINT: Repetition is when a process repeats itself until a desired outcome is reached. Look for the words "repeat", "all", or "keep" to identify repetition.

Planning with Pseudocode & Flowcharts

For complex problems, it is important to plan your solution before writing code.

  • Pseudocode is a simplified, informal way of describing the steps in an algorithm in a human language like English but following the sequence, selection, and repetition structure of a programming language.
  • Flowcharts are diagrams that represent the steps in an algorithm. Selection is usually represented as a triangle in a flowchart, and arrows are used to show repetition.

image-small

The order in which sequencing, selection, and repetition are used contributes to the outcome of the algorithm.

To understand why ORDER MATTERS, consider this pseudocode algorithm for buying a birthday gift:

  1. Initialize total amount of money to spend.
  2. Repeat while still have money in total:
    • If total more than $25, buy a gift card and subtract 25 from total.
    • If total more than $10, buy a small cake and subtract 10 from total.
    • If total more than $5, buy some candy and subtract 5 from total.
    • If total more than $1, buy a card and subtract 1 from total.
    • Otherwise, give them the change.

💬 Decide what the outcome will be if you have $16 to spend, based on the order of the steps and the conditions. What if you had $22?

Afterwards, switch the order of some of the steps and discuss how the outcomes might change.

Group Challenge: Algorithm Design

🍫 In small groups, design an algorithm for a common problem: choosing a snack. Write pseudocode that includes both selection and repetition, and then draw a flowchart.

Make it customized to your own preferences and experiences!

image-small

Examples:

  • If there are Oreos today, grab one immediately and head back to class.
  • If there are no good options in the Upper School lounge, go check the Middle School snack shelves.
    • You may want to consider every item in both snack areas, or search all the leftover candy in your locker, before deciding.
  • If there is something salty, like Cheez-its or Goldfish, grab an extra one for Mrs. Walter.

Summary

  • (AP 2.1.A.1) The building blocks of algorithms include sequencing, selection, and repetition.
  • (AP 2.1.A.2) Algorithms can contain selection, through decision making, and repetition, via looping.
  • (AP 2.1.A.3) Selection occurs when a choice of how the execution of an algorithm will proceed is based on a true or false decision.
  • (AP 2.1.A.4) Repetition is when a process repeats itself until a desired outcome is reached.
  • (AP 2.1.A.5) The order in which sequencing, selection, and repetition are used contributes to the outcome of the algorithm.

Acknowledgement

Content on this page is adapted from Runestone Academy - Barb Ericson, Beryl Hoffman, Peter Seibel.