Lesson 15: Processing Arrays

Unplugged | App Lab

Overview

This lesson will probably take two days to complete. It introduces students to algorithms that process lists of data. The students will do two unplugged activities related to algorithms and program some of them themselves in App Lab. The for 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. Students then move to Code Studio to write programs that use loops and arrays. Students are shown how to use a for loop to visit every element in an array. Students use this pattern to process an array in increasingly complex ways. At the end of the progression, students will write functions 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.

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 while loop by maintaining a variable to keep track of how many times the loop has executed, there are many small pieces to keep track of. The for loop consolidates all of those pieces - counter variable, incrementing, and boolean condition - onto one line. One of the most common uses of for loops in programming is to process arrays. for loops allow 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.

Agenda

Getting Started (15 minutes)

Activity (30 minutes)

Activity 2 (20 Minutes)

Wrap-up (10 minutes)

View on Code Studio

Objectives

Students will be able to:

  • Use a for 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.

Preparation

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Students

Vocabulary

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

Introduced Code

Teaching Guide

Getting Started (15 minutes)

Teaching Tip

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.

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

Recall: Minimum Card Algorithm

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, rather than the jump command.

Opening:

Remarks

Remember in a lesson a while back when we wrote algorithms for playing cards using the "Human Machine Language"?

Notice how a row of cards is kind of like a list.

Today we’re going to begin to write code to process lists of data. Processing large lists of data is one of the most powerful things computer programs can do. Many of the most important algorithms in computer science have their roots in processing lists of data.

So as a warm-up today, lets think back to algorithms that process lists with a short activity.

Distribute: Activity Guide - Minimum Card Algorithm - Activity Guide

Setup:

  • Put students in pairs or small groups.
  • Students should:
    • Read the instructions (or you might want to read out loud as a class).
    • Write their algorithm out on paper and test it out with each other (or possibly other groups).
  • Test it out with other groups, or demonstrate one.

Teacher Reference: Min Card Sample Algorithms

For your reference here are some plain English 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):

Pick up the first card in your left hand.
FOR EACH card IN the row of cards (ALTERNATIVE: WHILE there are more cards in the row)
     Pick up the next card with your right hand.
     IF the card in your right hand is less than the card in your left hand,
           THEN swap the cards (so the smaller one is in your left hand).
           Put the (larger) card in your right hand back down on the table.
(after the loop) Say “I found it!” and hold the card in your left hand up in the air.

Transitional Remarks

The same kind of thinking that went into designing this algorithms can be applied to making working code as well.

Don't confuse thinking about the algorithm with actually writing code.

Today you'll get some practice writing code with loops and if-statements to process a list - skills that will help you write your own algorithms for lists.

Activity (30 minutes)

App Lab: Processing Arrays

Teaching Tip

In terms of pacing, the unplugged Activity Guide - Card Search Algorithm - Activity Guide could be done on a second day of class. It’s also likely that students will not finish all of the Code Studio levels for the lesson by the end of the first day, but you do not have to wait for every student to complete every level to run it. It’s reasonable to be done at any point after students have gotten halfway through the Code Studio levels (basically, after they’ve written code for linear search).

You might elect to use the next activity as a getting started activity on day 2 if most students are halfway through.

Activity 2 (20 Minutes)

Unplugged Activity: Card Search Algorithm

In the lesson students programmed 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 - 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.

Distribute: Activity Guide - Card Search Algorithm - Activity Guide

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

Wrap-up (10 minutes)

Goal

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.” Students should understand the connection (and differences) between designing an algorithm and actually writing (implementing) the algorithm in code.

Remarks

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, and which we’ll use in the wrap-up.

Activity:

Give each pair of students 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]”

  • Ask the pair to come up with a brief (60 second) explanation of that statement and relate it to something they experienced as part of this lesson.
  • Give students 3 minutes to think and discuss.
  • Do a whip-around, or put pairs together, or group by statement, and
    • Have each pair read the statement out loud.
    • Given their explanation of what it means.

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.

  • Processing Lists with Loops
  • 2
  • (click tabs to see student view)
  • Introduction to for Loops
  • 3
  • (click tabs to see student view)
View on Code Studio

Student Instructions

for Loop

It's very common to want to repeat a set of commands a particular number of times. Recently, we have been using the while loop 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 the for loop before, and we'll explain it more in-depth now. The for loop was created to wrap all of those components related to counting loops into a single line of code.

Programmers would typically read a loop for (var i = 0; i < 10; i++) out like this:
"for variable i starting at 0, while i is less than 10, i plus plus (or increment i by 1)"

Notice that in reading a for loop we still use the word "while".

You may notice that when you drag a for loop out from the toolbox that we've set it up for you with i as the variable.

Why is i the variable? [click to expand]

Using the single character i as the variable in a for loop has become a convention in programming for a variety of reasons. One reason is that for loops are often used when processing arrays - you can think of i as shorthand for index. But there is no reason why you have to use i if you don't want to. It's just a variable.

Do This:

  • Drag out the for loop.

  • Insert a console.log statement inside the for loop that displays i.

  • Try changing:

    • The condition to stop the loop (make it run longer).
    • The amount you change i by each time (try changing i++ to something like i += 5).
    • The starting value of i.
  • Printing an Array
  • 4
  • (click tabs to see student view)
View on Code Studio

Student Instructions

Print an Array with a for Loop

As you know, we can use variables as indexes in an array. We can take advantage of this fact to create a for loop which visits every index in an array.

In this for loop, the i eventually gets set to every possible index in the array. You are going to use a loop of this kind to display all the values in an array.

Do This:

Starter code is provided that adds several random values to an array.

  • Create a for loop that uses the syntax shown below (and above) to iterate through every index in the array.

  • Use console.log to display the contents of the array at each index.

  • Run the program to confirm it is displaying all the values.

  • Math and Arrays
  • 5
  • 6
  • (click tabs to see student view)
View on Code Studio

Student Instructions

Updating Values in an Array with a for Loop

The for loop you set up on the last level is actually so common that we will rarely deviate from this for loop setup.

This for loop 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 for loop written with the syntax above.

In fact, we're going to see that happen right now as we use a for loop to add 5 to every value in an array.

Do This:

Starter code has been provided that creates an array of random values. You are also given a for loop that loops over every index in the array.

  • Add code inside the loop to add 5 to the value at every location in the array.
    • Remember: myArray[i] refers to the element in the array at the current value of i.
  • Confirm your code works by displaying the values in your array before and after your loop. Below is a sample result. Notice how, after the array has been processed, all of the values are 5 greater than the originals.

View on Code Studio

Student Instructions

Divide by 2

In the last exercise, you updated every element in an array using a for loop. Let's get a little bit more practice with the pattern you used in the last exercise, this time creating the loop yourself.

Do This:

Starter code is provided which creates an array of random values.

  • Create a for loop that iterates over every index in the array.

  • Within your loop, add code that divides each value in the array by 2.

  • Use the provided console.log statements to confirm your program runs as expected. Below is an example of the expected outcome.

View on Code Studio

Student Instructions

for Loop with if

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

Do This:

Starter code has been been provided that creates an array of random values.

  • Add a for loop that references every index in the array.

  • Add an if statement inside the for loop that displays every value in the array greater than 5 using console.log

  • Note: Because the original array is being constructed with random values it's possible that it might not have any values greater than 5. Just run the program a few times to make sure it works. An example of the possible output is below.

View on Code Studio

Student Instructions

Algorithms and General-Purpose Functions

Over the next several exercises we will be creating a general-purpose function to determine if a value is contained within an array. Over the course of these exercises, keep an eye out for the general pattern we are using, because you'll get to use it again to create functions 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.

Do This:

The starter code is similar to past levels, but you'll notice that we use a loop to construct myArray rather than appending items one line at a time. You are also given the for loop you will use.

  • Add an if statement inside the for loop to check if the value of the array at the current index is 5.
  • If the value is equal to 5, write true to the console. Otherwise write false to the console.
  • Test your code to make sure it is working as you intend. An example output is below.

View on Code Studio

Student Instructions

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.

Do This:

Starter Code is similar to past levels. We've also created a variable called fiveCount.

  • Add an if statement inside the for loop to increment fiveCount if the value is equal to 5. (Note: this will be exactly the same as the if statement you wrote in the previous level. Just giving you more practice).

  • 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, if you'd like to, change the first loop in the program to add 100 items to the array instead of 10. Your code should still work to count the number of 5's, no matter how big the original array is!

View on Code Studio

Student Instructions

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

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

HINT: one way to do this is to reference your counter variable fiveCount after the array has been processed.

Do This:

We've pulled your code from the previous level so you can continue to add to it.

  • Add a console.log statement to display a single "true" or "false" indicating whether there is a 5 anywhere in the array.
Example output 1: One or more 5's Example output 2: No 5's
View on Code Studio

Student Instructions

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 a count every time we find a 5 in the array, we will use a variable that acts like a flag. We will create a variable 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 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 just 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.

Do This:

  • Implement the pseudocode above in JavaScript.
  • We've given you code that constructs an array of random values, and the standard for loop for looping over an array.
  • The output will be no different from the previous exercise, but you should still confirm that your program correctly identifies when a 5 is in the array.
One or more 5's No 5's
View on Code Studio

Student Instructions

Generalize search by Making It Into a Function

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 want to do over and over again.

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

Do This:

Note: We've provided new starter code that implements the pseudocode from the last exercise. It also creates two more arrays that we'll be using later for testing. For this level just worry about testArray.

  • Run the starter code to verify that it works correctly.
  • Create a new function. Name the function search.
  • Move the code that checks for a 5 inside the function. Note: You must move the boolean variable inside the function as well, or it won't reset each time you call the function!
  • Call the function 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 a function to do it.

(Steps are shown in code animation below.)

View on Code Studio

Student Instructions

Generalize search by Making It Into a Function - Part 2

Right now, our function just searches for a 5 in a global array called testArray. We would like to be able to use this function to search through any array, so we will be adding a parameter to allow us to specify which array should be searched.

Do This:

  • Add a parameter to the search function called list.
  • Modify the code inside the function so that it loops over list (the parameter) instead of testArray (the global variable).
  • Call your function with each of the arrays provided at the top of the program.

(These steps are shown in the code animation below.)

View on Code Studio

Student Instructions

General Search

In order to make a general search function, 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.

Do This:

  • Add a second parameter to your search function to represent the item to search for. This example uses the name searchValue.

  • Update the code inside the function to check for searchValue instead of 5.

  • Call your search function to search for different values inside of each array.

  • The console.log statement is now inaccurate. Change it to say "Array has searchValue: " followed by the value in flag.

(These steps are shown in the code animation below.)

View on Code Studio

Student Instructions

Reusing a Function Pattern: Find Minimum

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

Basic Function Pattern

  • Create a function 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 for 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 a function 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.

Do This:

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

  • 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.
  • Write code in the places indicated with comments to complete the function.
    • 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.

HINT: pseudocode [click to expand]

Here is some pseduocode that you should be able to implement.

minVal = first value in array 
for EACH value IN array
  if value < minVal
     minVal = value

display(minVal)

Standards Alignment

View full course alignment

Computer Science Principles

1.2 - Computing enables people to use creative development processes to create computational artifacts for creative expression or to solve a problem.
1.2.3 - Create a new computational artifact by combining or modifying existing artifacts. [P2]
  • 1.2.3A - Creating computational artifacts can be done by combining and modifying existing artifacts or by creating new artifacts.
4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
4.1.1 - Develop an algorithm for implementation in a program. [P2]
  • 4.1.1A - Sequencing, selection, and iteration are building blocks of algorithms.
  • 4.1.1B - Sequencing is the application of each step of an algorithm in the order in which the statements are given.
  • 4.1.1C - Selection uses a Boolean condition to determine which of two parts of an algorithm is used.
  • 4.1.1D - Iteration is the repetition of part of an algorithm until a condition is met or for a specified number of times.
4.2 - Algorithms can solve many but not all computational problems.
4.2.4 - Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
  • 4.2.4D - Different correct algorithms for the same problem can have different efficiencies.
  • 4.2.4E - Sometimes more efficient algorithms are more complex.
  • 4.2.4F - Finding an efficient algorithm for a problem can help solve larger instances of the problem.
  • 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.
5.1 - Programs can be developed for creative expression, to satisfy personal curiosity, to create new knowledge, or to solve problems (to help people, organizations, or society).
5.1.2 - Develop a correct program to solve problems. [P2]
  • 5.1.2A - An iterative process of program development helps in developing a correct program to solve problems.
  • 5.1.2B - Developing correct program components and then combining them helps in creating correct programs.
5.3 - Programming is facilitated by appropriate abstractions.
5.3.1 - Use abstraction to manage complexity in programs. [P3]
  • 5.3.1K - Lists and list operations, such as add, remove, and search, are common in many programs.
  • 5.3.1L - Using lists and procedures as abstractions in programming can result in programs that are easier to develop and maintain.
5.5 - Programming uses mathematical and logical concepts.
5.5.1 - Employ appropriate mathematical and logical concepts in programming. [P1]
  • 5.5.1E - Logical concepts and Boolean algebra are fundamental to programming.
  • 5.5.1J - Basic operations on collections include adding elements, removing elements, iterating over all elements, and determining whether an element is in a collection.

CSTA K-12 Computer Science Standards (2017)

AP - Algorithms & Programming
  • 3A-AP-14 - Use lists to simplify solutions, generalizing computational problems instead of repeated use of simple variables.
  • 3B-AP-10 - Use and adapt classic algorithms to solve computational problems.
  • 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
  • 3B-AP-12 - Compare and contrast fundamental data structures and their uses.
  • 3B-AP-14 - Construct solutions to problems using student-created components, such as procedures, modules and/or objects.