Decision - Algorithms

Question 1

What 2 algorithms are used to find minimum spanning trees?

Answer 1

• Kruskal’s Algorithm
• Prim’s Algorithm

Question 2

How do you perform Kruskal’s algorithm?

Answer 2

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

Question 3

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

Answer 3

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

Question 4

What are advantages/disadvantages of Kruskals algorithm?

Answer 4

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

Question 5

What are advantages/disadvantages of Prim’s algorithm?

Answer 5

• Quite Intuitive
• Easy to use on large networks

Question 6

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

Answer 6

1. Choose the start vertex and label the corresponmding column to that vertex with a 1
2. Delete the row of the vertex you just labelled
3. Look in all the columns that have been numbered so far. Circle the smallest undeleted entry and read off the vertex for the row
4. Label the column corresponding to this vertex with the next available label then delete the row
5. Repeat steps 3 and 4 until all the rows have been deleted
   (write out edges as they are selected and draw the graph)

Question 7

What does Dijkstra’s algorithm do?

Answer 7

It finds the shortest distance between 2 vertices in a network

Question 8

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

Answer 8

1. Give the start vertex (S) a permanent label of 0
2. give each vertex connected to S a working value by recording its distance from S
3. Find the smallest working value and give the corresponding vertex V this value as a permanent label
4. 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
5. Repeat steps 3 and 4 until the destination vertex has been given a permanent label

Question 9

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

Answer 9

Top left: Order of Labelling
Top Right: Permanent Label
Bottom: Working Values

Question 10

When do you stop in Dijkstra’s algorithm?

Answer 10

When the destination vertex has been given a permanent label

Question 11

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

Answer 11

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

Question 12

What is the method for bubble sort?

Answer 12

1. 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
2. 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
3. If you have made any swaps in the prevuoius pass repeat step 1
4. 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”

Question 13

What is the method for first fit bin pack algorithm?

Answer 13

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

Question 14

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

Answer 14

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

Question 15

What is the method for full bin pack algorithm?

Answer 15

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

Question 16

What is the method for Floyds algorithm?

Answer 16

1. Complete an initial distance table for the network. If there is no direct route from 1 vertex another, label the distance with the infinity symbol
2. Complete an initial route table by making every entry in the first column the same as the label at the top of the first column, making every entry inm the second column the same as the label at the top of the second column etc
3. In the first iteration copy the first row and the first column values of the distance table into a new table and highlight this row and column
4. Consider each unshaded position in turn. Compare the value in this position in the previous table with the sum of the corresponding shaded values. If the sum is less than the original value, copt this new value into the distance table and write [A] in the corresponding position in the route table, if it is more, keep the original value
5. For the second interation, copy the second row and second column from the last iteration and highlight these rows
6. Repeat steps 4-5 until complete
7. Use the route table and distance table to determine route

Question 17

What is the method for quick sort?

Answer 17

1. Choose and circle the item at the midpoint of the list to be the first pivot (if there is an even number of items, choose the pivot to be the item to the right of the middle)
2. On a new row, write down all the items that are less than the pivot, keeping their order, on the left of the pivot. Write down all the items that are more than the pivot, keeping their order on the right of the pivot. Underline the old pivot
3. Repeat steps 1-2 on each side of the old pivot until all of the items have been selected as a pivot
4. If it is required in descending order, ensure you swap items to the opposite side when working. DO NOT SORT IN ASCENDING ORDER AND THEN FLIP AT THE END

State pivots in each iteration and conclude with “sort complete”