Further Decision - Key Terms

Question 1

Algorithm (C1)

Answer 1

Finite sequence of step-by-step instructions carried out to solve a problem.

Question 2

Trace Table (C1)

Answer 2

Used to record values of each variable as the algorithm

Instruction| n | A | B | C | Print
Step

Question 3

Flow Chart Symbols (C1)

Answer 3

Stretched Circle - Start/End
Rectangle - Instruction
Rhombus - Decision (question)

Question 4

Full-bin packing (C1)

Answer 4

Select ANY items to fill bins as much as possible.

Question 5

Lower bound (C1)

Answer 5

Sum of values / bin size

Allows you to determine what the minimum no. of bins needed and thus whether your answer is optimal.

Question 6

Optimal Solution (C1)

Answer 6

Solution that cannot be improved upon.

(e.g. Bin Packing = Smallest no. of bins)

Question 7

Order (C1)

Answer 7

‘A function of its size.’ If order = f(n), then increasing size of the problem from n to m will increase the run time by a factor of f(m)/f(n).

Identifies how changes in the size of a problem affects the approximate run time of the algorithm.

Linear = n (e.g. Bubble sort
Quadratic = n^2 = Quadratic)
Cubic = n^3

Question 8

Order (continued) (C1)

Answer 8

Increasing size of problem by factor k means:

• Linear alg. = k times longer
• Quadratic alg. = k^2 times longer
• Cubic alg. = k^3 times longer

Question 9

Graph (C2)

Answer 9

Vertices/nodes connected by edges/arcs.

Question 10

Weighted Graph (C2)

Answer 10

(Network)

Each edge has a ‘weight’ - number associated with it.

Question 11

Vertex (C2)

Answer 11

(a.k.a node)

A point on a graph connected by edges.

Question 12

Vertex/Edge Set (C2)

Answer 12

List of vertices/edges.

Question 13

Edge (C2)

Answer 13

(a.k.a arc)

A line segment connecting vertices.

Question 14

Subgraph (C2)

Answer 14

A graph of which the vertices belong to another bigger graph.

Question 15

Degree (C2)

Answer 15

(Valency/Order)

The number of edges connecting to a vertex.

Question 16

Walk (C2)

Answer 16

A route through a graph along edges going from one vertex to the next.

Question 17

Path (C2)

Answer 17

A WALK in which no vertex is visited more than once.

Question 18

Trail (C2)

Answer 18

A WALK in which no edge is visited more than once.

Question 19

Cycle (C2)

Answer 19

A PATH in which the end vertex is the same as the start vertex.

Question 20

Hamiltonian Cycle (C2)

Answer 20

A CYCLE including every vertex within it.

Question 21

Eulerian Circuit (C2)

Answer 21

A TRAIL which traverses every arc and starts and ends at the same vertex.

Question 22

Connected Graph (C2)

Answer 22

All vertices are connected to at least one other vertex.

Question 23

Loop (C2)

Answer 23

An edge/arc that starts and finishes at the same vertex.

Question 24

Simple Graph (C2)

Answer 24

A GRAPH with no loops & at most one edge is connecting to any pair of vertices.

Question 25

Directed Edges (C2)

Answer 25

Edges which have a specific direction associated.

Question 26

Directed Graph (C2)

Answer 26

(disgraph) Graph with directed edges.

Question 27

Undirected Graph (C2)

Answer 27

Edges have no direction. Sum of degrees of vertices = 2 x no. of edges Thus the number of odd vertices must be even or 0. (a.k.a Euler's handshaking lemma)

Question 28

Tree (C2)

Answer 28

A connected graph with no cycles.

Question 29

Spanning Tree (C2)

Answer 29

A subgraph which includes all vertices of the original graph and is a tree.

Question 30

Complete Graph (C2)

Answer 30

A graph in which every vertex is directly connected by a single edge to each of the other vertices.

Question 31

Isomorphic Graphs (C2)

Answer 31

Graphs which show the same information but are drawn differently.

Question 32

Adjacency Matrix (C2)

Answer 32

Each entry describes the number of arcs joining the corresponding vertices. (Symmetrical two-way table)

Question 33

Distance Matrix (C2)

Answer 33

The matrix associated with a weighted graph and so the entries represent the weight of each arc, not the no. of arcs.

Question 34

Planarity Graph (C2)

Answer 34

A graph that can be drawn in a plane such that, when drawn, no two edges meet except at a vertex.

Question 35

Minimum Spanning Tree (C3)

Answer 35

A spanning tree such that the total length of its arcs is as small as possible.

Question 36

Eulerian Graph (C4)

Answer 36

Network containing a trail including every edge that starts and ends at the same vertex. The trail is called a Eulerian Circuit.

Question 37

Semi-Eulerian Graph (C4)

Answer 37

Network containing a trail including every edge but starts and finishes at different vertices. [Any connected graph with exactly 2 odd vertices is Semi-Eulerian]

Question 38

Tour (C5)

Answer 38

Walk which visits every vertex and returns to its starting vertex. (May visit vertices more than once, thus is different to a Hamiltonian cycle)

Question 39

Table of least distances (C5)

Answer 39

Distance matrix which shows the shortest path between any 2 points in a network. (two-way table)

Question 40

Residual Minimum Spanning Tree (C5)

Answer 40

MST for the resulting network after removing a vertex.

Question 41

Decision Variables (C6)

Answer 41

Numbers of each of the things that can be varied. (e.g. 12x)

Question 42

Objective (C6)

Answer 42

Aim of the linear programming problem.

Question 43

Constraints (C6)

Answer 43

Features of a problem that prevent infinite numbers of each of the variables - these form inequalities.

Question 44

Feasible Solution (C6)

Answer 44

Values for decision variables that satisfy the constraints.

Question 45

Feasible Region (C6)

Answer 45

Region which contains all feasible solutions.

Question 46

Optimal solution (C6)

Answer 46

Feasible solution which meets the objective. (May be >1 OS)

Question 47

Slack variables (C7)

Answer 47

Represents the difference between the actual quantity and the maximum possible value. → Takes up 'spare' in function → Used to turn ≤ inequalities into equations

Question 48

Artificial Variable (C7)

Answer 48

Used to ensure each constraint with a surplus variable contains a basic variable. [Type of Surplus variable]

Question 49

Surplus Variable (C7)

Answer 49

→ Take up 'excess' in function → Used to turn ≥ inequalities into equations

Question 50

Precedence/Dependence Table (C8)

Answer 50

Shows which activities must be completed before others are started.

Question 51

'Activity On Arc' Network (C8)

Answer 51

Arc represent activities & nodes represent events (completion of activities)

Question 52

Types of Node (C8)

Answer 52

Source = First Sink = Final

Question 53

Dummy Activity (C8)

Answer 53

Has no time or cost. Aims to show dependencies between activities to avoid 2 arcs starting and ending at the same node. ARC GOES FIRST, THEN DUMMY.

Question 54

Event Times (C8)

Answer 54

Early = Earliest time of arrival at event, allowing for completion of all preceding activities. Late = Latest time event can be left without extending time needed for project.

Question 55

Critical Activity (C8)

Answer 55

Any increase in its duration results in a corresponding increase in duration of entire project. Not every activity connect 2 critical events is a critical activity.

Question 56

Critical Path (C8)

Answer 56

Longest path from source node to sink node contained in network which entirely follows critical activities. Event times: Early = Late THERE CAN BE > 1 CP.

Question 57

Total Float (C8)

Answer 57

Amount of time that an activity's start may be delayed without affecting the duration of the project. TF = Latest finish time - duration - earliest start time TF of a critical activity = 0