Unit 5 Lesson 9: Traversals Explore

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:

Use appropriate vocabulary to describe traversals.
Understand how to use a loop to traverse a list
Trace simple programs with loop traversals

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:

List - an ordered sequence of elements.
Element - an individual value in a list that is assigned a unique index.
Index - a common method for referencing the elements in a list or string using natural numbers.
Iteration - a repetitive portion of an algorithm. Iteration repeats until a given condition is met.

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:

The dotted line at the top of the sheet
The box with the list index
The box inside of the variable baggy

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"

If students are using the Traversal Machine, they should take two small pieces of a sticky note and write temps on them. Then, place the sticky note pieces over the two instances of list on the machine.
If students are using pseudocode, they can erase and replace the instances of list in the text.

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?

We are able to access each item in a list by using a loop.
This is called traversal. We are traveling or traversing through a list one element at a time.

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:

Write down the code below and put it in your loop.
If you're using the Traversal Machine, pull the index sheet up each time you go through the loop.
Run the loop until it is finished.
Write output to the "console" -- a scrap piece of paper, a separate blank document, etc.
When done, compare your console with another group.

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:

We're going to add a new global variable to our program, integer min = temps:Get(0). You can add this to the top of your pseudocode or store it on a scrap piece of paper.
Evaluate that statement to find the first value stored in min.
Replace the inside of your loop with the new code below.
Run the program.
Update the variable min as needed.

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:

With your partner, update the code inside the for loop to now find the largest number (max)
One partner creates a new list of 8 random numbers and keeps them hidden.
The other partner runs the Traversal Machine to find the largest number in the list by asking for each number one at a time.
Before beginning:
- Store a new global variable: integer max = temps:Get(0)
- Evaluate that statement to find the value stored in max. Ask your partner what is stored at "temps index 0"
Run the loop.
Check your answer at the end with your partner!

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:

One partner creates a list of eight random animal names and stores it in the list animals. Keep this list hidden.
The other partner separately keep track of a new list called animalsListA.
Change the name of the list in your code to animals.
Copy the code below and place it in your loop.

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:

Run the code
Keep track of your console
When finished, trade your animal list with another group, run the code, and compare your console outputs

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.

There are opportunities throughout the presentation for students to actively engage. At these moments students should be making things with their manipulatives or using them to answer questions. Use these opportunities to check progress.
There is a fair amount of new vocabulary introduced but it is introduced gradually and with intentional repetition. Make a point of actively modeling the use of new terms.
The most important goal here is building a mental model. It is ok if students have some open questions that will get resolved over the subsequent conditional lessons.
Both you and students can use the "Key Takeaways" to check your understanding at the end.

Wrap Up

Do This: Review key takeaways with the class.

Key Takeaways

We use a loop to traverse a list, visiting each element one at a time.
Each pass through the loop, the counting variable changes - usually by one. We can access each element by evaluating list:Get(i) in the loop.
Once we know the element at each spot in a list, we can do different things with it:
- Filter (create a subset of elements from the original list)
- Reduce (reduce the list down to a single element, for example: the smallest number in the list)

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

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

Traversal: the process of accessing each item in a list one at a time

Remarks

We can use traversals to modify data in several different ways that we will investigate tomorrow including transforming or changing each element in a list, filtering a dataset, and combining or comparing data.

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

CSTA K-12 Computer Science Standards (2017): 3A-AP-14, 3B-AP-10
CSP2021: AAP-2.O.1, AAP-2.O.2, AAP-2.O.4
CSP2021: DAT-2.D.6