List Of Algorithms

Question 1

Bubble sort

Answer 1

Question 2

Quick sort

Answer 2

Question 3

First fit

Answer 3

Question 4

First fit decreasing

Answer 4

Question 5

Full bin

Answer 5

Question 6

Kruskal’s

Answer 6

Question 7

Prims normal

Answer 7

Question 8

Prims (Distance Matrix)

Answer 8

Question 9

Dijikstra’s

Answer 9

You go from lowest to largest when selecting the order of the vertexes considered
After each new final output is written you do another pass

Question 10

Route Inspection Algorithm

Answer 10

Question 11

PSP UB

Answer 11

Question 12

SP LB

Answer 12

Question 13

Nearest Neighbour

Answer 13

Question 14

Planetary algorithm

Answer 14

Question 15

What does the route inspection algorithm do?

Answer 15

Find the minimum tour (general idea)

Question 16

What is the aim of the algorithms to do with the Salesman Problem

Answer 16

Find a tour (generally)

Question 17

What is a tour?

Answer 17

Tour - A walk which visits every vertex and which returns to its starting vertex

Question 18

What does the planetary algorithm attempt to do?

Answer 18

Determine if a graph is planar or not

Question 19

What does the nearest neighbour algorithm do?

Answer 19

Finds a upper bound to the Salesman’s problem

Question 20

What is the difference between the simplex algorithm and the other 2?

Answer 20

The other 2 involve greater than or equal to constraints

Question 21

What is the difference between the 2 stage simplex method and the Big M method?

Answer 21

The 2 stage simplex creates a new objective function to be minimised, whilst the Big M just manipulates the original objective function

Question 22

What are the 3 steps to floyd’s algorithm?

Answer 22

Set up
Iteration
Interpretation

Question 23

Explain the set up phase of floyd’s algorithm?

Answer 23

Remember everything is down then right.
You set up your distance table. Down the leading diagnal you have dashes
If there is no direct route then you put infinity

For the route table sameyou write ABCD down the page
ABCD
ABCD
ABCD
ABCD

Question 24

How do you do the iteration stage of floyd’s algorithm?

Answer 24

Copy the first row and column and highlight them. Then for each box work out the value (X+Y) and compare it with the original value. If smaller than replace it.
If you replace it change the letter in the route table to the corresponding detour (the letter will the the one which has been highlighted)
Do this for each row and column

Question 25

How do you do the interpretation stage of Floyd’s algorithm?

Answer 25

Remember down then right/
Find what detour is needed to get from A to D (eg C) then find what detour is needed to get from A C and repeat until you get C to C. (This will look like going across the row) Then write it in reverse/sensible order