Lists, Loops, and Traversals - Lesson 10: Traversals Investigate

Overview

In this lesson students work with partners to investigate three different apps that use traversal to access items in a lists. Students first explore all three apps without seeing the code to notice similarities and predict how they will work. Then they explore the code itself and make additions and modifications to the apps. To conclude the lesson, students review and discuss common programming patterns with traversals.

Goals

Students will be able to:

• Identify common programming patterns using traversals
• Explain the purpose of programming patterns with traversals both in terms of how they work and what they accomplish
• Modify apps that make use of common programming patterns with traversals to adjust their functionality

Purpose

After building a conceptual model using a loop to traverse a list in the previous lesson, this lesson allows students to see how this is actually implemented in code. This lesson also introduces common programming patterns when using lists and traverals. Students will have some opportunities to modify working code in this lesson, but the most significant practice with lists and traversals will come in the following lesson.

Resources

• CSP-Widgets repository

Getting Started (5 minutes)

Prompt: Let's review last lesson. What did we do?

Activity (35 minutes)

Mile Tracker Investigation

Group: Group students into groups of four.

Open a Project: Today's lesson uses three apps, starting with Lesson10_App1.

App 1: Students read the entire code, and then students focus their attention on a single action. Students should re-read the code for their function.

• Student A - Average()
• Student B - Slow()
• Student C - Fast()
• Student D - NumberedListDisplay()

Discuss:How does the app work?

Students discuss in their groups how each of their functions work, specifically referencing the list it uses and how it is traversed using a for loop. Then as a class address any confusion over how the app works.

• The goal: The goal of this investigation is to give students the opportunity to see lists traversed for different reasons and with different outcomes. Students should look at the code for their assigned function and make sense of what the function does overall and how it does it.
• What to look for: It may be helpful to re-watch the video in the U5L10 - Traversals Explore lesson starting at 3:07 to hear how the speaker describes a section of code that processes a list for a specific purpose. Listening to that explanation will help give you an idea of what student explanations of their functions should sound like.

For example, when explaining the average function in this investigation, students should describe what the function does. In this case, the function calculates the average of the values stored in the mileTimes list and stores that value in the avg variable. In addition to describing what the function does, students should describe how the function works. This will involve more detail. Students should be able to describe that the function contains a local variable of total which is initialized at 0.

Then the function uses a for loop to traverse through the mileTimes list. In the loop, each value inside mileTimes list is accessed and added to the current value stored inside the total variable. When the loop reaches the end of the list, the loop ends and the total variable contains the sum of all the mileTimes. In the last line of the function, the value stored in avg is updated by dividing the value stored in total by the total number of elements in the mileTimes list.

When you bring the class together to talk about how the app works, you should talk both about what the functions do as well as how they work. There likely is not time to go over all four functions, but discussing one or two of them will ensure the full class has an opportunity to hear how their peers describe code.

Modify: Students work with a partner to create a function that adds together the total time of every element in the list. Output the result. Call this function in the UpdateScreen() function.

Data Tab Investigation

App 2 (5 mins): Students read the code, and then investigate the data folder.

Discuss: Encourage students to share out what they found in the datasets and how they can interact with it with code.

• How does it work? What information is available? What can you change? What can't you change? Investigate a few different datasets.
• The goal: The goal of this investigation is to get students comfortable with information inside the Data tab and to help them understand the getColumn command. Students should be given some time to explore the Data tab themselves and even try the Modify task for a few minutes.
• What to look for: When you bring the class together, students should be able to describe what information they see in the data tab and how they can use the data tab to help get access to data. Key points to draw out are:
  • The Data Library on the left hand side has different categories of datasets that students can view.
  • Students need to import a data set to be able to see the data inside it or to use the data in the code.
  • Once imported, students will see the data set in the Data Browser area and can click on the name of the Data Set to see the data in table form.
  • To use the getColumn command, you need the name of the table you want to use and the name of the column from that table.
  • getColumn will return the column from your table as a list. You can see it is a list because when it is printed to the console, it has square brackets [ ] around the items which are separated by commas.

Modify: Students load a new dataset into the project. Then students modify the code to print out a column of data from the new dataset. Point out to students that when they pull out a column, they are creating a list.

Do This: Show the Data Tab in App Lab video.

Random Dog Picker Investigation

App 3: Instruct students to run the app and then carefully read it. There is a lot of information in the comments in this app. Students work through all of the questions on the screen.

Discuss: Go through the questions one by one and answer as a class. Afterwards, go line by line with the class explaining how the app works.

• The goal: The goal of this investigation is to give students an opportunity to make sense of how traversals and the datasets can be used together to create a working app. It is important to note that the algorithms in this app have some of the same qualities as the algorithm students will need to develop for the Create PT.
• What to look for: This project defines several different functions. Help guide students particularly to how the lists are filled. Students should see a listSetup function. This function calls the filter function. filter is where the lists are being filled. Use the questions listed in CodeStudio to help students make sense of this code. In particular, spend a little extra time discussing the question How are these lists filled?. This is an opportunity to go through the filter function line by line to understand how the function works.

Traversal Patterns

Pattern Review: Review the two patterns below as a class: the List Filter Pattern and the List Reduce Pattern.

• Have students add any relevant notes about the patterns to their journals.
• Discuss which patterns were used in the apps today.

List Filter Patterns

Filtering One List

This pattern allows the user to filter a list into a new list by limiting the information that is added to the new list. For example, you could filter a list of words so that only words of a certain length or words that start with a specific letter appear in the new list.

Example: List Filter - starting letter

Array<text> list
list:Add("apples")
list:Add("oranges")
list:Add("apricots")
list:Add("bananas")

Array<text> filteredList

integer i = 0
repeat while i < list:GetSize()
    text firstLetter = list:Get(i):GetSubtext(0, 1)
    if firstLetter = "a"
        filteredList:Add(list:Get(i))
    end
    i = i + 1
end

Example: List Filter - length

Array<text> list
list:Add("apples")
list:Add("oranges")
list:Add("apricots")
list:Add("bananas")

Array<text> filteredList

integer i = 0
repeat while i < list:GetSize()
    integer wordLength = list:Get(i):GetSize()
    if wordLength > 7
        filteredList:Add(list:Get(i))
    end
    i = i + 1
end

How does it work?

• Create a variable and store a list in it
• Create a blank list to store the filtered list
• Use a loop to access each element in the original list
• If that element meets a certain condition, append it to the filtered list

Filtering Multiple Lists

What if you have multiple lists, but want to filter all the lists based on the information in a single list?

Example: Multiple List Filterh

Array<text> studentNameList
Array<integer> studentGradeList
Array<integer> studentAgeList

Array<text> filteredStudentNameList
Array<integer> filteredStudentGradeList
Array<integer> filteredStudentAgeList

action Start
    studentNameList:Add("Sal")
    studentNameList:Add("Maya")
    studentNameList:Add("Rudy")
    studentNameList:Add("Gina")
    studentNameList:Add("Paris")
    
    studentGradeList:Add(10)
    studentGradeList:Add(11)
    studentGradeList:Add(10)
    studentGradeList:Add(12)
    studentGradeList:Add(11)
    
    studentAgeList:Add(16)
    studentAgeList:Add(18)
    studentAgeList:Add(15)
    studentAgeList:Add(17)
    studentAgeList:Add(17)

    Filter()
end

action Filter
    // Start with blank lists
    filteredStudentNameList:Empty()
    filteredStudentGradeList:Empty()
    filteredStudentAgeList:Empty()

    integer i = 0
    repeat while i < studentGradeList:GetSize()
        if studentGradeList:Get(i) = 11
            filteredStudentNameList:Add(studentNameList:Get(i))
            filteredStudentGradeList:Add(studentGradeList:Get(i))
            filteredStudentAgeList:Add(studentAgeList:Get(i))
        end
        i = i + 1
    end
end

All the lists must be the same length for this pattern - ideally they are columns pulled from a table

How does it work?

• Create a variable for each list
• Create blank lists to store the filtered lists
• In a function, first reset all filtered lists to blank lists. Every time the function is called, the filtered lists will reset.
• Use a loop to access each item in the list that contains the element you are filtering by
• If the element is found, append to each filtered list the element at the index in the original lists where the element was found

List Reduce Patterns

This pattern is used when you want to reduce the information in a list down to a single number. For example, you might want to find the average of a list of numbers or the smallest number.

Example: List Reduce - average

Array<number> list
number average = 0

action Start
    list:Add(1)
    list:Add(2)
    list:Add(3)
    list:Add(4)
    list:Add(5)

    FindAverage()
end

action FindAverage
    number total = 0
    integer i = 0
    repeat while i < list:GetSize()
        total = total + list:Get(i)
        i = i + 1
    end
    average = total / list:GetSize()
end

How does it work?

• Create a list of numbers
• Create a blank variable to store the average
• In a function create a local variable to store the total value of all elements in the list
• Use a loop to access each element in the list and add its value to total
• After the loop, calculate the average by dividing total by the length of the list

Example: List Reduce - smallest

Array<number> list
number smallest = 0

action Start
    list:Add(5)
    list:Add(4)
    list:Add(3)
    list:Add(2)
    list:Add(1)

    FindSmallest()
end

action FindSmallest
    number temp = list:Get(0)
    integer i = 0
    repeat while i < list:GetSize()
        if list:Get(i) < temp
            temp = list:Get(i)
        end
        i = i + 1
    end
    smallest = temp
end

How does it work?

• Create a list of numbers
• Create a blank variable to store the smallest number
• In a function create a local variable to store a temporary value
• Use a for loop to access each element in the list
• If that element is less than the value stored in temp, set the value of temp to the current element
• After the loop set the value of smallest to the value stored in temp

Wrap Up (5 minutes)

Prompt: What aspects of using traversals to process a list do you feel you already understand? What questions do you want to dig into more tomorrow during the practice lesson?

Assessment: Check for Understanding

For Students

Open a word doc or google doc and copy/paste the following question.

Question

Explain how you would filter the dog dataset using traversal to have a filtered list of dogs who live long lives.

Standards Alignment

• CSTA K-12 Computer Science Standards (2017): 3A-AP-14, 3B-AP-10, 3B-AP-23
• Computer Science Principles: AAP-3.F.1, AAP-3.F.2, AAP-3.F.3, AAP-3.F.4, AAP-3.F.5, AAP-3.F.6, AAP-3.F.7

Next Tutorial

In the next tutorial, we will discuss Code.Org Unit 5 Lesson 11, which describes Practice using traversals.