AP CSP BJC Unit 5 Vocabulary

problem

general description of task; may (or may not) be solved algorithmically

instance of a problem

one case of a problem, with specific inputs

linear/sequential search

checks each element of a list in order (takes linear time); can use sorted or unsorted lists; complete traversal

binary search

starts in the middle of a sorted list and repeatedly eliminates half of the list until it either finds the desired value or eliminates the entire list; must use sorted lists; partial traversal

efficiency

relationship between input size of a problem and the number of steps required to solve it

linear time

number of steps is proportional to input size (doubling input doubles time required)

sublinear time

number of steps grows more slowly than input size

constant time

takes same number of steps regardless of input size

quadratic time

number of steps is proportional to the square of the input size

polynomial time

number of steps is less than or equal to a power of the size of the input

exponential time

number of steps is proportional to an exponential function of the size of the input

reasonable time

any algorithm that runs in polynomial time (not exponential)

heuristic solution

polynomial-time algorithm that gives an approximation of the solution

decision problem

problem with true/false answer

optimization problem

problem with goal of finding the best solution among many

decidable problem

decision problem where it is possible to write an algorithm that will give a correct output for all inputs

undecidable problem

decision problem where it is not possible to write an algorithm that will give a correct output for all inputs (may be possible for some inputs)

sequential computing

operations performed in order one at a time

parallel computing

program is broken into smaller steps, some of which are performed at the same time

distributed computing

form of parallel computing that uses multiple computers

processor

piece of circuitry inside a computer that processes instructions from computer programs

speedup

how many times as fast the parallel solution is compared to the sequential solution (sequential/parallel; will always be greater than or equal to 1)

model

computer representation of an object (or system of objects) in the real world

simulation

algorithm that uses models of real things or situations that vary over time; abstraction designed for a particular purpose

data

values that the computer receives from various sources

information

humanly-useful patterns extracted from data

correlation

type of information; dependence between two variables

insight

meaningful conclusion drawn from analyzing information

CSV (comma-separated values)

tables of data stored with commas between each item in a row and line breaks between each row in the table

spreadsheet

two-dimensional data organized in rows and columns

dataset

general term for any collection of data

record

one row in a dataset (other than column headings); horizontal slice; e.g. data for one student

field

one item of a record in a dataset; e.g. one student’s homeroom teacher

column

list containing data from one field for all records of a dataset; vertical slice; e.g. every students’ homeroom teachers

cleaning data

process of making the data uniform without changing its meaning

bias

reasons the data might not mean what they seem to mean

classifying data

distributing data into groups based on common characteristics

mode

value that appears most often in a dataset

metadata

data about data; gives additional information about the data

proof by contradiction

two-step proof that a statement is false

1. assuming the statement is true

2. showing the assumption creates a contradiction

undecidable problem

might be true or might be false; no algorithm can ever be written that will always give a correct true/false decision for every input value; unsolvable

self-contradictory statement

can be neither true nor false

provably true/false

can indisputably be proven true or false

infinite loop

sequence of computer instructions that repeats forever

unsolvable problem

no algorithm can ever be written to find the solution

halting problem

problem of determining whether the program will finish running or continue to run forever; undecidable

Halting Theorem

proof that halting problem is undecidable; first proved by Alan Turing

autonomous weapon

weapon that can decide to fire itself without human decision-making

drone

remotely-piloted aircraft