Lesson 3: Unreasonable Time
Overview
Students investigate two different types of raffles that highlight the way seemingly small problems can quickly grow large. The first raffle asks students to hunt for pairs of tickets that add to a target value. The second raffle asks students to hunt for any group of tickets that adds to a target value. After trying out each raffle live students will try to figure out the patterns for how many total combinations need to be checked in each. At the end they discuss the difference between reasonable and unreasonable algorithms based on their experiences.
Purpose
This lesson explores some tricky mathematical concepts in a hands on and interactive way. Building off the raffle analogy used in the previous lesson, it gives students an experience with two types of problems that grow quickly in size, though as they'll see one grows much faster than the other. This lesson should give students a sense of how computer scientists use mathematics to think about problems without relying too heavily on mathematical background that not all students may have.
Agenda
Lesson Modifications
Warm Up (5 mins)
Activity (30 mins)
Wrap Up (10 mins)
View on Code Studio
Objectives
Students will be able to:
- Explain the difference between problems that run in a reasonable time and those that do not
- Explain how both formal mathematical reasoning and informal measurement can be used to determine an algorithm's efficiency
Preparation
- Review the slides to make sure you are prepared to lead the different discussions in this lesson.
Links
Heads Up! Please make a copy of any documents you plan to share with students.
For the Teachers
- CSP Unit 6 - Algorithms - Presentation
For the Students
- Unreasonable Time - Activity Guide
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)
Discussion Goal
Goal: This prompt is a review from the previous lesson. Students should be free to refer to notes or their journals. You should might hear the following points.
- One algorithm requires fewer steps to complete than another
- "The line for one algorithm curves below the other"
- More efficient algorithms are much more helpful as input size grows. The amount of work grows more slowly.
You may wish to refer to slides from previous lessons.
Prompt: What does it mean to say one algorithm is “more efficient” than another?
Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.
Remarks
Yesterday we started looking at how computer scientists might compare two algorithms that solve the same problem. Today we're going to look at two different problems. They may seem similar but as we'll see they actually are much harder to solve than either of the two we saw yesterday. The question will be "how much harder"? Let's get to it!
Activity (30 mins)
Teaching Tip
Running the Raffles: Both because it helps give students a sense of the problem space and because it's fun to run a raffle, you should run both the pair raffle and the group raffle in your classroom. Here's some helpful tips.
- Insist that students check for the pair raffle silently. For this one it's very easy to just yell out what number you would pair with and lose the opporuntity to see how many total checks are necessary if they can just all yell from their seats.
- The group raffle doesn't necessarily need to be silent. As students will see, it's an incredibly difficult problem and they're going to need to do a lot of checking even if they're able to talk out loud.
- Think ahead about whether you actually want to award winners of the raffles. It's pretty unlikely that there will be a winner.
- There's a pretty good chance that no one will win either raffle.
Running The Two Raffles
Distribute: Send students to the ticket generator widget on Code Studio.
Display: Show slides that explain the pair raffle.
Circulate: Give students a couple of minutes to walk around the room seeing if they can find a partner with which they can win the raffle. After a couple of minutes have them return to their desks. If there are any winners feel free to celebrate.
Remarks
Alright, that was interesting. Let's try out a different version of the raffle. Last time I made you work silently so that we got a better sense of how many checks needed to happen. This time we're going to run a group raffle, but I'll let you talk out loud if you want.
Display: Show slides that explain the group raffle.
Circulate: Give students a couple of minutes to walk around the room seeing if they can find a group with which they can win the raffle. After a couple of minutes have them return to their desks. If there are any winners feel free to celebrate.
Discussion Goal
Goal: This discussion is primarily designed to get quick reactions from students to motivate the second big activity in this lesson. Students will likely note that the group raffle felt a lot harder to check, even with the ability to talk. That said, there's no wrong answers at this point. You're about to check their intutions mathematically.
Prompt: Which raffle felt like it was more difficult to check? Why?
Discuss: Have students discuss this prompt with a neighbor. Then have a few students share out their reflections.
Remarks
As computer scientists we're getting better at thinking about problems and algorithms. We also saw last time that we can use a little mathematical reasoning to decide if one algorithm is more efficient than the other. Let's do a little work on these two raffles to see if our intuitions are correct.
Distribute: Distribute copies of Unreasonable Time - Activity Guide
Teaching Tip
Encouraging Drawing: Students will likely be able to answer these questions much more easily if they draw on a sheet of paper. The question for the pair raffle becomes "if I draw some dots on a sheet of paper, how many lines can I draw between them?" since each line connects two points. For the group raffle it is a little more tricky but it's "how many ways can I combine the dots?"
8 is a Challenge: The activity guide indicates that 8 is a challenge for both activities. Unless students are starting to see that patterns for each raffle size they will likely find this extremely challenging, especially for the group raffle. Reassure students it's a challenge and they don't need to complete it.
Ending Early: It's more important that students get experience with how these two problems are different in how quickly they grow. If students are getting stuck with one encourage them to move on to the other.
Activity Guide - Unreasonable Time
Pair Raffle: Ask students to fill out the first page where they must figure out the total number of pairs for different sized "pair raffles". This may take several minutes and require students to draw pictures.
Group Raffle: Ask students to fill out the second page where they must figure out the total number of groups for different sized "group raffles". This may take several minutes and require students to draw pictures.
Share Responses: Ask students to share their responses with another group.
Display: Show the slides summarizing the correct solutions for each as well as providing language to describe these two kinds of curves.
Prompt: Polynomial and exponential both curve up. Why do you think only exponential is considered “unreasonable”?
Discuss: Briefly ask students for their ideas why before showing them the following slides. Exponential curves grow extremely quickly. You simply can't build a computer fast enough even for relatively small raffle sizes.
Wrap Up (10 mins)
Journal: Students add the following vocabulary words and definitions to their journals: unreasonable time, reasonable time
Discussion Goal
Goal: Use this discussion to reinforce vocabulary introduced in the slides and make sure they have understood the main concepts of the day. Students should be able to explain with the term reasonable, unreasonable, and exponential, why running a group raffle in a school of most sizes is impossible.
Prompt: Your school is considering running the group raffle at an upcoming assembly to give away a prize. Write a brief explanation of what advice you would give them.
Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.
Remarks
The group raffle is just one example of an algorithm that is "unreasonable". It grows exponentially and so we'd never want to run it at our school. Next time we'll talk more about what to do when we encounter unreasonable problems.
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: Which of the follow efficiencies would be considered unreasonable?
Question: Based on the data provided, does this algorithm run in a reasonable or unreasonable time? Explain your answer
Standards Alignment
View full course alignment
CSTA K-12 Computer Science Standards (2017)
AP - Algorithms & Programming
- 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
CSP2021
AAP-4 - There exist problems that the computer cannot solve
AAP-4.A - For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not run in reasonable time. b. Identify situations where a heuristic solution may be more appropriate.
- AAP-4.A.4 - An algorithm’s efficiency is determined through formal or mathematical reasoning.
- AAP-4.A.7 - Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of