AP CSP U10 Terms (BIG IDEA 3) Algorithms and Programming

Binary Search

a search algorithm that starts at the middle of a 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

Efficiency

a measure of how many steps are needed to complete an algorithm

Linear Search

a search algorithm which checks each element of a list, in order, until the desired value is found or all elements in the list have been checked

Algorithm

a finite set of instructions that accomplish a task

• steps to solve a problem

• ex: calculate grade avg, run ac until it reaches 72, and calculate shortest route

Iteration

a repetitive portion of an algorithm which repeats a specified number of times or until a given condition is met

• Repeating statements “n” times

• For loops and while loops

• “Repeat for all values in this list”

Problem

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

Selection

deciding which steps to do next

Sequencing

putting steps in an order

Distributed Computing

a model in which multiple devices run programs

• heavy duty processing

• More data

• Run the same program

• Results sent to parent computer

Parallel Computing

a model in which programs are broken into small pieces, some of which are run simultaneously

• cuts time and runs faster

• Code is broken into smaller sections

Sequential Computing

a model in which programs run in order, one command at a time

1. Order of step of an algorithm

Speedup

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

Decision/decidable Problem

a problem with a yes/no answer (e.g., is there a path from A to B?)

Heuristic

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

• quick and sufficient

Optimization Problem

a problem to find the "best" solution among many (e.g., what is the shortest path from A to B?)

Undecidable Problem

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

Reasonable Time

Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) 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

Selection Statements

If statements

• True or false question

• Yes or no