Lesson 2: Searching

Do This: Demonstrate the activity by acting as the magician.

1. Ask students to choose a card.
2. Shuffle the cards.
3. Reveal a card and ask if that was the card. Add one to the number of guesses.
4. Put the revealed card into a pile of checked cards until the next round.
5. Repeat steps 2 through 4 until the revealed card is the one the student chose.

Repeat the process several times to create a variety in the number of guesses it took to find the chosen card.

Discuss: Click through the animated slide to display the prompts. Use the Retrieve-Pair-Share strategy to discuss the prompts.

• Am I the world’s worst magician?
• How many guesses would the world’s best magician take?
• How many guesses would the real world’s worst magician take?

Discussion Goal: Students suggest that the world's best magician always finds the correct card on the first try. Students share that the world’s worst magician would guess the correct card on their very last attempt.

When we have written algorithms to find a target value in a data structure, we are searching the entire data structure one element at a time from first to last. This approach is actually one of many standard algorithms used by software engineers for searching a data structure.

Do This: Review the lesson objectives.

Group: Place students in pairs.

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 the method traverses each array one element at a time from first to last. Students also notice that the program displays each element it checks and keeps a count of how many checks it executes. Students may wonder if there is a faster way to search for data.

Do This: Click through the animated slide to define linear/sequential search and demonstrate using the algorithm with a 1D array.

Do This: Click through the animated slide to demonstrate using the algorithm with a 2D array.

Do This: Click through the animated slide to define the best case, average case, and worst case.

Discuss: Click through the animated slide to display the prompts. Use the Retrieve-Pair-Share strategy to discuss the prompts.

• What is the best case for the World's Worst Magician?
• What is the average case for the World's Worst Magician?
• What is the worst case for the World's Worst Magician?

Discussion Goal: Students identify the best case as guessing the card on the first try, and the worst case as the total number of cards. Students suggest values for the average case based on their experience in the warm up activity.

To help students identify the average case, ask students additional guiding questions. For example:

• What does finding the average of a scenario like this consist of?
• How many times should we test the algorithm to identify the average case?

When we need to choose an algorithm for a specific task, we typically choose or create the most efficient one. Software engineers use different techniques and tools to measure the efficiency of algorithms. One way that we can measure efficiency is by counting the number of times a code segment executes.

Do This: Click through the animated slide to define execution count.

Distribute: Give each student a copy of the Counting Executions with Code handout.

Do This: Have students complete the Counting Executions with Code handout.

Do This: Have students compare their findings with a partner.

As software engineers, one of our primary goals is to develop software that provides usefulness and value to users. Our goal for the Creative Coding Project is to create a program using the console that portrays a personal interest or solves a problem. When we develop programs to convey a personal interest, we typically have an audience in mind that we want to show our work to. When we develop programs to solve a problem, we typically have a specific type of user that we want to benefit from the program.

Do This: Click through the animated slide to review user stories.

Do This: Have students write user stories for their project on page five of their Creative Coding with the Console Project Planning Guide.

We just learned a lot of new information today, which may have even answered some of the Need to Know questions you wrote down about the Creative Coding Project. As we progress through the unit, it is helpful to stop and note what we have learned that is related to or useful for the project.

Do This: Have students review the questions they wrote in the "Need to Know" column on page two of their Creative Coding with the Console Project Planning Guide. Students add new questions to this column, check off any answered questions, and write answers to any questions in the "Learned" column.

Do This: Have students share what they added to their chart with a partner.

If time permits, you can also have students share as a class.

Do This: Review the concepts covered in this lesson.

Display: Key Vocabulary

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.

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 4.5
• Topic Questions 7.5

Note: Some Learning Objectives and Essential Knowledge statements in the suggested Topic Questions are covered in later units.