ap comp sci unit 6 and 7

Algorithm

a finite set of instructions that accomplish a task

Argument

the value passed to the parameter

API

Application Program Interface - specifications for how functions in a library behave and can be used

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

Decision Problem

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

Distributed Computing

a model in which programs are run by multiple devices

Efficiency

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

Heuristic

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

Iteration

doing some steps over and over

Library

a group of functions (procedures) that may be used in creating new programs

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

Modularity

the subdivision of a computer program into separate subprograms

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?)

Parallel Computing

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

Parameter

a variable in a function definition. Used as a placeholder for values that will be passed through the function.

Problem

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

Procedural Abstraction

a process and allows a procedure to be used only knowing what it does, not how it does it. Procedural abstraction allows a solution to a large problem to be based on the solution of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems. Libraries and functions use procedural abstraction.

Reasonable Time

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

Return

used to return the flow of control to the point where the procedure (also known as a function) was called and to return the value of expression

Selection

deciding which steps to do next

Sequencing

putting steps in an order

Sequential Computing

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

Speedup

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

Undecidable Problem

a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer. They are a type of problem for which it has been proven that there simply is no algorithm that will always produce a correct result. The issue isn't simply that it takes a long time, but that it is demonstrably impossible to write such an algorithm

Unreasonable Time

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

Unreasonable time algorithms

can theoretically be run and will produce a correct solution. They just grow in size so quickly, even for small inputs, that it is usually unreasonable to run that algorithm