Algorithms - APCSP

Algorithm

A finite step of instructions that accomplishes a task

Parallel

Some steps are performed at the same time

Sequential

Steps are performed in order, one at a time

Iteration

Doing some steps over and over (for loops)

Sequencing

Putting steps in an order

Selection

Deciding which steps to do next (if/else)

Linear Search

Checks possibly through all numbers (Ex: (1,2,3,4,5) max amount of checks → 5)

Binary Search

Searches through data by going by halfs (Ex: (1,4,6,10,15,20) Guesses (for 20): 6,15,20.

Reasonable Time

Algorithms with a polynomial efficiency, or lower (log, linear, polynomial) are said to run in 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

Heuristic

provides a “good enough” solution to a problem when an actual solution is impractical or impossible

Undecidable Problem

A problem for which no algorithm can be constructed that is elways capable of providing a correct yes-or-no answer (Ex: The Halting Problem)

Sequential Computing

Programs run in an order, one command at a time

Parallel Computing

Programs are broken into small pieces, some of which are run simultaneously

Distributed Computing

Programs are run by multiple devices

Speed Up

The time used to complete a task sequentially divided by the time used to complete a task in parallel

Intractable Problem

A problem where there is only an inefficient algorithm to solve it (Ex: Traveling Salesman)