<h3 id=algorithm class='section-heading anchor-link glossary-anchor-link'>Algorithm</h3>

A step by step process that describes how to solve a problem and/or complete a task, which will always give a result.

See also introduction, computer program, algorithm cost, searching algorithms, and sorting algorithms.

### Alphabet

In formal languages, a list of characters that may occur in a language, or more generally, a list of all possible inputs that might happen.

See also Formal languages.

### Binary Search

Searching a sorted list by looking at the middle item, and then searching the appropriate half recursively (used for phone books, dictionaries and computer algorithms).

<h3 id=brooks-law class='section-heading anchor-link glossary-anchor-link'>Brooks' law</h3>

An observation that adding more people to a project that is running late may actually slow it down more.

See also software engineering.

### Chomsky Hierarchy

A hierarchy of four classifications of formal languages, ranging from simple regular expressions to very flexible (but computationally difficult) grammars.

See also Formal languages.

### Complexity

How long it takes to solve a problem. A problem has an inherent complexity (minimum time needed to solve it); any algorithm to solve the problem will have a higher complexity (take at least that long).

See also problems and algorithms.

### Digital signature

An encryption system that allows the receiver to verify that a document was sent by the person who claims to have sent it.

<h3 id=finite-state-automaton class='section-heading anchor-link glossary-anchor-link'>Finite State Automaton</h3>

In formal languages, a simple 'machine' that has states, and transitions from one state to another based on strings of input symbols.

See also Formal languages, FSA abbreviation, Formal languages, and related to regular expressions.

### Finite State Machine

Alternative name for a finite state automaton.

See also Formal languages.

### Grammar

In formal languages, a set of rules for specifying a language, for example, to specify syntax for programming languages.

See also Formal languages.

### Interpolation

Working out values between some given values; for example, if a sequence of 5 numbers starts with 3 and finishes with 11, we might interpolate the values 5, 7, 9 in between.

See also compressing images.

### Language

In formal languages, it's the set of all strings that the language accepts i.e. that are correct.

See also Formal languages, and regular expression.

### Pattern matching

In formal languages, finding text that matches a particular rule, typically using a regular expression to give the rule.

See also Formal languages.

### Pixel

This term is an abbreviation of *picture element*, the name given to the tiny squares that make up a grid that is used to represent images on a computer.

See also definition.

### Quicksort

A process for achieving an outcome, normally for a general problem such as searching, sorting, finding an optimal path through a map and so on.

<h3 id=regular-expression class='section-heading anchor-link glossary-anchor-link'>Regular expression</h3>

A formula used to describe a pattern in a text that is to be matched or searched for. These are typically used for finding elements of a program (such as variable names) and checking input in forms (such as checking that an email address has the right format.)

See also introduction, and abbreviations.

### Slope

This is a way of expressing the angle or gradient of a line. The slope is simply how far up the line goes for every unit we move to the right. For example, if we have a line with a slope of 2, then after moving 3 units to the right, it will have gone up 6 units. A line with a slope of 0 is horizontal. Normally the slope of a line is represented using the symbol \(m\).

See also computer graphics.

### String

A sequence of characters.

See also Formal languages, and regular expression.

### tractable

A *tractable* problem is one that can be solved in a reasonable amount of time; usually the distinction between tractable and intractable is drawn at the boundary between problems that can be solved in an amount of time that is polynomial; those that require exponential time are regarded as intractable.

See also encryption, and complexity and tractability chapter.

### Transition

In a finite state machine, the links between the states.

See also Formal languages.