# Decision - Algorithms Flashcards

What 2 algorithms are used to find minimum spanning trees?

- Kruskal’s Algorithm
- Prim’s Algorithm

How do you perform Kruskal’s algorithm?

- List the edges in order of weight, smallest first
- Choose the edge with the smallest weight
- From the remaining edges, choose the edge with the smallest weight, as long as it does not form a cycle with edges already chosen
- Repeat step 3 until all vertices have been included

How do you perform Prim’s algorithm on a graph?

- Choose a start vertex
- Connect the start vertex to the nearest new vertex by adding the shortest edge
- From any vertex on the tree so far, add the shortest edge which connects to a new vertex
- Repeat step 3 until all vertices have been included

What are advantages/disadvantages of Kruskals algorithm?

- Very Intuitive
- However takes work to sort edges before you start
- Can be difficult to check for cycles in large networks

What are advantages/disadvantages of Prim’s algorithm?

- Quite Intuitive
- Easy to use on large networks

How do you perform Prim’s algorithm on a matrix?

- Choose the start vertex and label the corresponmding column to that vertex with a 1
- Delete the row of the vertex you just labelled
- Look in all the columns that have been numbered so far. Circle the smallest undeleted entry and read off the vertex for the row
- Label the column corresponding to this vertex with the next available label then delete the row
- Repeat steps 3 and 4 until all the rows have been deleted

(write out edges as they are selected and draw the graph)

What does Dijkstra’s algorithm do?

It finds the shortest distance between 2 vertices in a network

What is the method to find the shortest distance between 2 points using Dijkstra’s algorithm?

- Give the start vertex (S) a permanent label of 0
- give each vertex connected to S a working value by recording its distance from S
- Find the smallest working value and give the corresponding vertex V this value as a permanent label
- Update any working values at any unlabelled vertices that can be reached from V and update any working values if they would be reduced by travelling from V
- Repeat steps 3 and 4 until the destination vertex has been given a permanent label

What are the compartments in the box when performing Dijkstra’s algorithm used for?

Top left: Order of Labelling

Top Right: Permanent Label

Bottom: Working Values

When do you stop in Dijkstra’s algorithm?

When the destination vertex has been given a permanent label

What is the method for performing Dijkstra’s algorithm to backtrack and find the shortest route?

- Start from the destination vertex
- From the current vertex V, look at all the vertices that lead directly to V
- Of these vertices, vertex P is the previous vertex on the route if Label V - Weight PV = Label P
- Repeat steps 2 and 3 using the vertex just found as the current vertex
- Stop when you have backtracked all the way back to the start vertex
- Record each vertex as you select them then flip the order in which they are recorded (as you started from the destination vertex)

What is the method for bubble sort?

- Start at the beggining of the working list and move from left to right comparing adjacent items, if they are in the correct order, leave them, if not swap them
- When you get to the end of the working list, the last item is in the final position . This is item is no longer in the working list
- If you have made any swaps in the prevuoius pass repeat step 1
- When a pass is completed without any swaps, the list is in ordered

Circle comparisons, Label end of each pass, “No swaps made in last pass so the list is in order”

What is the method for first fit bin pack algorithm?

- Take the items in the order given
- Place each item in the first available bin, start from bin 1 each time

What is the method for first fit decreasing bin pack algorithm?

- Sort the items so that they are in descending order
- Apply the first fit algorithm to the reordered list

What is the method for full bin pack algorithm?

- Use observation to find combinations of items that will fill a bin
- any remaining items are packed using the first fit algorithm