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.
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
Students will be able to:
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 trying 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.
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 searching for.
Since we have learned about loops in the course, your students might write pseudocode with a loop construct in it.
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
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.
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.
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 experience that right now as we use a loop to add 5 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
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).
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.
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.
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:
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.
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.
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.
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.
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.
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.
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.
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.
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 searching 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.
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.
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.