decision 1

Question 1

what are the steps of a bubble sort pass ?

Answer 1

• compare 1st and 2nd numbers and swap if 2nd is smaller
• compare second and 3rd ,swap if 3rd is smaller
• continue through the whole list and corner of the last value

Question 2

steps of bubble sort

Answer 2

• if there is one number stop
• complete a pass comparing and swapping necessary
• if NO swaps have occurred stop
• otherwise ignore last element and follow though another pass

Question 3

disadvantages of bubble sort

Answer 3

a lot more comparisons, a whole pass must occur without a swap to stop the process therefore there a plenty of excess and unnecessary swaps

Question 4

how to find out the number of comparisons in bubble sort

Answer 4

(n-1)+(n-2)+(n-3)+….+3+2

or

n(n-1)/2

Question 5

steps of shuttle sort

Answer 5

• corner off first 2 , then compare 1st and 2nd and swap if necessary
  -then compare 2nd and 3rd swap if necessary. if swap occurs then compare 1st and 2nd.
• compare 3rd and 4th and swap if necessary, if swap occurs continue.
  if swap doesn’t occur move one to next pass

Question 6

advantages of shuttle sort

Answer 6

same amount of swaps but less comparisons than bubble sort

Question 7

what is the efficiency of an algorithm

Answer 7

the order is determined by the algorithm, commonly a quadratic function.

Question 8

what is the first fit algorithm

Answer 8

place each object in turn in the first available space in which it will fit, commonly lings in bins or cut off from logs

Question 9

what is a node ?

Answer 9

is a vertices which connects two arcs

Question 10

what is a complete graph ?

Answer 10

a graph where each node is connected by precisely one arc to very other node

Question 11

what is a bipartite graph ?

Answer 11

these graphs have two sets of nodes of which arcs only connect nodes from one set to the other and none connect them in the set.

Question 12

what is an eulerian graph ?

Answer 12

is a connected graph which has a closed trail containing every arc exactly once. ie can be formed with one line without lifting a pen
eulerian graphs must have nodes of all even order

Question 13

what is a semi eulerian graph

Answer 13

a not closedgraph which contains every arcs exactly once

has exactly 2 odd nodes

Question 14

Steps of primms algorithm

Answer 14

• choose node
• choose shortest arc off said node
• choose next hottest arc ( don’t create a loop)

Question 15

Number of arcs used in primms algorithm

Answer 15

N - 1

Question 16

What does primms algorithm create

Answer 16

Creates a minimum spanning tree

Question 17

Steps of kruskal algorithm

Answer 17

• choose shortest arc
• choose next shortest arc
  ( don’t create a cycle)

Question 18

Steps of dijkstra

Answer 18

• label first node 1 weight 0
• add temporary label of possible weight
• choose smallest temporary label and label node 2 with said weight
• readjust temporary labels
• repeat the step

Question 19

Other name for a route inspection algorithm

Answer 19

Chinese postman

Question 20

Steps of Chinese postman

Answer 20

• find odd nodes
• pair odd nodes
• choose shortest pairs without causing a loop
• add the two arcs to the network
• fin the weight of the minimum spanning tree

Question 21

Steps is lower bound algorithm

Answer 21

• choose node
• consider the arcs and choose the 2 shortest arcs , calculate their weight
• remove said node and find the minimum spanning tree ( kruskal )
• sum the weight of the minimum spanning tree add the two removed arcs

Question 22

What is a planar graph ?

Answer 22

Graph with no crossing lines connecting nodes

Question 23

What is a tree ?

Answer 23

A non connected graph with no cycles

Question 24

Regions + nodes =

Answer 24

Arcs + 2

Question 25

Arcs + 2 =

Answer 25

Regions + nodes

Question 26

What is a tour improvement

Answer 26

An algorithm to make the shortest route going it e same nodes

Question 27

Steps of tour improvement algorithm

Answer 27

• let I = 1
• if d(vi, vi+2) + d(vi+1, vi+3 ) < d(vi+ vi+1) + d(vi+2, vi+3) then swap vi+1 and vi+2
• replace I with I+1
• if I < n repeat then steps

Question 28

What is a Hamiltonian cycle

Answer 28

A tour which contains every node precisely once

Question 29

Why does the traveling sales person find ?

Answer 29

A Hamiltonian cycle of minimum weight

Question 30

What is eulers relationship ?

Answer 30

R + n = a+ 2

Question 31

What is a drawback of dijkstra ?

Answer 31

It cannot be used if any of the weights are negative. For example they might gain a profit going down that route