## 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 loop: a typical looping construct designed to make it easy to repeat a section of code using a counter variable. The for loop combines the creation of a variable, a boolean looping condition, and an update to the variable in one statement. Below is an example of what format you would expect to see in other programming languages.

``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:

• Use a "repeat while" loop in a program to implement an algorithm that processes all elements of an array.
• Write code that implements a linear search on an unsorted array of numbers.
• Write code to find the minimum value in an unsorted list of numbers.
• Explain how binary search is more efficient than linear search but can only be used on sorted lists.

## 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.

## Introduced Code

• output arrayOfRandom:Get(index)
• repeat while index <= arrayOfRandom:GetSize() - 1

## 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:

• You may refer to the "first" and "last" cards in the row as part of your instructions.
• You may also give an instruction to move a hand some number of cards (or positions) to the left or right.
• You can give an instruction to put a card down on the table in one of the open positions, or put it back where it was originally picked up from.

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.

## 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:

• Reset the value of the variable "index" to 0
• Add a loop that references every index in the Array
• Add an if-statement inside the loop that displays every value in the Array greater than 50

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:

• Declare a boolean called "bool"
• Reset the "index" variable to 0
• Add an if-statement inside the "repeat while" loop to check if the value of the Array at the current index is 5.
• If the value is equal to 5, set "bool" to true. Otherwise, set "bool" to false.
• Output the updated "bool" variable
• Test your code to make sure it is working as you intend. An example output is below.

``````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:

• Add an if-statement inside the loop to increment fiveCount if the value is equal to 5. (Hint: this will be exactly the same as the if-statement you wrote in the previous level, but will run different code inside the if-statement. Also, you won't need the "else" condition).
• Run and re-run your code to make sure that it's accurately counting the number of 5's in the array. Since the Array is getting a random set of values every time you run the program, you might have to run it a bunch of times to thoroughly test it. Make sure you get it to run at least once when no 5's appear in the Array.
• Finally, change the first loop in the program to add 100 items to the array instead of 5. Since there are so many values, you should also comment out (using "//") the statement of "output arrayOfRandom:Ge(index)." Your code should still work to count the number of 5's, no matter how big the original array is!

## 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:

• The list does not contain any 5's; you need to display "false"
• The list contains at least one 5; you need to display "true"

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.

• Run the starter code to verify that it works correctly.
• Create a new action named "search." Note: Remember that we need to establish formal code structure with "class Main" and "action Main" when we start writing actions
• Move the code that checks for a 5 inside the action. Note: You must move the boolean variable inside the action as well, or it won't reset each time you call the action!
• Call the action to make sure your code still works. The actual behavior will be the same as when you ran it the first time. The difference now is that you're calling an action to do it.

## 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.

• Add a parameter to the search action called list
• Modify the code inside the action so that it loops over list (the parameter) instead of only over "arrayOfRandom1"
• Call your action with each of the Arrays provided at the top of the program

#### 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.

• Add a second parameter to your search action to represent the item to search for. This example uses the name "searchValue."
• Update the code inside the action to check for "searchValue" instead of 5.
• Call your search action to search for different values inside of each Array.
• The output statement is now inaccurate. Change it to say "Array has searchValue: " followed by the value in our boolean flag.

#### 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

• Create an action that accepts an Array as input.
• Create a "flag" variable and set its default value before looping through the Array.
• Loop through your Array with a "repeat while" loop that visits every index in the Array.
• Update your flag as necessary with every iteration of your loop.
• Display your flag at the end of the loop.
• Let's use this pattern to write an action that finds and displays the smallest value in an Array.
• Instead of using a true/false flag to indicate whether we found a value, we'll use a variable to keep track of the smallest value we've seen in the array so far.

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.

• Before programming, try to develop an algorithm that you could use to find the minimum value in an Array.
• Use the pattern outlined above as a guide.
• You'll want to use the minVal variable to keep track of the smallest value you've found so far.
• You'll need to write an if-statement that checks whether the current value in the Array is less than minVal. If it is, then update the smallest value.
• Run the code to ensure it is working as you intend.

## 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.

• 4.2.4D Different correct algorithms for the same problem can have different efficiencies. - Both linear search and binary search solve the same problem, but they have different efficiencies.
• 4.2.4E Sometimes more efficient algorithms are more complex. - Binary search is more efficient than linear search, but even though it might be easy to understand at a high level, it is much more challenging to write code for.
• 4.2.4F Finding an efficient algorithm for a problem can help solve larger instances of the problem. - The algorithms we wrote work for any size input.
• 4.2.4G Efficiency includes both execution time and memory usage. - Execution "time" here means number of operations that need to be performed in the worst case.
• 4.2.4H Linear search can be used when searching for an item in any list; binary search can be used only when the list is sorted. - Emphasis should be placed on the fact that binary search only works when the list is sorted. It's a fact often forgotten.

## Standards Alignment

• Computer Science Principles: 1.2.3 (A)
• Computer Science Principles: 4.1.1 (A, B, C, D)
• Computer Science Principles: 4.2.4 (D, E, F, H)
• Computer Science Principles: 5.1.2 (A, B)
• Computer Science Principles: 5.3.1 (K, L)
• Computer Science Principles: 5.5.1 (E, J)