Define problem (in computing).

A problem is a general description of a task that can (or cannot) be solved algorithmically.

Define instance of a problem.

An instance of a problem is the problem with a specific input , such as sorting the list [2, 3, 1, 7].

Define efficiency of an algorithm.

Efficiency is an estimation of the amount of computational resources used by an algorithm , typically expressed in terms of the size of the input .

How can the efficiency of an algorithm be measured informally?

Efficiency can be measured informally by counting the number of times a statement or group of statements executes .

Define decision problem .

A decision problem is a problem with a yes/no answer .

Define optimization problem .

An optimization problem aims to find the best solution among many options .

How many times is DISPLAY executed when this code segment runs? REPEAT 4 TIMES { REPEAT 3 TIMES { DISPLAY("*") } }

DISPLAY is executed 12 times (4 × 3).

Which algorithm efficiencies run in a reasonable amount of time ?

Algorithms with polynomial efficiency or lower (constant, linear, square, cube, and so on) run in a reasonable amount of time.

Which algorithm efficiencies run in an unreasonable amount of time ?

Algorithms with exponential or factorial efficiency run in an unreasonable amount of time.

True or False? Whether an algorithm runs in a reasonable amount of time depends on how fast it runs on a single input.

False. It depends on how efficiency scales with input size , not on speed for any single input.

A heuristic is an approach that produces a solution not guaranteed to be optimal , used when techniques that always find an optimal solution are impractical .

When a problem cannot be solved in a reasonable amount of time, ___________ solutions are sought instead of exact ones.

When a problem cannot be solved in a reasonable amount of time, approximate solutions are sought instead of exact ones.

Why do algorithms with exponential efficiency run in an unreasonable amount of time?

Exponential algorithms run in an unreasonable amount of time because the number of steps grows too quickly to be practical on large inputs.

AP®Computer ScienceCollege BoardComputer Science PrinciplesFlashcardsUnit 3: Algorithms and ProgrammingAlgorithmic Efficiency

Algorithmic Efficiency (College Board AP® Computer Science Principles): Flashcards

1/13

0Still learning

Know0

FrontEfficiency of an algorithm
Define problem (in computing).

Was this flashcard helpful?

Cards in this collection (13)

Define problem (in computing).
A problem is a general description of a task that can (or cannot) be solved algorithmically.
Define instance of a problem.
An instance of a problem is the problem with a specific input, such as sorting the list [2, 3, 1, 7].
Define efficiency of an algorithm.
Efficiency is an estimation of the amount of computational resources used by an algorithm, typically expressed in terms of the size of the input.
How can the efficiency of an algorithm be measured informally?
Efficiency can be measured informally by counting the number of times a statement or group of statements executes.
Define decision problem.
A decision problem is a problem with a yes/no answer.
Define optimization problem.
An optimization problem aims to find the best solution among many options.
How many times is DISPLAY executed when this code segment runs?
```
REPEAT 4 TIMES
```
```
{
```
```
   REPEAT 3 TIMES
```
```
   {
```
```
      DISPLAY("*")
```
```
   }
```
```
}
```
DISPLAY is executed 12 times (4 × 3).
Which algorithm efficiencies run in a reasonable amount of time?
Algorithms with polynomial efficiency or lower (constant, linear, square, cube, and so on) run in a reasonable amount of time.
Which algorithm efficiencies run in an unreasonable amount of time?
Algorithms with exponential or factorial efficiency run in an unreasonable amount of time.
True or False?
Whether an algorithm runs in a reasonable amount of time depends on how fast it runs on a single input.
False.
It depends on how efficiency scales with input size, not on speed for any single input.
Define heuristic.
A heuristic is an approach that produces a solution not guaranteed to be optimal, used when techniques that always find an optimal solution are impractical.
When a problem cannot be solved in a reasonable amount of time, ___________ solutions are sought instead of exact ones.
When a problem cannot be solved in a reasonable amount of time, approximate solutions are sought instead of exact ones.
Why do algorithms with exponential efficiency run in an unreasonable amount of time?
Exponential algorithms run in an unreasonable amount of time because the number of steps grows too quickly to be practical on large inputs.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:SimulationsNext:Undecidable Problems