Day 18: Traversing Lists

Learning Objectives

• AAP-2.M: For algorithms involving elements of a list: Write iteration statements to traverse a list.
• AAP-2.N: For list operations: Write expressions that use list indexing and list procedures.
• AAP-2.O: For algorithms involving elements of a list: Determine the result of an algorithm that includes list traversals.
• AAP-2.P: For binary search algorithms: Determine the number of iterations required to find a value in a data set.

Essential Questions

• How do we efficiently process all elements in a list?
• What are different patterns for traversing and processing lists?

Materials Needed

• Presentation slides on list traversal
• Programming environment
• List traversal worksheet
• Sample data sets
• Exit ticket templates

Vocabulary

• Traversal
• Iteration
• FOR EACH loop
• Index-based traversal
• Element-based traversal
• Complete traversal
• Partial traversal
• Linear search
• Sequential search

Procedure (50 minutes)

Opening (8 minutes)

1. Review and Connection (3 minutes)

   • Review list operations from previous lesson
   • Connect to today's focus on systematically processing list elements

2. Warm-up Activity (5 minutes)

   • Present a list and a task requiring processing each element
   • Ask students to write pseudocode for processing the entire list
   • Discuss different approaches to visiting each element

Main Activities (32 minutes)

3. Lecture: Traversing Lists with Loops (12 minutes)

   • Define list traversal as visiting each element in a list
   • Explain types of traversals:
     • Complete traversal: accessing all elements
     • Partial traversal: accessing only some elements
   • Introduce traversal methods:
     • Index-based traversal using REPEAT n TIMES
     • Element-based traversal using FOR EACH
   • Explain the FOR EACH loop syntax:
     • FOR EACH item IN aList
     • How the variable item takes on each value in the list
     • Order of traversal (first to last element)
   • Discuss common traversal patterns:
     • Processing each element
     • Transforming elements
     • Filtering elements
     • Searching for elements
   • Explain linear/sequential search algorithm:
     • Checking each element in order
     • Stopping when the desired value is found or all elements are checked
     • Efficiency considerations

4. Demo: Different Traversal Patterns (8 minutes)

   • Walk through examples of list traversals:
     • Using FOR EACH to process every element
     • Using index-based loops for more control
     • Implementing linear search
     • Transforming list elements
     • Filtering elements based on conditions
   • Demonstrate when to use each traversal approach
   • Show how to combine traversal with other operations
   • Highlight common patterns and techniques
   • Discuss potential errors and edge cases

5. Hands-on: Writing List Traversal Code (12 minutes)

   • Students work in the programming environment
   • Guide students through implementing different traversal patterns
   • Have students create programs that:
     • Process all elements in a list using FOR EACH
     • Implement linear search for a value
     • Transform list elements (e.g., doubling all numbers)
     • Filter elements based on conditions
     • Count elements meeting certain criteria
   • Encourage students to test their traversals with different inputs
   • Challenge students to handle edge cases (empty lists, not found, etc.)

Closing (10 minutes)

6. Activity: Processing Data in Lists (5 minutes)

   • Provide students with a real-world dataset as a list
   • Students write code to analyze the data using list traversal
   • Tasks might include:
     • Finding patterns in the data
     • Calculating statistics
     • Identifying outliers
     • Transforming the data
   • Share and discuss different approaches
   • Highlight effective traversal techniques

7. Exit Ticket and Preview (5 minutes)

   • Students create a program that traverses and processes list data
   • Preview that next class will focus on 2D lists and nested loops

Assessment

• Formative: Quality of list traversal implementation during hands-on activities
• Exit Ticket: Correctness and efficiency of list traversal program

Differentiation

For Advanced Students

• Challenge them to implement more complex traversal patterns
• Introduce early termination techniques for efficiency
• Have them compare the efficiency of different traversal approaches

For Struggling Students

• Provide traversal code templates to complete
• Focus on one traversal pattern at a time
• Use visual aids to illustrate the traversal process

Homework/Extension

• Complete a worksheet with list traversal exercises
• Create a program that analyzes a dataset using list traversal
• Research and implement a more advanced traversal algorithm

Teacher Notes

• Emphasize that list traversal is one of the most common operations in programming
• Watch for off-by-one errors in index-based traversals
• Make connections to real-world data processing tasks
• Consider using animations or visualizations to show traversal
• Remind students that list traversal will be assessed on the AP exam