Give the steps of a bubble sort
(Decision)
Compare first two values
Swap if in wrong order
Repeat for all values, moving from left to right
Repeat until no swaps in pass, ignoring the furthest item right each time
Give the steps of a quick sort
Select the middle number of the list to be the pivot
Place the numbers to the left or right of the pivot based on where they are in the sorted list
Repeat until every number has been selected as a pivot
Define the first fit bin packing algorithm
Beginning with the first item, place each element into the first bin it fits in
Define the first fit decreasing bin packing algorithm
Order the objects in descending order of size
Starting with the largest, apply the first fit algorithm
Define the full bin packing algorithm
Choose elements which will entirely fill a bin and place them together
Place other elements using the first fit algorithm
Give pros and cons of the first fit algorithm
Fast
No need to sort objects
Rarely provides optimal solution
State how to calculate the lower bound for bin packing algorithms
Total size of all objects / bin capacity
Take ceiling
Give pros and cons of the first fit decreasing algorithm
Usually close to optimal solution
Requires list to be sorted
Takes longer than first fit
Give pros and cons of the full bin algorithm
Usually provides close to optimal solution
No guarantee better than first fit decreasing
Difficult to program computer to do
Give an example of an algorithm with linear order
Finding an item in unsorted list
Give an example of an algorithm with quadratic order
Bubble sort
Quick sort
Shortest path
Give an example of an algorithm with cubic order
Minimum connector
Dijkstra’s algorithm
Describe a distance matrix
Distance from element on side to element on top in table e.g.
A B C
A - 10 -
B 10 - 1
C - 1 -
Link of distance 10 from A to B
Link of distance 1 from B to C
Describe an adjacency matrix
Shows number of paths between points e.g.
A B C
A - 2 -
B 2 - 1
C - 1 -
2 paths directly from A to B
1 path directly from B to C
Define the degree of a vertex
Number of arcs that meet at that node
Note: a path from a node to itself counts as 2
Define a subgraph
A graph from the original with vertices and edges which are subsets of the original
Define a walk
Route on a graph from one vertex to the next
Define a path
A finite sequence of edges where no vertex is visited more than once such that the end of one edge is the start of the next
Define a trail
A walk where no edge is visited more than once
Define a cycle
A walk with the same start and end vertex and where no other vertex is visited more than once
Define a Hamiltonian Cycle
A cycle which includes every vertex
Define a connected graph
A graph with all of its vertices connected
Define a loop on a graph
An edge that starts and finishes at the same vertex
Define a tree
A connected graph with no cycles
