Unit 5 BJC

problem

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

Linear Search or Sequential Search

An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten. This search also checks each element of a list in order

binary search

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. Partial Traversing.

efficiency

The relationship between the input size and the number of steps required to solve a problem is the…. of the algorithm used to solve the problem.s

sublinear time

• An algorithm takes…if the number of steps grows more slowly than the size.

constant time

An algorithm takes…if it takes the same number of steps regardless of input size

quadratic time

An algorithm takes…if the number of steps is proportional to the square of the input size.

linear time

An algorithm takes…if the number of steps is proportional to the input size; doubling the input size doubles the time required.

polynomial time

An algorithm takes…if 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³).

exponential time

An algorithm takes…if 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.

reasonable time

describes any algorithm that runs in polynomial time. Exponential time algorithms are not considered this…

heuristics

polynomial-time algorithms that don't solve the problem exactly, but give a good enough approximation. Called “hill climbing” meaning it will find the best nearby path but there might be a better path farther away.

Decision Problem

a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?")

Optimization Problem

• A problem with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?").

decidable problem

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

undecidable 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.

sequential Computing

operations are performed in order one at a time

parallel computing

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

distributed computing

a form of parallel computing that uses multiple computers (perhaps even spread out around the world)

Processor

a piece of circuitry inside a computer that processes the instructions from computer programs

speedup

Programmers refer to the….of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution

Simulation

computer representations of real things or situations that vary over time. A… is an abstraction designed for a particular purpose.

Data

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

Information

humanly-useful patterns extracted from data

correlation

a particular kind of information, namely a dependence between two variables

Insight

a meaningful conclusion drawn from analyzing information

record

one row in a dataset (other than the first row, which contains the column headings)

field

one item of a record in a dataset

column

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

Classifying data

distributing data into groups based on common characteristics

Metadata

data about data. For example, the piece of data may be an image, while the metadata may include the date of creation or the file size of the image

Infinite Loop

a sequence of computer instructions that repeats forever

unsolvable problem

no algorithm can ever be written to find the solution

Undecidable Problem

no algorithm can ever be written that will always give a correct true/false decision for every input value. These are a subcategory of unsolvable problems that include only problems that should have a yes/no answer (such as: does my code have a bug?)