Overview

The lesson begins with a quick review of lists and loops before moving into the main activity. Here students explore the concept using pseudocode and optionally the Traversal Machine, a physical model of traversal using a for loop.

Goals

Students will be able to:

Purpose

Students are introduced to the concept of traversal using pseudocode and (optionally) the Traversal Machine. This unplugged lesson provides students a physical mental model they will be able to use when they transition to programming traversals in actual code.

Resources


Teaching Tip

Optional Materials and Substitutions: Like the previous explore lessons, this lesson is a guided activity with optional accompanying slides. The activity makes use of the Traversal Machine, a paper cut-out with a for loop and a sliding track. Whether or not you use the handout, the core of this activity is in writing and running pseudocode. The slides show Javascript-style pseudocode, and we have included Quorum-style pseudocode here. You can direct students to use either.

Instead of using the Traversal Machine, you can instead ask students to write pseudocode directly on paper or in a text editor. You can even have them write actual code in a blank project in Quorum Studio, but if you do, it's okay if student's code doesn't compile. For this lesson, it's only important that students explore the concept, rather than worry about the exact syntax of code.


Getting Started (5 mins)

Discuss: Review key vocabulary for lists and loops with students:

Activity

Guided Activity: The focus of today's lesson is an unplugged guided activity. You can optionally use the Code.org presentation slides for this lesson. Prompts below indicate when to move to a new slide. If you aren't using the slides, you can ignore these prompts.


Slide: Traversals Explore

Distribute: If you are using the Traversal Machine, hand them out to students and ensure they have the supplies listed on the slide. Otherwise, make sure students have access to pencil and paper, a text editor, or whatever alternative tools you choose to use for this lesson.

Note to Teacher: If you are using the Traversal Machines and are concerned about time or material management, the Traversal Machines can be prepared ahead of time. You only need one Traversal Machine per pair of students, and machines can be shared between classes.

There are three places to make cuts:

Say: Today we are going to learn about Traversals. Make sure you and your partner have all the supplies you need.


Slide: Do This

Do This: Write down this list:

temps = [77, 85, 89, 65]

Slide: What if...

Prompt: What if I want to know if a value is in a list? With a partner, discuss the method you would use to look for an item in a list.

Answer: Most likely, you would scan your list looking at each item until you found the correct one.


Slide: Computers are really good at checking things one by one.

Say: Computers are really good at checking things one by one. To do this, let's use a loop.


Slide: Get ready! Set up the Traversal Machine

Do This: Set up the Traversal Machine, or write down this pseudocode. Make sure to leave plenty of space open in the middle of the loop!

Note: Students use scissors make cuts as directed on the Traversal Machines. As noted before, this can all be done before class to save time.

integer i = 0
repeat while i < list:GetSize()
    integer element = list:Get(i)





    i = i + 1
end

Slide: This is where we assign the starting value...

Do This: Direct students attention to the Traversal Machines or to the first line of pseudocode as you describe the parts.

integer i = 0

Say: This is where we assign the starting value to the counter variable i. Usually we assign it to 0. What else starts with 0? The index of a list!

Note: In Javascript and Quorum, the index of a list starts at 0. You may want to remind students that on the AP Exam, pseudocode starts the index at 1.


Slide: This is the Boolean expression...

i < list:GetSize()

Say: This is the Boolean expression that is checked to see if the loop should continue to run. When working with a list, we want to access every element in the list, so we are going to keep the loop going until we have hit the size of the list.

Note: You may want to remind students that list:GetSize() evaluates to the length of a list, which will be different than the last index number. For example, in a list of three, the length is 3 and the index numbers are 0, 1, 2


Slide: Do This: replace list...

Do This: Replace "list" with the name of your list. In this case, we would replace it with "temps"


Slide: The counter variable i...

i = i + 1

Say: The counter variable i increases after each loop runs.


Slide: To access each element in the list...

Say: To access each element in the list, we are going to store the element in a variable inside the for loop. Let's try this out.

Click for animation.

Do This: If you're using the Traversal Machine, set up a variable baggy and give it the name element.

Whether you're using the Traversal Machine or pseudocode, you may opt to not use variable baggies at all in this lesson and instead have students keep track of variables separately, such as on a scrap piece of paper. In this case, the variable element is tracking the local variable that is inside of the for loop. With every round of the for loop, the variable will update.


NOTE: If you are not using the Traversal Machine, you can skip this slide and its related section.

Slide: Do this: Pull the index sheet up to assign i to 0.

Do This: Pull the index sheet up to assign i to 0.

Click for animation.

Say: Notice how the variable in the baggy has changed Each time the loop is executed, the variable i increases by one.

Note: For the following six slides, students will follow along with what's happening on the screen with their own Traversal Machines. Give students a few seconds to pull up the index sheet at each step.


Slide: Do This: Look at the list below.

Say: Look at our list. Right now, i = 0.

temps = [77, 85, 89, 65]

Do This: Evaluate the statement in the for loop to see what value is stored by the variable element.

Click through animation: There are six steps to click through. temps:Get(0) evaluates to 77 which is stored in the variable element.


Slide: Do This: Now pull the index sheet up one spot.

Do This: Now, evaluate the next iteration of the loop. If you're using the Traversal Machine, pull the index sheet up one spot. i now equals 1. Evaluate the statement inside the loop.

Click through animation: There are seven steps to click through. temps:Get(1) evaluates to 85 which is stored in the variable element.


Slide: Do This: Pull the sheet up again

Do This: Evaluate the next iteration again. If you're using the Traversal Machine, pull the index sheet up again. i now equals 2. Evaluate the statement inside the loop.

Click through animation: There are seven steps to click through. temps:Get(2) evaluates to 89 which is stored in the variable element.


Slide: Do This: Pull the sheet up again

Do This: Evaluate the next iteration again. If you're using the Traversal Machine, pull the index sheet up again. i now equals 3. Evaluate the statement inside the loop.

Click through animation: There are seven steps to click through. temps:Get(3) evaluates to 65 which is stored in the variable element.


Slide: Do This: Now pull up the index sheet one last time.

Do This: Evaluate the loop one last time, pulling up the index sheet again if you're using the Traversal Machine. i now equals 4.

Click through animation: There are three steps to click through.

Say: Is 4 less than 4 (the length of the list)? No - so we exit out of the loop.


Slide: Are you starting to see a pattern here?

Say: Are you starting to a see a pattern here?


Slide: Do this: Let's look for a number in the temps list.

Say: Let's look for a number in the temps list. It's easy for you to scan the list quickly with your own eyes, but for this exercise, let's pretend you are a computer and must use code to look for the number.

Do this:

integer element = temps:Get(i)
if element = 85
    output "Element found at index " + i
else
    output "Not here!"
end
i = i + 1

Slide: My Console

Say: Check your console. Does it look like this?

Not here!
Element found at index 1
Not here!
Not here!

Say: The number 85 was found at index 1, the second number in the list. Notice that i currently has the value 4. This is because we stopped after four rounds. Element is currently storing 65, the last element that we accessed, at index 3.


Slide: Do this: Now I want to find the smallest number in my list.

Say: Now I want to find the smallest number in a list. I am going to reduce the list to the smallest number.

Do This:

integer element = temps:Get(i)
if element < min
    min = element
end
i = i + 1

Slide: The smallest number in the list is 65.

Say: The smallest number in the list is 65. Again, this is easy for you to quickly scan with your eyes when your list is short, but imagine if your list contained 1,000 or 1,000,000 elements? This is where a computer using a loop really shines.


Slide: Do this: Let's make it more challenging.

Say: Let's make it more challenging.

Do This:

Note:Read this example out loud so students understand how they should interact while doing the challenge.

"Marnie, what number is at temps index 0?"
- Run one round of the loop. If the value is greater than what is already stored in max, update max. If it is not greater than, continue on.
"Marnie, what number is at temps index 1?"
- And so on and so forth ... until you get to the end of the list.

Allow students five or so minutes to fully complete the task. Here's a sample of what their updated code might look like:

if element > max
    max = element
end

Slide: Do this: I have a list of animals...

Say: Now I have a list of animals from which I want to filter some elements and store them in another list.

Do This:

text element = animals:Get(i)
if element:GetSubtext(0, 1) = "a"
    listAnimalsA:Add(element)
    output "Added " + element + " list" 
else
    output "Nothing to see here!"
end
i = i + 1

Slide: Do This: Run the code

Do This:

Note: Expect this activity to take around 5 minutes. When students have finished, move on to the Takeaways in the Wrap Up.


Teaching Tip

Running the Activity: This activity asks students to follow along as a number of core concepts for programming are introduced. The model is typically that a term or concept is introduced and modeled and then afterwards students are encouraged to try it out on their own. Trying it out typically means they are writing information down and sharing it with another group before discussing the results with the whole class.

Slides with animations have an icon in the bottom left corner to let you know you need to click to reveal more of the slide's content.

To help you more easily prepare the activity and keep track of your instructions, detailed instructions have been included as speaker notes in the presentation. Here are some tips to help you throughout the presentation.


Wrap Up

Do This: Review key takeaways with the class.

Key Takeaways

Video: As a class, watch the CS Principles: Processing Lists video.

Journal: Have students add the definition for the word traversal to their journal:

Remarks

Assessment: Check for Understanding

Question: Why is a traversal with a loop a good method for accessing and updating items in a lengthy list?

Standards Alignment