APCSP Unit 10

Algorithm

A finite set of instructions that accomplish a task and solve certain problems. There are usually many algorithms to solve the same problem and many ways to express one algorithm.

Sequencing

Putting steps in an order.

Selection

Deciding which steps to do next.

Iteration

Doing some steps over and over.

Common Algorithms

Determining the maximum or minimum number from two or more numbers; calculating the average of a group of numbers.

Searching

Finding the needed element from everything in the dataset or determining that it is not there.

Linear Search/Sequential Search

A search algorithm which checks each element of a list in order until the desired value is found or all the elements in the list have been checked. The more elements you add the less efficient it will be.

Binary Search

A search algorithm that starts at the middle of the sorted set of numbers and removes half of the data; this process repeats until the desired value is found or all elements have been eliminated; logarithmic curve.

Parallel Processing

Problem is being solved at the same time, which takes a lot of computing space; happens within one machine.

Instance of a Problem

A specific example.

Decision Problem

Has a yes or no answer.

Optimization Problem

A problem that should find the best solution.

Algorithm Efficiency

A measure of how many steps are needed to complete an algorithm; can be determined mathematically.

Polynomial Efficiency

An algorithm whose efficiency includes the variable in the base (n^2).

Exponential Efficiency

An algorithm whose efficiency includes the variable in the exponent (2^n).

Reasonable Time

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

Unreasonable Time

Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

Limits of Algorithms

Some problems do not have algorithms efficient enough to solve.

Sequential Computing

Programs run in order, one command at a time.

Parallel Computing

Programs are broken into small pieces, some of which are run simultaneously; faster than distributed computing.

Distributed Computing

Programs are run by multiple devices.

Speedup

Sequential time divided by parallel time.

Heuristic

Provides a "good enough" solution to a problem when the actual solution is impractical or impossible; close enough to use as a solution.

Decidable Problem

An algorithm can be written that results in a correct "yes" or "no" answer for all inputs, like determining if a number is prime.

Undecidable Problem

Does not have an algorithm that can give a correct "yes" or "no" for all the cases of the problem.