# List Of Algorithms Flashcards

1
Q

Bubble sort

A
2
Q

Quick sort

A
3
Q

First fit

A
4
Q

First fit decreasing

A
5
Q

Full bin

A
6
Q

Kruskal’s

A
7
Q

Prims normal

A
8
Q

Prims (Distance Matrix)

A
9
Q

Dijikstra’s

A

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

10
Q

Route Inspection Algorithm

A
11
Q

PSP UB

A
12
Q

SP LB

A
13
Q

Nearest Neighbour

A
14
Q

Planetary algorithm

A
15
Q

What does the route inspection algorithm do?

A

Find the minimum tour (general idea)

16
Q

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

A

Find a tour (generally)

17
Q

What is a tour?

A

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

18
Q

What does the planetary algorithm attempt to do?

A

Determine if a graph is planar or not

19
Q

What does the nearest neighbour algorithm do?

A

Finds a upper bound to the Salesman’s problem

20
Q

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

A

The other 2 involve greater than or equal to constraints

21
Q

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

A

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

22
Q

What are the 3 steps to floyd’s algorithm?

A

Set up
Iteration
Interpretation

23
Q

Explain the set up phase of floyd’s algorithm?

A

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

24
Q

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

A

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

25
Q

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

A

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