# D1 Maths Definitions

HideShow resource information
• Created by: Lizzy Day
• Created on: 08-03-15 18:26
Algorithm
a precise set of instructions so clear that it will allow anyone/anything to use it to achieve a particular goal in a specified number of steps.
1 of 48
Flow Chart
a visual representation of an algorithm in which boxes and lines are used to indicate different steps in a process
2 of 48
Bubble sort
an algorithm to sort a list into alphabetical or numerical order
3 of 48
next to eachother.
4 of 48
Pass
one run through a set of steps in an algorithm which may be repeated
5 of 48
Quick sort
an algorithm to sort a list into alphabetical or numerical order
6 of 48
Pivot
the item selected in the quick sort which are either less than or more than a particular pivot value. Each sub-list remains in the order of the items before comparison with the pivot.
7 of 48
Binary Search
an algorithm to check whether a particular value appears in an ordered numerical or alphabetical list
8 of 48
Ordered List
a list that has been sorted, perhaps by the quick sort or bubble sort algorithm
9 of 48
Bin-packing algorithm
a class of problems in which it is desirable to fit items of varying small sizes into containers of a larger size, called bins. The sizes may typically refer to lengths or times.
10 of 48
Optimal Solution
the best possible answer to a problem. A sub-optimal solution is one which is not optimal.
11 of 48
First-fit algorithm
a quick, but often sub-optimal, bin-packing algorithm in which unsorted items are placed in the first bin possible
12 of 48
First-fit decreasing algorithm
an easy, two-step bin-packing algorithm hat gives fairly good, but possibly sub-optimal solutions by solving the items first, then applying the first-fit algorithm
13 of 48
Full-Bin packing
a bin-packing routine which relies on intelligence. The user spots combinations of items that will fit together and then fits remaining items by using the first-fit algorithm. It is slow but often results in an optimal solution
14 of 48
Graph
an object consisting of points which are connected by lines
15 of 48
Vertex
a point on a graph
16 of 48
Node
another name for a vertex or a point on a graph
17 of 48
Edge
a line connecting a pair of points on a graph. These 'points' may be a single point
18 of 48
Arc
another name for an edge.
19 of 48
Weight
a number associated with an edge (arc) that represents length, cost, time or some other variable associated with this line
20 of 48
Weighted Graph
a graph in which all edges have a weight
21 of 48
Network
a shorter name for a weighted graph
22 of 48
Vertex set
the set of all nodes or vertices of a graph
23 of 48
Edge set
the set of all arcs or edges of a graph
24 of 48
Subgraph
starting from an original graph G, select some or all of the vertices and some of the edges. A subgraph is part of the original graph
25 of 48
Degree (of a vertex)
is the number of edges incident to it. The degree of a node is the number of arcs coming from it
26 of 48
Valency (of a vertex)
another name for the degree of a vertex
27 of 48
Order (of a vertex)
yet another name for the degree of a vertex
28 of 48
Handshaking lemma
the sum of the degrees of all vertices in a graph must be even since we count each edge twice- once from each end of the 'handshake' between it's vertices.
29 of 48
Even Degree
a vertex which has a degree which is an even number
30 of 48
Odd degree
a vertex which has a degree which is an odd number
31 of 48
Walk
a finite sequence of edges, such that the end vertex of one edge is the start of the next edge
32 of 48
Path
a finite sequence of edges, such that the end vertex of one edge is the start of the next edge and in which no vertex appears more than once.
33 of 48
Cycle
a path which is then 'closed' by the addition of an extra edge which joins the path's ending vertex back to the paths starting vetex
34 of 48
Circuit
another name for a cycle
35 of 48
Connected (vertex)
two vertices are connected if there is a path between them.
36 of 48
Connected (graph)
a graph is connected if all possible pairs of vertices in it are connected
37 of 48
Loop
an edge that starts and finished at the same vertex
38 of 48
Simple graph
a graph in which there are no loops and no pair of vertices has more than one edge joining them directly
39 of 48
Directed edge
an edge in which the direction of connection matters and is shown by an arrow
40 of 48
Directed graph
a graph that contains directed edges
41 of 48
Digraph
a directed graph
42 of 48
Tree
a connected graph that contains no cycles
43 of 48
Spanning tree
a subgraph which includes all the vertices but only sufficient of the edges to be a tree
44 of 48
Bipartite graph
a graph which contains two sets of vertices, X and Y in which all the edges join a vertex in set X to a vertex in set Y
45 of 48
Eulerian graph
all even nodes
46 of 48
Semi Eulerian graph
exactly 2 odd nodes
47 of 48
Non Eulerian graph
all odd nodes
48 of 48

## Other cards in this set

### Card 2

#### Front

a visual representation of an algorithm in which boxes and lines are used to indicate different steps in a process

Flow Chart

### Card 3

#### Front

an algorithm to sort a list into alphabetical or numerical order

### Card 4

#### Front

next to eachother.

### Card 5

#### Front

one run through a set of steps in an algorithm which may be repeated