Algorithms

Question 1

Quick sort algorithm

Answer 1

1. Select the pivot element (first) from the list
2. write down all of the numbers that are smaller than the pivot in a sub-list to the left of the pivot, keeping the numbers in their original order
3. write all the numbers larger than the pivot in a sub-list to the right of the pivot, keeping numbers in their original order
4. apply steps 1-3 to each separate sub-list until each one contains only one number
   (circle/underline a number when it is in its fixed position, after it is a pivot element)

Question 2

Kruskal’s algorithm

Answer 2

1. select the shortest edge in a network
2. select the next shortest edge which does not create a cycle
3. repeat step 2 until all vertices have been connected

Question 3

Prim’s algorithm (graph)

Answer 3

1. select any vertex
2. select the shortest edge connected to that vertex
3. select the shortest edge connected to any vertex already connected
4. repeat step 3 until all vertices have been connected

Question 4

Prim’s algorithm (table)

Answer 4

1. delete the row corresponding to the starting node. label ‘1’ to the column corresponding to this node.
2. look down the labelled column(s) and find the smallest value in that column that is not already crossed out. choose this entry by circling it.
3. delete the row that contains the entry that was just circled. label the column corresponding to the node that was just crossed out.
4. If any row is not crossed out go back to step 2, otherwise stop.

Question 5

Dijkstra’s algorithm

Answer 5

1. label the start vertex with permanent label 0 and order label 1
2. assign temporary labels to all the vertices that can be reached directly from the start
3. select the vertex with the smallest temporary label and make its label permanent. add the correct order label.
4. put temporary labels on each vertex that can be reached directly from the vertex you have just made permanent. the temporary label must be equal to the sum of the permanent label and the direct distance from it. if there is an existing temporary label at a vertex, it should be replaced only if the new sum is smaller
5. select the vertex with the smallest temporary label and make its label permanent. add the correct order label.
6. repeat until the finishing vertex has a permanent label
7. to find the shortest path(s), trace back from the end vertex to the start vertex. write the route forwards and state the length.

Question 6

First-fit algorithm

Answer 6

Take the boxes in the order listed and pack each box in the first bin that has enough space (starting each time with the first bin).

Question 7

First-fit decreasing algorithm

Answer 7

Reorder the boxes from largest to smallest, then apply the first-fit method to this list.

Question 8

Full-bin strategy

Answer 8

Look for combinations of boxes that will fill bins. pack these boxes. put the rest together in combinations that result in bins that are as nearly full as possible. (not an algorithm since there is no set way to make the full bins).

Question 9

What does heuristic mean?

Answer 9

A method that finds a solution efficiently, but with no guarantee that the solution is optimal.