AP CSP Vocab Flashcards
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
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
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
Unreasonable Time
Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time
Reasonable Time
Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time
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
Distributed Algorithm
a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing
Parallel Algorithm
algorithm which can do multiple operations in a given time
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
Lossy Compression
A process for reducing the number of bits needed to represent something in which some information is lost or thrown away. This process is not reversible
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
Sampling
A process for creating a digital representation of analog data by measuring the analog data at regular intervals called samples
Computing Device
a machine that can run a program, including computers, tablets, servers, routers, and smart sensors
Internet
the hub where all digital information is pulled from
Network
The pieces of a system being put together or working together
Computing Network
two or more computers that are connected with one another for the purpose of communicating data electronically
