# D1 Maths Definitions

0.0 / 5

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

Adjacent

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

#### Back

Flow Chart

### Card 3

#### Front

an algorithm to sort a list into alphabetical or numerical order

#### Back

### Card 4

#### Front

next to eachother.

#### Back

### Card 5

#### Front

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

#### Back

## Similar Mathematics resources:

3.0 / 5

0.0 / 5

0.0 / 5

2.0 / 5

3.5 / 5

0.0 / 5

0.0 / 5

2.5 / 5

2.0 / 5

## Comments

No comments have yet been made