Decision

Question 1

Algorithm

Answer 1

A finite sequence of step-by-step instructions carried out to solve a problem

Question 2

Bubble Sort

Answer 2

Compare Adjacent items in the list:
· If in order, then leave them
· If out of order, then swap terms.
Compare all pairs in the list
Sort is complete when a full pass with no swaps is complete.

Question 3

Quick Sort

Answer 3

Select midpoint as pivot, write all terms smaller than pivot on the left and all the terms bigger than the pivot on the right hand side.
Repeat this for the sublists produced.
Sort complete when all terms have been a pivot.

Question 4

What are the 3 bin packing algorithms?

Answer 4

First-fit - considering items in the order they are given in.
First-Fit decreasing - order items in decreasing order and apply first fit algorithm.
Full-Bin - by inspection select items that will combine to fill bins, then apply first fit to remaining terms.

Question 5

Order of an algorithm

Answer 5

A measure of the run time of the algorithm.
Increasing the size from m to n, increases the algorithm by a factor of f(m)/f(n)

Question 6

Increasing the size of a problem by k

Answer 6

· An algorithm of linear order will take k times longer.
· An algorithm of quadratic order will take k² times longer.
· An algorithm of cubic order will take k³ times longer.

Question 7

A graph

Answer 7

A graph consists of nodes which are connected by edges.

Question 8

A Weighted Graph

Answer 8

Edges have a number associated with them, denoted there size.

Question 9

A subgraph

Answer 9

A subgraph is a section of an original graph, showing only select nodes and edges.

Question 10

Degree, Valency, or Order of a node

Answer 10

The number of edges going into a node.

Question 11

Odd and Even Nodes

Answer 11

Denoted is the order of a node is odd or even.

Question 12

Walk
Path
Trail
Cycle

Answer 12

A walk is a route through a graph from one node to the next.
A path is a walk in which no node is visited more than once.
A trail is a walk in which no edge is visited more than once.
A cycle is a walk where the start and end node are the same and no other node is visited more than once.

Question 13

Hamiltonian Cycle

Answer 13

A cycle that includes every vertex.

Question 14

Connected Graph

Answer 14

A graph where every vertex is connected. There is a path to any vertex from any vertex.

Question 15

A Loop

Answer 15

An edge which starts and finished at the same vertex.

Question 16

Simple graph

Answer 16

No Loops and there is a single edge from every vertex to every vertex.

Question 17

Directed Graph

Answer 17

Edges have a direction and can only be commuted in that direction.

Question 18

Euler’s Handshaking Lemma

Answer 18

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges. Number of odd nodes must be even.

Question 19

A tree

Answer 19

A connected graph with no cycles

Question 20

A Spanning Tree

Answer 20

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

Question 21

A Complete Graph

Answer 21

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

Question 22

An Isomorphic Graph

Answer 22

Graphs which show the same information but may be drawn differently

Question 23

Adjacency Matrix

Answer 23

A matrix describing the number of arcs joining the corresponding vertices.

Question 24

Distance Matrix

Answer 24

A matrix describing the weight of arcs connecting vertices.

Question 25

Minimum Spanning Tree

Answer 25

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

Question 26

Kruskal’s Algorithm

Answer 26

1) sort edges into ascending order of weight
2) select the edge of least weight
3) select from edges not previously selected, the edge of least weight that does not form a cycle
4) repeat step 3 until selected edges form a spanning tree

Question 27

Prim’s Algorithm

Answer 27

1) choose starting vertex
2) choose vertex nearest to starting vertex, add that vertex and add its associated edge to the tree
3) connect to the tree of connected vertices that vertex that is nearest to any vertex in the connected set, but to a vertex not already in the tree
4) repeat step 3 till all vertices are connected to the tree

Question 28

Prim’s Algorithm with a distance matrix

Answer 28

1) start with the matrix representing the network and choose a starting vertex. Delete the row corresponding to to that vertex
2) label with ‘1’ the column corresponding to the start vertex, ring the smallest undeleted entry in that column
3) delete the row corresponding to the entry you just ringed
4) label with the next number the column corresponding to the vertex you just ringed
5) ring the lowest undeleted entry in all labelled columns
6) repeat steps 3, 4 and 5 till all rows are deleted. The ringed entries represent the edges in the minimum connector

Question 29

Dijkstra’s Algorithm

Answer 29

1) give start vertex label 0
2) give each vertex connected to start vertex a working value
3) find smallest working value and give it its permanent label
4) update working values at any unlabelled vertex that can be reached from V
5) repeat steps 3 and 4 till destination vertex given permanent label

Question 30

Eulerian Graph

Answer 30

Contains a trail that includes every edge but starts and finishes at the same vertex. Graph must be connected and have all even vertices.

Question 31

Semi-Eulerian Graph

Answer 31

Contains a trail that includes every edge but starts and finishes at different vertices. Graph must be connected and have exactly 2 odd vertices.

Question 32

Route Inspection Algorithm

Answer 32

1) list all odd vertices
2) form all possible pairings of odd vertices
3) for each pairing find the edges that are best to repeat and find the sum of the lengths of these edges
4) choose the pairing with the smallest sum, construct a route that repeats these edges

Question 33

Vertex Method to find the Optimal Point

Answer 33

Find the Feasible Region
Find the co-ordinates of the vertices of the feasible region
Trial each vertex to see which gives the optimal solution

Question 34

Precedence Table

Answer 34

A table that shows which activities must be completed before others are started.

Question 35

Dummy Activity

Answer 35

No time or cost. Shows the dependancy between activities.

Question 36

Early Event Time

Answer 36

The earliest time an activity can start allowing all preceding activities to occur, These can be found on the forward pass.

Question 37

Late Event Time

Answer 37

The latest time that an event can be left without exceeding the time needed for the project. These can be found on the backwards pass.

Question 38

Critical Activity and Path

Answer 38

Critical activities are any activities with equal Early and Late Event Times. Critical activities form the critical path.

Question 39

Float

Answer 39

Total Float = Latest finish time - Duration - Earliest start time

Question 40

Gantt Charts

Answer 40

A visual showing the critical path, and the earliest start and latest finish time of each activity.