D1: Algorithms you must know

State the bubble sort algorithm

State the bubble sort algorithm

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.

State the quick sort algorithm

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.

What are the bubble and quick sort algorithms used for?

To order arrays of data

What is the planarity algorithm used for?

To determine whether a graph is planar

State Kruskal's algorithm when applied to a graph

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

State Prim's algorithm when applied to a graph

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

What is Kruskal's and Prim's algorithms used for?

To find a minimum spanning tree

What are four differences between Kruskal's and Prim's algorithms?

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

State Dijkstra's algorithm

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

State Floyd’s algorithm

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.

How to fill out an initial distance table

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

How to fill out an initial route table

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

	A	B	C	D
A	A	B	C	D
B	A	B	C	D
C	A	B	C	D
D	A	B	C	D

What is Dijkstra's and Floyd’s algorithms used for?

To find the shortest path between two vertices in a network

What’s the difference between Dijkstra’s and Floyd’s?

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.

Another phrase for temporary label?

working value

State the route inspection algorithm

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

What is the route inspection algorithm used for?

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

What is another name for the route inspection algorithm?

The Chinese salesman algorithm

If the graph is Eulerian…

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

If the graph is semi-Eulerian…

…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.