### Algorithm

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).

### 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

### 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.

### Finite State Automaton

In formal languages, a simple

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, and 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.

### Regular expression

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