A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.
Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.
The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.
A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.
An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.
This section covers two computational models:
Distributed computing is a form of parallel computing that uses multiple computers (perhaps even spread out around the world).
A processor is a piece of circuitry inside a computer that processes the instructions from computer programs.
Image credit: Wikipedia user Solipsist
Programmers refer to the speedup of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution:
\text{speedup} = \frac{\text{sequential time}}{\text{parallel time}}
Simulations are computer representations of real things or situations that vary over time. A simulation is an abstraction designed for a particular purpose.
A correlation is a particular kind of information, namely a dependence between two variables in a situation. For example in the first picture here, as one variable goes up the other goes down. It's also a correlation when as one variable goes up or down the other changes in the same manner.
Cleaning data is the process of making the data uniform without changing its meaning (such as replacing abbreviations, spellings, and capitalizations with the intended word or converting miles to kilometers). Programmers can use programs to filter and clean digital data, thereby gaining insight and knowledge.
Classifying data is extracting groups of data with a common characteristic.
The mode of a data set is the value that appears most often in it.
Metadata are data about data. For example, the piece of data may be an image, while the metadata may include the date of creation or the file size of the image.
A proof by contradiction is a two-step proof that something is false that is done by:
An undecidable statement might be true or might be false; we don't know which.
A self-contradictory statement can be neither true nor false.
An infinite loop is a sequence of computer instructions that repeats forever.
An unsolvable problem is one for which no algorithm can ever be written to find the solution.
An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value. Undecidable problems are a subcategory of unsolvable problems that include only problems that should have a yes/no answer (such as: does my code have a bug?).