Unit 10 - Algorithms Review

AP CSP

Problem

• A general description of a task that can (or cannot) be solved with an algorithm

Algorithm

• A finite set of instructions that accomplish a task

Building Blocks

• All algorithms can be created by combining three types of steps: sequencing, selection, iteration

Sequencing

• putting steps in a specific order

Selection

• deciding which steps to do next based on a condition

Iteration

• repeating some steps over and over again

Efficiency

• a measure of how many steps are required to complete an algorithm

Linear Search

• a search algorithm that checks every element of a list in order until the value is found or all elements are checked

• as you add more inputs, the number of steps grows at the same rate

Binary Search

• a search algorithm that starts at the middle of a SORTED set of numbers and eliminated half of the remaining data with each step

• much faster than linear search for large datasets but the data must be sorted first

Reasonable Time

• algorithms with polynomial efficiency or lower(such as constant, linear, square, or cube) are considered to run in this time

Unreasonable Time

• algorithms with exponential or factorial efficiencies are considered this because the number of steps grows to quickly to be practical for large inputs

Decision Problem

• a problem with yes or no answer

Optimization Problem

• a problem where the goal is to find the “best“ solution among many possibilities

Heuristic

• a technique that provides a good enough solution to a problem when an actual. perfect solution is impossible/impractical to calculate in a reasonable time

Undecidable Problem

• a problem for which no algorithm can ever be built that is always capable of providing a correct yes or no answer

• An example is the Halting problem

Sequential Computing

• a model where steps are performed one at a time, in order

Parallel Computing

• a model where some steps are performed at the same time to speed up the process

Distributed Computing

• multiple devices are used together to run a program or solve a problem

Speedup

• calculated by dividing the time it takes for a sequential solution by the time it takes for a parallel solution

Limitations

• speedup is NEVER EQUAL to the number of processes used because some portions of an algorithm cannot be made parallel and eventually reach a limit