Further Decision

Question 1

Trace Table (C1)

Answer 1

Used to record values of each variable as the algorithm

e.g.
- Instruction Step
- n
- A
- B
- C
- Print

Question 2

Flow Charts (C1)

Answer 2

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

Question 3

Bubble Sort (C1)

Answer 3

Comparison of adjacent items in a list, if they are out of order, you swap them.

Once a pass is completed without any swaps, the list is in order.

ALWAYS SORT BACK TO FRONT

‘Ascending’ (Rising value) => Start with organising biggest values at the end.

‘Descending’ (Decreasing value) => Start with organising smallest values at end.

Question 4

Quick Sort (C1)

Answer 4

Select a pivot then split items into 2 sub-lists;
- Values < Pivot
- Values > Pivot

Repeat until all items have become pivots - the list should now be in order.

Question 5

First-Fit Algorithm (C1)

Answer 5

Consider items in order given - fitting into first bin possible.

Question 6

First-Fit DECREASING Algorithm (C1)

Answer 6

Same as FF but first sort items into descending value before applying the algorithm.

(Fit into first bin possible)

Question 7

Full-bin packing (C1)

Answer 7

Select ANY items to fill bins as much as possible.

Question 8

Lower bound (C1)

Answer 8

Sum of values / bin size

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

Question 9

Order (a.k.a complexity) of an Algorithm (C1)

Answer 9

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

e.g. Bubble sort = Quadratic Order

Linear order = n
Quadratic order = n^2
Cubic order = n^3

Question 10

Vertex (node) (C2)

Answer 10

A point on a graph connected by edges. (a.k.a node)

A ist of vertices is sometimes called the vertex set.

Question 11

Edge (arc) (C2)

Answer 11

A line segment connecting vertices. (a.k.a arc)

Question 12

Subgraph (C2)

Answer 12

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

Question 13

Degree/Valency/Order (C2)

Answer 13

The number of edges incident to a vertex.

Question 14

Walk (C2)

Answer 14

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

Question 15

Path (C2)

Answer 15

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

Question 16

Trail (C2)

Answer 16

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

Question 17

Cycle (C2)

Answer 17

A walk in which the end vertex is the same as the start vertex.
(And no vertex is visited more than once)

Question 18

Hamiltonian Cycle (C2)

Answer 18

A cycle including every vertex within it.

Question 19

Connected Graph (C2)

Answer 19

All vertices are connected to at least one other vertex.

Question 20

Loop (C2)

Answer 20

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

Question 21

Simple Graph (C2)

Answer 21

One in which there are no loops & at most one edge is connecting to any pair of vertices.

Question 22

Directed Edges (C2)

Answer 22

Edges which have a specific direction associated with them

Question 23

Undirected Graph (C2)

Answer 23

Edges have no direction.

Sum of degrees of vertices = 2 x no. of edges

Thus the number of odd vertices must be even -
Euler’s handshaking lemma.

Question 24

Tree (C2)

Answer 24

A connected graph with no cycles.

Question 25

Spanning Tree (C2)

Answer 25

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

Question 26

Complete Graph (C2)

Answer 26

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

Question 27

Isomorphic Graphs (C2)

Answer 27

Graphs which show the same information but are drawn differently.

Question 28

Adjacency Matrix (C2)

Answer 28

Each entry describes the number of arcs joining the corresponding vertices.
(Square table which is symmetrical)

Question 29

Distance Matrix (C2)

Answer 29

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

Question 30

Minimum Spanning Tree (C3)

Answer 30

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

Question 31

Kruskal’s Algorithm (C3)

Answer 31

Used to find MST
- Sort edges into ascending order of weight
- Select arc of least weight to start the tree
- Select next arc of least weight which DOESN’T form a cycle.
- Repeat until all vertices are connected

Question 32

Prim’s Algorithm (C3)

Answer 32

Used to find MST
- Choose any vertex to start
- Select an adjoining arc of least weight that connects to a vertex not yet in the tree
- Repeat until all vertices are connected

Question 33

Prim’s => Distance Matrix (C3)

Answer 33

• Choose any vertex to start
• Delete the row of the vertex
• Circle the lowest undeleted entry in the column
• Move to the corresponding column of the circled no.
• Repeat the process for each circled number

Question 34

Dijkstra’s Algorithm

Answer 34

Used to find shortest path between two vertices in a network.

Uses…
Vertex | Label Ord | Final Label
Working Values

Question 35

FLOYD’s?