D1: Algorithms you must know

1. List the array of items in the working list

2. Compare adjacent items: only swap them if they are not in order

3. Repeat step 2 until all adjacent items have been compared. This is the first pass; the last item of the list should now be in order => no longer in working list

4. Repeat step 3 until you can complete a pass with no swaps. In this case, the list is now ordered.

1. List the array of items in the working list

2. Select an item to be a pivot

3. Create two sublists of items in the order appear in the working list. One last should be of items lower in value to the now fixed pivot and the other should be of items greater in value. They should be separated by the fixed pivot depending on whether the final list is in ascending or descending order.

4. Select two new pivots in each other the sublists and repeat step 3.

5. Repeat step 4 until all items are fixed. The list is now ordered.

To order arrays of data

To determine whether a graph is planar

1. Sort all edges in ascending order of weight (in alphabetical order too)

2. Select the edge of least weight to sort the spanning tree

3. Consider the next arc of least length: only add it to the graph if it will not form a cycle

4. Repeat step 3 until all vertices are connected

1. Choose any vertex to start the tree

2. Select an arc of least weight that joins a vertex in the tree to a vertex not yet in the tree. If there are multiple arcs of equal weight, choose any of them.

3. Repeat step 2 until all vertices are connected

To find a minimum spanning tree

1. Kruskal's considers arcs whereas Prim's considers vertices

2. When Kruskal's algorithm is applied, the MST can grow chaotically whereas with Prim's the MST always grows in a connected fashion

3. Prim’s can be applied to a matrix whereas Kruskal’s can’t

4. You have to check for cycles with Kruskal’s whereas you don’t have to with Prim’s

1. Select a starting vertex 'S'. Give it order label 1 and permanent label 0.

2. Consider the vertices directly connected to the starting vertex. Record temporary labels for them (value of temporary labels = S permanent label + weight of arc connecting S and vertex in question).

3. Select the vertex with the least working value. The working value is now fixed => permanent label, and the vertex should be given the appropriate order label. This vertex will no longer be considered

4. Repeat step 2 and 3 and work through all vertices of the network until the destination vertex is reached. If a vertex with a temporary label is revisited, only replace the label if the new value is smaller.

5. To find the shortest path, trace back from the end vertex to the start. Reverse this to state the correct route + state its weight

1. State the initial distance and route tables of the corresponding graph

2. Repeat n iterations of the steps below (with n being the number of vertices in the graph)

   1. copy the n^th row and n^th column (and all the dashes) of the distance table into a copy distance table. Highlight these entries.

   2. consider each empty entry:

      1. if the row-column sum ≥ preceding entry, keep preceding entry

      2. if the row-column sum < preceding entry, replace preceding entry with value of row-column sum and edit route table to the corresponding entry is the n^th vertex

   3. repeat until all empty entries have been considered, then move onto next iteration

3. Once final iteration has been completed, the resultant distance and route tables will detail the shortest route between any two vertices and its weight.

Entries should be the weight on each arc of the graph

• row-to-column is the corresponding direction on the graph (relevant if the graph is directed)

• if there is no direct arc between two vertices, denote the entry with an infinity symbol

The entries of each column should be the corresponding label of each column e.g.

To find the shortest path between two vertices in a network

Floyd’s finds the shortest route between every pair of vertices whereas Dijkstra’s only finds the shortest route between one selected vertex and the rest of the vertices in the graph.

working value

1. Record all vertices with odd degrees

2. List all possible pairings of these vertices

3. Select the arcs of the pairings with the least weight

4. Add a repeat of the arcs indicated by this pairing to the network

Used to find the shortest route in a network that traverse every arc once and returns to its starting point

The Chinese salesman algorithm

…the shortest route will be equal to the weight of the network

…the shortest route will be the sum of the weight of the network and the length of the shortest path between the two odd vertices.