ALEX Classroom Resource

  

Computer Science Principles Unit 4 Chapter 1 Optional Lesson: One-Way Functions - The Wifi Hotspot Problem

  Classroom Resource Information  

Title:

Computer Science Principles Unit 4 Chapter 1 Optional Lesson: One-Way Functions - The Wifi Hotspot Problem

URL:

https://curriculum.code.org/csp-18/unit4/8/optional/12/

Content Source:

Code.org
Type: Lesson/Unit Plan

Overview:

In this lesson, students continue their exploration of computationally hard problems as they investigate a one-way function, a problem which is easy to construct in such a way that you know the solution, but it is computationally hard to solve. Students will begin the lesson by trying to solve the “Wireless Hotspot Problem” (also known as the vertex cover or dominating sets problem) to experience first-hand the challenge of solving it. They will then be instructed on how easy it is to create such a problem and will practice doing so themselves. In the Wrap-up, students are introduced to the concept of a one-way function and consider why such problems might be useful tools when constructing methods of encryption. If it’s easy to create a problem that is hard for a computer (or human!) to solve, then perhaps it is possible to make truly secure encryptions.

Students will be able to:
- describe the properties of a one-way function.
- construct a wireless hotspot map, starting from a solution key.
- explain why the wireless hotspot problem is a computationally hard problem.
- describe the difference between the Traveling Salesman Problem and the Wireless Hotspot Problem and why one-way functions are desirable when creating cryptographic methods.

Note: You will need to create a free account on code.org before you can view this resource.

Content Standard(s):
Digital Literacy and Computer Science
DLIT (2018)
Grade: 9-12
39) Identify a problem that cannot be solved by either humans or machines alone and discuss a solution for it by decomposing the task into sub-problems suited for a human or machine to accomplish.

Examples: Forecasting weather, piloting airplanes.

Insight Unpacked Content
Evidence Of Student Attainment:
Students will:
  • identify a problem that cannot be solved by humans or machines alone.
  • discuss possible solutions using decomposition.
  • identify subproblems for either a human or machine to solve.
Knowledge:
Students know:
  • how to identify a problem.
  • how to decompose a problem.
  • how to identify possible solutions to a problem.
Skills:
Students are able to:
  • identify a problem that cannot be solved by humans or machines alone.
  • discuss possible solutions using decomposition.
  • identify subproblems for either a human or machine to solve.
Understanding:
Students understand that:
  • problems exist that cannot be solved by a human or machine alone.
  • identifying subproblems can make a complex problem easier to solve.
  • humans and machines can work together to solve complex problems.
Tags: computationally hard, oneway function, optional, wireless hotspot problem
License Type: Custom Permission Type
See Terms: https://code.org/tos
For full descriptions of license types and a guide to usage, visit :
https://creativecommons.org/licenses
Accessibility
Comments
  This resource provided by:  
Author: Aimee Bates