CSP Vocab

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.

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.

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. 

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

Traversal

•  the process of accessing each item in a list one at a time.

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. 

Library

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

API

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

Overflow Error

• Error from attempting to represent a number that is too large.

Round-off Error

• Error from attempting to represent a number that is too precise. The value is rounded.

Analog Data

• Data with values that change continuously, or smoothly, over time. Some examples of analog data include music, colors of a painting, or position of a sprinter during a race.

Digital Data

• Data that changes discretely through a finite set of possible values