keywords:
Bookmark and Share



Front Back
0?1 knapsack
A variant of the knapsack problem in which only one copy of each item is available.
3SAT
The decision problem whether there is an interpretation that makes a 3CNF propositional logic formula true.
abstract data type (ADT)
A definition of a data structure only in terms of the operations that may be performed on it and by the pre- and postconditions of those operations.
abstraction
Abstraction provides a handle on complexity by either ignoring detail by means of a model hiding detail through the use of encapsulation.
acyclic (graph)
A graph containing no cycles.
adjacency list
A means of representing a graph as a collection of unordered lists
adjacency matrix
A means of representing a graph showing which vertices of a graph are adjacent to which other vertices.
algorithm
A precisely stated list of step by step instructions
algorithmic complexity
See complexity.
alphabet
In string-searching algorithms, the set of distinct characters that are used to construct the search string.

In Python implementations, an alphabet such as {G, A, C, T} is often represented as a string (i.e. 'GACT') though it could be represented as a proper set of strings: {'G', 'A', 'C', 'T'}.

ambiguous
When an expression of any natural language, such as English, or any formal language, such as predicate logic, can be interpreted in more than one way, it is described as ambiguous. Ambiguity is the property of being ambiguous.
approximate algorithm
An algorithm that does not always return an optimal solution. On a very restrictive interpretation of this concept, an approximate algorithm should always return solutions that are within a fixed range from the optimal solution.
approximate algorithms
A class of algorithms which will not necessarily find the best solution to a problem
arcs
See edges.
argument (logic)
A demonstration that a particular proposition (the conclusion, C) follows from, or is implied by, one or more other propositions (the premises, P1, P2, …, Pn).

In Unit 6, arguments are laid out vertically:



In Unit 7, an alternative notation is used: {P1, P2, …, Pn} ⊢ C.

argument (predicate)
An entity to which a predicate applies.
argument (programming)
A value required by a function in a programming language.
arity
The arity of a predicate or function is the number of arguments that the predicate or function takes.
assignment (predicate logic)
An assignment in predicate logic associates each constant with an object in the domain and each n-ary predicate with an n-ary relation.
assignment (programming)
A statement that stores a value in a variable.
assignment (propositional logic)
An assignment in propositional logic associates each propositional variable with a truth value.
atomic
Used to refer to the data types of a programming language, such as integers, Booleans, etc., which cannot be divided or further broken down in any way.
atomic formula
In predicate logic, an atomic formula is anexpression of the form:

p(t1, t2, …, tn)

where p is a predicate symbol of arity n, and each of the t1, t2, …, tn is either a constantsymbol or a variable symbol.

average case
An input to an algorithm that would be expected in normal circumstances
average-case analysis
The average-case analysis of an algorithm consists of an analysis of the efficiency of an algorithm using a model which identifies those inputs that occur in the real world (as opposed to all possible inputs).
AVL tree
A type of binary search tree in which every node has a balance factor of no less than -1 and no greater than 1.
backtracking
In tree or graph search algorithms, the process of returning to an earlier state to explore a new set of possible states from there.
balance factor
In an AVL tree, the height of a node’s right subtree subtracted from the height of its left subtree.
best case
An input to an algorithm that would result in its quickest performance. For example, the best case for bubble sort is an input sequence that is already sorted.
best first search (BeFS)
A form of algorithm for traversing trees or graphs in which the next node chosen for exploration is the one with the best value, where this value is calculated according to some heuristic.
Big-O notation
A symbolism used in mathematics to indicate an upper bound on how fast a function f(n) grows as n increases. Used in computer science to approximate the number of computational steps required for an algorithm to complete for inputs of size n.
binary alphabet
The set {0,1}
binary (function
A binary function, predicate or relation has an arity of 2.
binary heap
A subclass of complete binary trees in which, for every node x with parent p, eitherp will be smaller than or equal to x (a min heap), or p will be greater than or equal to x(a max heap).
binary search
A classic divide-and-conquer algorithm for searching sorted sequences for a specified item. It works by progressively halving the length of the search sequence, and discarding the sub-sequences that could not possibly hold the search item.
binary search tree (BST)
A binary tree with the property that, for every node p, all the keys within p’s left subtree are less than the key of p; and all the keys within p’s right subtree are greater than or equal to the key of p.
binary tree
A tree in which every node may only have 0, 1 or 2 children.
bit string
A string of 0s and 1s used to represent a genome in genetic algorithms.
body (of a loop)
The group of statements that a loop performs repeatedly.
Boolean expression
An expression that evaluates to True or False.
boundary value errors
Errors occurring in computer programs at run time, resulting from the incorrect expression of a loop guard or the Boolean condition of a selection statement.
bound (variable)
A variable which occurs within the scope of a quantifier.
Boyer?Moore algorithm
An algorithm for efficiently searching for substrings of a given string.
breadth first search (BFS)
A form of algorithm for traversing trees or graphs in which all the child nodes of a given state are explored before any of the children of these states.
brute-force algorithm
Generally any algorithm that proceeds towards a solution by trying every available possibility.
bucket
Another term for a slot in a hash table.
caching
See memoisation.
cardinality
The cardinality of a set is the number of elements which it contains.
Cartesian product
The Cartesian product of the sets S1, S2, …,Sn is the set of tuples:

{(x1, x2, …, xn) : x1 ∈ S1, x2 ∈ S2, …, xn ∈Sn}

certificate
A certificate provides the information that is needed to verify ? for a specific decision problem and input ? that the answer is 1.
x of y cards Next > >> >|