ALEX Resources

   View Standards     Standard(s): [DLIT] (9-12) 9 :

3) Differentiate between a generalized expression of an algorithm in pseudocode and its concrete implementation in a programming language.

a. Explain that some algorithms do not lead to exact solutions in a reasonable amount of time and thus approximations are acceptable.

b. Compare and contrast the difference between specific control structures such as sequential statements, conditional, iteration, and explain the benefits and drawbacks of choices made.

Examples: Tradeoffs involving implementation, readability, and program performance.

c. Distinguish when a problem solution requires decisions to be made among alternatives, such as selection constructs, or when a solution needs to be iteratively processed to arrive at a result, such as iterative 'loop' constructs or recursion.

d. Evaluate and select algorithms based on performance, reusability, and ease of implementation.

e. Explain how more than one algorithm may solve the same problem and yet be characterized with different priorities.

Examples: All self-driving cars have a common goal of taking a passenger to a designation but may have different priorities such as safety, speed, or conservation; web search engines have their own algorithms for search with their own priorities.

[DLIT] (9-12) 45 :

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.

Are there problems that are too hard even for computers? It turns out that there are. In the chapter on Artificial Intelligence, we'll see that just having a conversation – chatting – is something computers can't do well, not because they can't speak but rather because they can't understand or think of sensible things to say. However, that’s not the kind of hard problem we’re talking about here – it's not that computers couldn’t have conversations, it's more that we don't know just how we do it ourselves and so we can't tell the computer what to do.

In this chapter, we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution.

   View Standards     Standard(s): [DLIT] (9-12) 45 :

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.

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.