Overview

This lesson introduces us to algorithms that process lists of data. Students will do two unplugged activities related to algorithms and program some of them themselves. The "repeat times" loop is re-introduced to implement these algorithms because it's straightforward to use to process all the elements of a list. The lesson begins with an unplugged activity in which students write an algorithm to find the minimum value in a hand of cards. They then move to an IDE to write programs that use loops and arrays. Students are shown how to use a "repeat while" loop to visit every element in an array. They then use this pattern to process an array in increasingly complex ways. At the end of the progression, students will write actions which process arrays to find or alter information, including finding the minimum value - a problem they worked on in the unplugged activity. Finally, an unplugged activity has students reason about linear vs. binary search and attempt to write pseudocode for a binary search.

Vocabulary

Note: the one vocab word for this lesson, the "for loop," is a concept that students are expected to know for the AP exam. However, Quorum does not have its own version of the for loop, so this lesson uses the "repeat while" loop instead, which can execute any algorithms/instructions a for loop can in a similar manner.
for(integer counter = 0; counter < 5; counter = counter + 1)

Again, the for loop above does not exist in Quorum. However, the form above represents the same as the following repeat while loop.

integer counter = 0

repeat while counter < 5

    counter = counter + 1
end

Goals

Students will be able to:

Purpose

There are many situations where we want to repeat a section of code a predetermined number of times. Although this can be done with a "repeat times" loop, we could alternatively use a "repeat while" loop by maintaining a variable to keep track of how many times the loop has executed. While there are many small pieces to keep track of, particularly the counter variable and incrementing, this allows us to use variables for our boolean condition. One of the most common uses of for loops in programming is to process arrays. The "repeat while" loop allows programmers to easily step through all the elements in an array. This basic pattern is at the core of many algorithms used to process a list of items. Whether you are looking to find a name in a list, find the closest store to your current location, or compute the total money in your account based on past transactions, a loop will probably be used at some point to access all the elements in a list.

Resources

Introduced Code

Getting Started

Introduce students to thinking about processing lists of information by recalling the FindMin problem they wrote an algorithm for in Unit 3 Lesson 2. In particular, introduce the common pattern of using a loop to visit every element in a list. Consider the following remarks when presenting these ideas to students.

Students might want help with language as they write out their algorithms. In particular, they might recognize that trying to clearly articulate which hands to use to pick up which cards is challenging. It's good if they recognize this. Here are some suggestions you can make:

To start, distribute the "Minimum Card Algorithm Activity Guide" resource and place students into pairs or small groups. Have students read the instructions and write their algorithm out on paper, then test it out with each other. If time permits, have them test out their algorithms with other groups or demonstrate one in front of the class.

Here are two examples of algorithms we might write. These are not the "correct answers" per se - there are many ways we might go about it - but they should give you the gist of what you might be looking for.

Min Card Sample Algorithms

SAMPLE ALGORITHM 1 (using a numbered list of instructions):

  1. Put your left hand on the first card in the row and your right hand on the card next to it.
  2. Pick up the card your left hand is on.
  3. Pick up the card your right hand is on.
  4. IF the card in your right hand is less than the card in your left hand,
  5. THEN swap the cards (so the smaller one is in your left hand).
  6. Put the card in your right hand back down on the table.
  7. IF there is another card in the row to the right of your right hand,
  8. THEN move your right hand one position to the right, and go back and repeat step 3 (with your right hand now on a new card).
  9. OTHERWISE: say "I found it!" and hold the card in your left hand up in the air.

Since we have learned about loops in the course, your students might write pseudocode with a loop construct in it.

SAMPLE ALGORITHM 2 (using a loop construct):

  1. Put your left hand on the first card in the row and your right hand on the card next to it.
  2. Pick up the card your left hand is on.
  3. Pick up the card your right hand is on.
  4. IF the card in your right hand is less than the card in your left hand,
  5. THEN swap the cards (so the smaller one is in your left hand).
  6. Put the card in your right hand back down on the table.
  7. IF there is another card in the row to the right of your right hand,
  8. THEN move your right hand one position to the right, and go back and repeat step 3 (with your right hand now on a new card).
  9. OTHERWISE: say "I found it!" and hold the card in your left hand up in the air.

Video: CS Principles: Processing Lists

Activity

This lesson focuses on Arrays like the previous two lessons have, but goes more in-depth into the usage of Arrays and introduces a few new actions of the Array class. Additionally, loops are essential to this lesson, as they are extremely useful in processing Arrays. As such, you may need to remind students of the concepts and syntax of the "repeat while" and "repeat times" loops. Consider the following concepts for review.

It's very common to want to repeat a set of commands a particular number of times. Recently, we have been using the "repeat while" to do this by creating a counting variable, setting the boolean expression, and incrementing the value of the counter by 1 each time. We've also used much simpler loop syntax "repeat times" before. The code syntax is very simple:

integer counter  = 0

repeat while counter < 5
   output "Hello World"
   counter = counter + 1
end

As you know, we can use variables as indexes in an array. We can take advantage of this fact to create a "repeat while" which visits every index in an array. You are going to use a loop of this kind to display all the values in an array.

integer counter  = 0

repeat while counter <= array:GetSize() - 1
   counter = counter + 1
end

Student Instructions

In this lesson, we will combine our knowledge of Arrays with our knowledge of loops to analyze the data stored within an Array. As such, you may want to briefly review those topics if you struggled with the lessons on either Arrays or loops.

Processing Arrays using Loops

Below the following starter code, add code that retrieves all information in the array and outputs to the console display. You need to use the following elements for this added code: the "counter" variable, the "repeat while" loop structure, and the Array class's "Get(integer location)" action.

Processing Arrays using Loops

Updating Values in an Array with a "repeat while"

Since we predefined our list in the challenge above to only have five elements, you may have simply repeated while the counter was less than five. However, there is a better method: using the Array class's "GetSize" action. Using this, we set up our loop to work no matter what size the Array is. Just remember that the "GetSize" action returns the number of elements, but the last index will actually be one less than the number of elements because the first index starts at 0. A template for this type of loop is shown below.

Array<integer> myArray
integer counter = 0

repeat while counter <= myArray:GetSize() - 1
    counter = counter + 1
end

The "repeat while" loop above is actually so common that we will rarely deviate from this loop setup.

This "repeat while" setup basically means "for every possible index in myArray..." and we use it as a basic building block for processing arrays. Common array-processing techniques like searching for a value, updating all values, or calculating simple stats on an array will all be completed using a "repeat while" written with the syntax above. In fact, we're going to see that happen right now as we use a loop to add 5 to every value in an array.

Adding to Every Value in an Array

Starter code has been provided that creates an Array of random values. You are also given an empty "repeat while" that loops over every index in the array. Add code inside this loop to add 5 to the value at every location in the Array.

Hint: Use the Array class's "Set(integer index, integer newValue)" and "Get(integer index)" actions together to update the value in a given index. Confirm that your code works by displaying the new values in your Array after they are updated within your loop. The values before the loop will already be output to the screen for you. Below is a sample result. Notice how, after the array has been processed, all of the values are 5 greater than the originals.

58
55
46
85
1
Integers after processing are:
63
60
51
90
6

Adding to Every Value in an Array

Additional Array Arithmetic

Modify the code above so that the processed integer value is about half of the original value instead of adding five. Since we're using integers, halving an odd number will drop the decimal point (i.e. 25 -> 12).

Additional Array Arithmetic

Using "repeat while" with if

Sometimes we want to find values in an Array that meet certain conditions. We can add an if-statement inside our loop to individually check every value within the Array. To practice this, we will create a loop that will display every value in the array greater than 50.

Starter code has been been provided that creates an Array of random values between 1 and 100.

Here's a quick list of what you need to do for this challenge:


Note: Because the original Array is being constructed with random values it's possible that it might not have any values greater than 50. As such, you should run the program a few times to make sure it works.

Using "repeat while" with if

Algorithms and General-Purpose Actions

Over the next several challenges we will be creating a general-purpose action to determine if a value is contained within an Array. Over the course of these challenges, keep an eye out for the general pattern we are using, because you'll get to use it again to create actions of your own.

To begin, we'll start simple. We'll write code that checks whether an Array contains a specific value. At every index, your program should display "true" if the value at that index is a 5 and "false" otherwise.

The starter code for this exercise is similar to previous exercises, but you'll notice that we generate integers between 1 and 5. You are also given the "repeat while" loop for your use.

Here are the steps for this challenge:


2
4
5
1
3
Is the value at the index position '5'?
false
false
true
false
false

Note: Because the original Array is being constructed with random values it's possible that it might not have any values equal to 5. As such, you should run the program a few times to make sure it works.

Algorithms and General-Purpose Actions

Counting Occurrences of a Value

Instead of displaying a true/false value for every item in the list, let's compute one value and display it. A common thing to want to do is count the number of times a value occurs. We can do this with a very small change to the code we've already got.

The following starter code is again similar to the previous exercises. We've also created a variable called fiveCount.

Here are the steps for this challenge:

Counting Occurrences of a Value

Output a Single True/False Value

Sometimes we don't care about the count and just want to know if the Array contains a 5 or not. Let's try to display a single true/false indicating whether the list contains a 5. There are two cases to consider:


Hint: One way to do this is to reference your "fiveCount" variable after the Array has been processed.

Copy and modify the previous exercise's code so that the program only outputs true if there is at least one occurrence of "5" in the Array. Also, modify the first loop to again only create 5 integers and again output each newly created integer, so you can check your results.

Output a Single True/False Value

Using a Boolean Variable as a Flag

We are going to do a challenge that is similar to the last exercise but, rather than counting the number of 5's in the array, we're going to use a different interesting programming technique for processing arrays that might prove useful to you in the future.

Using a Boolean Flag

The technique is generally referred to as using a boolean "flag." To understand this idea, think about how some mailboxes work: the flag starts down, and when a person wants to let the mail carrier know there is something to pick up, she puts the flag up to notify the mail carrier that there is outgoing mail in the box.

We can use a variable to do something similar when programming. Rather than incrementing an integer variable every time we find a 5 in the Array, we will use a boolean variable that acts like a flag. We will create the boolean before the loop and assign it false to start (flag is down). Then, as we process the Array, if we find a 5, set the boolean variable to true (put the flag up). Here is some pseudocode:

var flag = FALSE
FOR EACH item IN list
   IF (item EQUALS 5)
       flag = TRUE

DISPLAY (flag)

Notice that it doesn't matter if we find more than one 5; it will simply keep setting the flag to true. However, if there are no 5's, the if statement in the loop will never execute, and so the variable will remain the value it was initialized to, which was false.

Modify the previous code so that the boolean is assigned true only when a "5" occurs. Be careful not to reset the boolean value to false if an index's value is not "5." Then output the boolean flag after processing the Array to display whether or there was a "5" was in the list.

Using a Boolean Flag

Generalize Search by Making It Into an Action

You've just written code to search for a value in a list! If we could generalize this behavior, it might be useful to us in the future - it's probably something that we will want to do over and over again.

Over the next few Coding Challenges, we'll build up a very useful, general action for searching for any value in any list. But we'll do it one step at a time...

The following is the starter code for the next few exercises. This code creates three Arrays, with each Array named slightly differently. For the first exercise, you only need to consider "arrayOfRandom1."

use Libraries.Containers.Array
use Libraries.Compute.Random

Random random
Array<integer> arrayOfRandom1
Array<integer> arrayOfRandom2
Array<integer> arrayOfRandom3

 integer index = 0

   repeat 10 times
       integer randomInt = random:RandomIntegerBetween(1, 10)
       arrayOfRandom1:Add(randomInt)
       randomInt = random:RandomIntegerBetween(1, 10)
       arrayOfRandom2:Add(randomInt)
       randomInt = random:RandomIntegerBetween(1, 10)
       arrayOfRandom3:Add(randomInt)
   end

output "Did we have '5'?:"
boolean five = false
index = 0
repeat while index <= arrayOfRandom1:GetSize() - 1
   if arrayOfRandom1:Get(index) = 5
        five = true
   end
   index = index + 1
end

output five

Here are the requirements for this step.

Generalize Search

Generalize Search by Making It Into an Action - Part 2

Right now, our action just searches for a 5 in "arrayOfRandom1." We would like to be able to use this action to search through any Array, so we will be adding a parameter to allow us to specify which Array should be searched.

Generalize Search by Making It Into an Action - Part 3

In order to make a general search action, we should be able to search for any value, not just 5. We can do this by making the value to search for a parameter as well.

Reusing an Action Pattern: Find Minimum

Nice work! You've just written an action that implements an algorithm to process an array! If you feel comfortable with the basic pattern you used to create this action, you can quickly create actions for many other useful algorithms that work on arrays.

Basic Action Pattern

Starter code has been provided which outlines and calls findMinVal with different inputs. Your job will be to finish writing the action.

Here are the instructions for this step.

Find Minimum

Unplugged Activity: Card Search Algorithm

Now that students are finished with the Coding Challenges, distribute the "Card Search Algorithm Activity Guide" resource. Then present them the following as a prompt.

In the lesson we programmed a linear search (scan all the values in the list from beginning to end until you find what you're looking for). "Binary search" uses a different algorithm, that is faster, but requires that the list be in sorted order ahead of time, whereas a linear search will work for any list. Demonstrate why this algorithm can only be performed on sorted arrays and justify the fact that it is faster.

Note: The wrap-up for this lesson focuses primarily on the outcomes from the Card Search activity.

Wrap Up

The only algorithms the CSP framework mentioned by name are "linear search" and "binary search." Students should be able to reason about an algorithm's "efficiency." They should understand the connection (and differences) between designing an algorithm and actually writing (implementing) the algorithm in code.

When you talk about how "long" or how much "time" an algorithm takes to run, time is usually a measure of the number of operations a computer needs to perform to complete the task. You can measure the amount of time it takes to run an algorithm on a clock, but it's often not a useful measure, because the speed of the computer hardware obscures whether the algorithm is good or not.

There are several essential knowledge statements from the framework that directly tie to information about algorithms, efficiency and linear vs. binary search, which we'll use.

Wrap Up Activity

Have students pair up with a peer and take one of the 5 statements (D, E, F, G, H) listed below, which are taken directly from the CSP Framework under "4.2.4 Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]"

Come up with a brief (60 second) explanation of that statement and relate it to something you experienced as part of this lesson.

Standards Alignment