Unit5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Lesson 9: Traversals Explore

App Lab

Overview

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

Purpose

Students are introduced to the concept of traversal using the Traversal Machine. This unplugged lessons provides students a physical mental model they will be able to use when they transition to programming traversals in App Lab.

Agenda

Lesson Modifications

Warm Up (5 mins)

Activity (30 mins)

Wrap Up (10 mins)

View on Code Studio

Objectives

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

Preparation

Per pair of students:

  • 1 Traversal Machine

    • The index sheet contains enough sections to divide between six students

  • Preview the Intro to Traversals slideshow. Click through all animations.

Links

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

For the Teachers

Support

Report a Bug

Forum

Teaching Guide

Lesson Modifications

Attention, teachers! If you are teaching virtually or in a socially-distanced classroom, please read the full lesson plan below, then click here to access the modifications.

Warm Up (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 (30 mins)

Traversals

Display: Use the activity slides for this lesson to guide the unplugged activity on Traversals.

Slides                     Speaker Notes
Say: Today we are going to learn about Traversals. Make sure you and your partner have all the supplies you see on the screen.

Note to Teacher: If you 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
Do This: On a scrap piece of paper or a sticky note, write down the list on the screen.
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.

Click for animation to reveal suggested answer
Say: Computers are really good at checking things one by one. To do this... let's use a for loop.
Do This: Set up the Traversal Machine.

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.
Do This: Direct students attention to their Traversal Machines as you describe the parts.

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, 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.
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,s o we are going to keep the loop going until we have hit list.length.

Note: You may want to remind students that list.length 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
Do This: replace list with the name of your list. In this case, we would replace it with temps.
Say: The counter variable i increases after each loop runs.
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 with your Traversal Machine.

Click for animation

Do This: Set up a variable baggy and give it the name element.

Note: You may opt to not use variable baggies at all in this lesson and instead have students keep track of variables 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. It's not necessary to build a baggy for the variable i - this will be represented on the Traversal Machine itself as a drawing of a baggy.
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.
Say: Look at the list on the screen. Right now i=0.

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[0] evaluates to 77 which is stored in the variable element
Do This: Now pull the index sheet up one spot. i now equals 1. Evaluate the statement inside the for loop.

Click through animation: There are seven steps to click through. temps[1] evaluates to 85 which is stored in the variable element
Do This: Pull the index sheet up again. i now equals 2. Evaluate the statement inside the for loop.

Click through animation: There are seven steps to click through. temps[2] evaluates to 89 which is stored in the variable element
Do This: Pull the index sheet up again. i now equals 3. Evaluate the statement inside the for loop.

Click through animation: There are seven steps to click through. temps[3] evaluates to 65 which is stored in the variable element
Do This: Now pull up the index sheet one last time. i now equals 4.

Prompt: What happens next?

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.
Say: Are you starting to see a pattern here?

  • We are able to access each item in a list by using a for loop.
  • This is called traversal. We are traveling or traversing through a list one element at a time.
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 the Traversal Machine to look for the number.

Do this:
  • Write down the code to the left on a sticky note and put it in your for loop.
  • Pull the index sheet up each time you go through the loop.
  • Run the loop until it is finished
  • Your "console" can be a scrap piece of paper.
  • When done, compare your console with another group.
Say: Check your console. Does it look like what you see on the screen? 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.
Say: Now I want to find the smallest number in a list. I am going to reduce the list to the smallest number. We are going to leave the baggies behind now. You can use a scrap piece of paper to store the global variable var min = temps[0]

Do This:
  • Evaluate that statement to find the value stored in min.
  • Run the program
  • Update the variable min as needed
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.
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 the global variable on a scrap piece of paper: var max = temps[0];
    • Evaluate that statement to find the value stored in max. Ask your partner what is stored at "temps index 0"
  • Run the for loop.
  • Check your answer at the end with your partner!


Note: Read the example at the bottom of the screen out loud so students understand how they should interact while using the Traversal Machine. Allow students five or so minutes to fully complete the task on this slide. Here's a sample of what their updated code might look like:

if(element>max)
    {max = element;
}
Say: Now I have a list of animals from which I want to filter some elements and store them in another list.

Note: Guide the students through the setup listed on the screen.

Do This:
  • One partner creates a list of eight random animals, and stores it in the list animals on a scrap of paper. Keep this list hidden.
  • The other partner uses a separate scrap of paper to track a new list called animalsListA
  • Change the name of the list in the for loop of the Traversal Machine to animals.
  • Copy the code to the right on to a sticky note and place it in the for loop of the Traversal Machine.
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 on a sticky note 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 (10 mins)

Do This: Review key takeaways with the class.

Video: As a class watch the video on Traversals.

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

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

Check For Understanding Question(s) and solutions can be found in each lesson on Code Studio. These questions can be used for an exit ticket.

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

Standards Alignment

View full course alignment

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.

CSP2021

AAP-2 - The way statements are sequenced and combined in a program determines the computed result
AAP-2.O - For algorithms involving elements of a list: a. Represent using iterative statements to traverse a list. b. Determine the result of an algorithm with list traversals.
  • AAP-2.O.1 - Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed. EXCLUSION STATEMENT (EK AAP-2.O.1): Traversing multiple lists at the same time using the sam
  • AAP-2.O.2 - Iteration statements can be used to traverse a list.
  • AAP-2.O.4 - Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:●       determining a minimum or maximum value in a list●       computing a sum or a
DAT-2 - Programs can be used to process data
DAT-2.D - Extract information from data using a program.
  • DAT-2.D.6 - Some processes that can be used to extract or modify information from data include the following:●       transforming every element of a data set, such as doubling every element in a list, or extracting the parent’s email from every student record●