Complexity and Tractability

Learning Resource Type

Classroom Resource

Subject Area

Digital Literacy and Computer Science

Grade(s)

9, 10, 11, 12

Overview

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.

Digital Literacy and Computer Science (2018) Grade(s): 09-12

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

Vocabulary

pseudocode
programming language

a.

approximated

b.

iteration
conditional statements
control structures

c.

iterative loop
selection constructs
recursion

Knowledge

Students know:

that differences exist in pseudocode and a programming language.
that programming languages have certain requirements for language and syntax.

a.

that some programs cannot return a result in a reasonable time frame, therefore approximations must be allowed in those cases.

b.

how to identify sequential statements, conditional statements, and/or iterations in code.
the differences between sequential statements, conditional statements, and/or iterations.
trade-offs exist with using one control structure over another.

c.

some decisions in a program will require the use of iterative loops, selection constructs, or recursion.

d.

programs can be written to satisfy a number of needs such as performance, reusability, and ease of implementation.
that most times, algorithms will differ based on the need of the program; performance, reusability, or ease of implementation.

e.

that programs can be written with specific priorities in mind.
that there are multiple correct ways to write a program.
that solutions are often chosen to meet the priority need of the program.

Skills

Students are able to:

distinguish between a generalized expression of an algorithm in pseudocode and its concrete implementation in a programming language.
point out similarities in vocabulary and syntax between pseudocode and an algorithm.
point out differences in vocabulary and syntax between pseudocode and an algorithm.

a.

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

b.

identify sequential statements, conditional statements, and/or iterations in code.
identify tradeoffs associated with using one control structure over another.

c.

distinguish when a problem solution requires decisions to be made among alternatives or when a solution needs to be iteratively processed to arrive at a result.

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.

Understanding

Students understand that:

similarities and differences exist in pseudocode and programming code.
some programming languages more closely resemble pseudocode than do other programming languages.

a.

due to time or financial constraints, some programs may return an approximation of a solution.

b.

both benefits and drawbacks exist when selecting one control structure over another in a code.

c.

programs can use multiple methods to arrive at a solution.

d.

there are times when a program needs to be selected for a specific purpose, such as performance, reusability, and/or ease of implementation.

e.

multiple algorithms can solve the same problem.
algorithms can operate with a specific priority in mind, such as speed, simplicity, and/or safety.

Digital Literacy and Computer Science (2018) Grade(s): 09-12

DLCS18.HS.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.

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.

CR Resource Type

Lesson/Unit Plan

Resource Provider

CS Field Guide

License Type

Attribution Non-Commercial Share Alike

https://csfieldguide.org.nz/en/chapters/complexity-and-tractability/

Approved Date

2019-07-16

Design by Adaptive Theme