AP CSP Algorithm Unit

Algorithm

a step-by-step procedure for solving a problem

Efficiency

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

Linear Search Algorithm

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.

Binary Search Algorithm

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.

reasonable time algorithm

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

unreasonable time algorithm

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

Decision Problem

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

Optimization Problem

a problem with the goal of finding 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

Sequential Computing

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

Parallel Computing

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

distributed computing

a model in which programs are run by multiple devices

Speedup

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

selection programming structure

allows the computer to make a selection between alternative conditions; decisions choice, if/else

sequential programming structure

instructions that the computer follows in order, one by one, from top to bottom

Iterative Programming

A process of repeating a set of instructions a specified number of times or until a condition is met. Such as in a repetition of a process or a newer version of development in computer science.

Insertion Sort Algorithm

algorithm used to sort a list, will create a temp list

and pulls one item out of the original list at a time

and inserts it into the proper place in the temp list

Bubble Sort Algorithm

Looks at one pair of data at a time, puts them in order, then moves to the right to put the next pair in order, and goes all the way down the line then restarts until all are in order

variable

is a placeholder for a value

data types

are different categories of data that your computer can represent

array

are used to store multiple values in a single variable

Array Index

​The location of an array element, the first index always starts with [1,2...]

elements

are individual values in a list

Boolean Value

a data type that is either true or false.

procedure

a small section of a program that performs a specific task.

parameters

identify values that are passed into a function/ procedure

Arguments

The values that the programmer provides in the function call.

Application Programming Interface (API)

a set of routines, protocols, and tools for building software applications

simulation

A representation of a situation or problem with a similar but simpler model or a more easily manipulated model in order to determine experimental results.