BJC Unit 5 Review

A problem

a general description of a task that may (or may not) be solved algorithmically

A linear search (or sequential search) algorithm…

checks each element of a list in order, a process which takes linear time.

A binary search algorithm starts…

in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.

Linear search does a ________traversal of the list. Binary search saves time by doing a ___________ traversal of the list.

complete, partial

The relationship between the input size and the number of steps required to solve a problem

the efficiency of the algorithm used to solve the problem.

the number of steps is proportional to the input size; doubling the input size doubles the time required

linear time

the number of steps grows more slowly than the size

sublinear time

it takes the same number of steps regardless of input size

constant time

the number of steps is proportional to the square of the input size

quadratic time

the number of steps is less than or equal to a power of the size of the input, such as constant (n⁰), sublinear, linear (n¹), quadratic (n²), or cubic (n³)

polynomial time

the number of steps is proportional to an exponential function of the size of the input, such as 2ⁿ, 10ⁿ, etc., which is much slower than any polynomial

exponential time

a problem with a true/false answer

decision problem

a problem with the goal of finding the best solution among many

optimization problem

a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs

A decidable problem

It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

An undecidable problem

operations are performed in order one at a time

sequential computing

the program is broken into smaller steps, some of which are performed at the same time

parallel computing

a form of parallel computing that uses multiple computers

Distributed computing

computer representations of real things or situations that vary over time.

Simulations

the values that computers receive from various sources, including human activity, sensors, etc.

Data

the humanly-useful patterns extracted from data

Information

one row in a dataset

record

one item of a record in a dataset

field

a list containing the data from one field for all records in a dataset

column

data about data

Metadata

reasonable time

polynomial time

unreasonable time

exponential time

dual-use technology

application of technology both in civilian and military targets

how many times as fast the parallel solution is compared to the sequential solution

speedup