decision 1 Flashcards
what are the steps of a bubble sort pass ?
- 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
steps of bubble sort
- 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
disadvantages of bubble sort
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
how to find out the number of comparisons in bubble sort
(n-1)+(n-2)+(n-3)+….+3+2
or
n(n-1)/2
steps of shuttle sort
- 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
advantages of shuttle sort
same amount of swaps but less comparisons than bubble sort
what is the efficiency of an algorithm
the order is determined by the algorithm, commonly a quadratic function.
what is the first fit algorithm
place each object in turn in the first available space in which it will fit, commonly lings in bins or cut off from logs
what is a node ?
is a vertices which connects two arcs
what is a complete graph ?
a graph where each node is connected by precisely one arc to very other node
what is a bipartite graph ?
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.
what is an eulerian graph ?
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
what is a semi eulerian graph
a not closedgraph which contains every arcs exactly once
has exactly 2 odd nodes
Steps of primms algorithm
- choose node
- choose shortest arc off said node
- choose next hottest arc ( don’t create a loop)
Number of arcs used in primms algorithm
N - 1
What does primms algorithm create
Creates a minimum spanning tree
Steps of kruskal algorithm
- choose shortest arc
- choose next shortest arc
( don’t create a cycle)
Steps of dijkstra
- 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
Other name for a route inspection algorithm
Chinese postman
Steps of Chinese postman
- 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
Steps is lower bound algorithm
- 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
What is a planar graph ?
Graph with no crossing lines connecting nodes
What is a tree ?
A non connected graph with no cycles
Regions + nodes =
Arcs + 2
Arcs + 2 =
Regions + nodes
What is a tour improvement
An algorithm to make the shortest route going it e same nodes
Steps of tour improvement algorithm
- 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
What is a Hamiltonian cycle
A tour which contains every node precisely once
Why does the traveling sales person find ?
A Hamiltonian cycle of minimum weight
What is eulers relationship ?
R + n = a+ 2
What is a drawback of dijkstra ?
It cannot be used if any of the weights are negative. For example they might gain a profit going down that route
