Decision 1 uncomplete

A finite sequence of instructions for solving a problem

Requires:

A given input, so an algorithm produces a unique output

A sequence must end, so it requires a stopping condition

Shuttle sort is more efficient than Bubble, because they have the same number of swaps, but Bubble has more comparisons.

Compare each number to the number above it. Fro ascending order : If the number below is smaller than the one above, then swap positions of the 2 numbers compared, then repeat with each row.

in 1st pass largest number always goes to bottom and is ignored. 2nd pass the next largest will stay at the bottom and so forth

Comparisons: 1st comparison is 1 less than the amount of numbers to order and decrease by 1 by each pass

Swaps: the stopping condition is 0 swaps

• In original list compare position1 and position.2.
• (for ascending order) if position.2 is smaller then swap positions for 1st pass.
• In 2nd pass compare position2 and position3 if pos.3 is smaller swap positions, then compare new number in position2 and position1 and swap if necessary
• in 3rd pass compare position 3 and 4 and repeat process

there should be 1 less pass than amount of numbers in list to order

there will be no checking pass

• is a Node/Vertices... -------- is an arc, a number on an arc is the weight

Tree - All nodes are connected, but has no cycles

A Simple graph - there are no multiple arcs, no nodes are connected to themselves

Complete graph - All nodes are connected by precisely 1 arc to every other node

Planar - Arcs never cross, therefore they only meet eafch other at nodes.

Bipartite - 2 sets of nodes, and arcs only connect from 1 set to the other

Every arc has 2 ends so when N is a node the amount of arcs is 1/2 N(N-1)

Eularian - has an even order Eulars relationship - regions + nodes = arcs + 2

Semi Eularian - has exactly to odd orders ( odd number of arcs from a node)

Spanning tree - all nodes connected without cycles

Minimum spanning tree - the above with littlest sum of weight

A number on an arc is a weight

Prims

• Pick any start node
• pick the lightest arc which is attached
• Pick the nect lightest arc which is attached to either nodes without making a cycle
• Obviously Reject any arc that makes a cycle
• Continue until all nodes are attached
• Add up total

• Pick lightest arc
• Pick the next lightest arc which is attached
• Reject any arcs that make a cycle
• Continue till all nodes are connected
• add up total

• Pick Start node mark collumn and cross out row
• Pick smallest arc (number in grid that is within the collum)
• Arrow new collumn and cross out row
• Find smallest arc from either node and repeat process
• Continue until all comllums are highlighted
• Add total weight