Lesson 2: Row-Major Traversal
45 minutes
Standards
CON-2 - Programmers incorporate iteration and selection into code as a way of providing instructions for the computer to process each of the many possible input values
CON-2.I - For algorithms in the context of a particular specification that requires the use of array traversals: • Identify standard algorithms. • Modify standard algorithms. • Develop an algorithm.
- CON-2.I.1 - There are standard algorithms that utilize array traversals to: • Determine a minimum or maximum value • Compute a sum, average, or mode • Determine if at least one element has a particular property • Determine if all elements have a particular property • Access all consecutive pairs of elements • Determine the presence or absence of duplicate elements • Determine the number of elements meeting specific criteria
CON-2.N - For Algorithms in the context of a particular specification that requires the use of 2D array traversals: • Identify standard algorithms. • Modify standard algorithms. • Develop an algorithm.
- CON-2.N.2 - All standard 1D array algorithms can be applied to 2D array objects.
VAR-2 - To manage large amounts of data or complex relationships in data, programmers write code that groups the data together into a single data structure wihtout creating individual variables for each value.
VAR-2.F - Represent collections of related primitive or object reference data using two-dimensional (2D) array objects.
- VAR-2.F.5 - “Row-major order” refers to an ordering of 2D array elements where traversal occurs across each row, while “column-major order” traversal occurs down each column
VAR-2.G - For 2D array objects: • Traverse using nested for loops. • Traverse using nested enhanced for loops.
- VAR-2.G.1 - Nested iteration statements are used to traverse and access all elements in a 2D array. Since 2D arrays are stored as arrays of arrays, the way 2D arrays are traversed using for loops and enhanced for loops is similar to 1D array objects.
- VAR-2.G.2 - Nested iteration statements can be written to traverse the 2D array in “row-major order” or “column-major order.”
Agenda
Objectives
Students will be able to:
- Apply standard 1D array algorithms to a 2D array
- Write nested loops to traverse a two-dimensional (2D) array in row-major order
Preparation
- Check the Teacher's Lounge for verified teachers on the CSA Forum to find additional strategies or resources shared by fellow teachers
Links
Heads Up! Please make a copy of any documents you plan to share with students.
For the students
- Row-Major Traversal - Video
- Tracing 2D Array Traversals - Handout
- U5L2 Extra Practice - Handout
Vocabulary
- row-major order - traversing a 2D array by accessing each row from top to bottom
Teaching Guide
Warm Up (10 minutes)
2D Array Algorithms
Remarks
We worked with standard 1D array algorithms in the previous units to find information and perform calculations. These standard algorithms can also work with 2D arrays.
Group: Place students in groups of three or four.
Do This: Have students write an algorithm to find the values greater than 10 in the 2D array.
Ask a student from each group to share the algorithms they developed with the class or have groups share their algorithms with each other.
Activity (30 minutes)
Row-Major Traversal (15 minutes)
Remarks
To access each element in a 2D array, we have to move through the array row-by-row and column-by-column. We learned to use nested loops to manipulate elements in a 1D array, and we can also use nested loops with 2D arrays to access each element. Let's take a look at how this works.
Do This: Review the lesson objectives.
Do This: Direct students to Level 1 on Code Studio to investigate the program with a partner. Students make the changes to the program as prompted.
Discuss: Click through the animated slide to display the prompts.
- What do you notice about the code in this program?
- What do you wonder about the code in this program?
Discussion Goal: Students notice that the outer loop accesses each row, and the inner loop accesses each column in the current row. Students may wonder about the syntax for referring to the column in the inner loop.
Display: Show the video – Row-Major Traversal.
Do This: Click through the animated slide to demonstrate a row-major traversal.
Group: Place students in pairs.
Distribute: Give each pair a copy of the Tracing 2D Array Traversals handout.
Do This: Have students complete the Tracing 2D Array Traversals handout.
You can choose to model completing the first few rows of the trace table as a class first, then have students work with their partners to complete the remaining rows.
Traversing 2D Arrays (15 minutes)
Remarks
Traversing a 2D array can help us find information similar to how we found information in a 1D array. When data is represented as a table, it allows us to ask different types of questions to find information.
Discuss: Use the Hold That Thought strategy to discuss the prompt.
- What are some questions we could answer by traversing through this data?
Discussion Goal: Students suggest questions that would require finding information within a row or column or performing calculations on values within a row or column.
Remarks
We have used a standard algorithm to find the sum of all elements in a 1D array. All standard 1D array algorithms can be applied to 2D arrays. Let's use what we know about traversing a 2D array to modify this algorithm to find the sum of all elements in a 2D array.
Do This: Have students write pseudocode to find the sum of all elements in a 2D array.
Do This: Direct students to Level 2 on Code Studio to complete Levels 2 and 3. Students implement their algorithm on Level 2, then continue to Level 3 to complete a choice level to apply a standard 1D array algorithm to a 2D array using the console or The Theater.
Wrap Up (5 minutes)
Software Engineering Skills
Remarks
Both 1D and 2D arrays expand our capabilities for storing data in a program. With these data structures, we can implement algorithms to find information and perform calculations based on the needs of our programs.
Discuss: How did you use your skills as a software engineer to implement your algorithms?
Discussion Goal: Students share examples of how they used software engineering skills and characteristics to implement their algorithms.
Do This: Review the concepts covered in this lesson.
Display: Key Vocabulary
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.
AP Classroom Topic Questions
To assign questions from the AP Classroom Question Bank that align with this lesson, create a custom quiz in AP Classroom by searching the Question Bank for the Essential Knowledge statements listed at the top of this lesson plan. You can find instructions and video demonstrations to do this on AP Central.
The following Topic Questions in AP Classroom can be assigned as a formative assessment for this lesson:
- Topic Questions 8.1
Note: Some Learning Objectives and Essential Knowledge statements in the suggested Topic Questions are covered in later units.
This work is available under a Creative Commons License (CC BY-NC-SA 4.0).
If you are interested in licensing Code.org materials for commercial purposes contact us.
