# Rest of Decision Flashcards

What is an algorithm?

A finite sequence of step-by-step instructions carried out to solve a problem

What does an oval shaped box mean in a flow chart?

The start/end

What does a rectangular box mean in a flowchart?

It’s an instruction

What does a diamond shaped box mean in a flowchart?

A decision

Describe how to carry out a bubble sort

You compare adjacent items in a list:

If they are in order, leave them

If they are not in order, swap them

The list is in order when a pass is completed without any swaps

Describe how to carry out a quick sort

You select a pivot then split the items into two sub-lists:

One sub list contains items less than the pivot

The other sub list contains items greater than the pivot

You then select further pivots from within each sub list and repeat the process

What are the three bin packing algorithms?

First fit

First fit decreasing

Full bin

Describe how to carry out first fit bin packing

Take the items in the order given

Place each item in the first available bin that can take it. Start from bin one each time

What is the advantage/disadvantage of first fit bin packing?

Ad: It is quick to implement

Dis: It is not likely to lead to a good solution

Describe how to carry our first fit decreasing bin packing

Sort the items so that they are in descending order

Apply the first fit algorithm to the re-ordered list

What are the advantages/disadvantages of first fit decreasing bin packing?

Ad: You usually get a fairly good solution. It is easy to implement

Dis: You may not get an optimal solution

Describe how to carry out full bin packing

Use observation to find combinations of items that will fill a bin. Pack these items first.

Any remaining items are packed using the first fit algorithm

What are the advantages/disadvantages of full bin packing?

Ad: You usually get a good solution

Dis: It is difficult to do, especially when the numbers are plentiful and awkward

What is the order of an algorithm?

Tells you how changes in the size of a problem affect the approximate time taken for its completion

What order is bubble sort?

Quadratic: 0.5(n-1)n

In any undirected graph, the sum of the degrees of the vertices equals…?

2 x the no. of edges

What is Euler’s handshaking lemma?

The number of orders vertices must be even, including possibly zero

What is a planar graph?

One that can be drawn in a plane such that no two edges meet except at a vertex

What is a minimum spanning tree?

A spanning tree such that the total length of it arcs is as small as possible

Which algorithms find the minimum spanning tree?

Kruskal’s (list all edges) and Prim’s (either pick one node on the graph, and find MST. Or use distance matrix)

What is the main difference between Kruskal’s and Prim’s?

Kruskal’s looks at edges

Prim’s looks at nodes

What can Dijkstra’s algorithm be used for?

Find the shortest path from the start vertex, to any other vertex in the graph

Floyd’s algorithm: explain how you know that the graph contains directed edges, (given the distance table and route table)

The distance table is not symmetrical about the leading diagonal

What is the difference in output between Floyd’s algorithm and Dijkatra’s?

The output of Floyd’s gives the shortest distance between every pair of nodes

The output of Dijkstra’s gives the shortest distance from the start mode to every other node

Floyd’s algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration

(n-1)(n-2) = n^2 - 3n + 2

What is the order of Floyd’s algorithm?

Cubic

What is an Eulerian graph?

One which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called an Eulerian circuit. Any connected graph who is vertices are all even is Eulerian

What is a semi-Eulerian graph?

One which contains a trail that includes every edge that starts and finishes at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian

If all the vertices in a network have even degree, then the length of the shortest route will be…?

The total weight of the network

If a network has exactly 2 odd vertices, then the length of the shortest route will be…?

The total weight of the network, plus the length of the shortest path between the two odd vertices

What is the route inspection algorithm ?

Identify any vertices with odd degree

Consider all possible complete pairings of these vertices

Select the complete pairing that has the least sum

Add a repeat of the arcs indicated by this pairing to the network

Describe the classical and practical travelling salesman problem

In the classical problem, each vertex must be visited exactly once before returning to the start

In the practical problem, each vertex must be visited at least once before returning to the start

What do you need to convert the network into, in order for the classical and practical travelling salesman problems to be the same?

A complete network of least distances

The table representing this = table of least distances

Travelling salesman problem: How can you find an upper bound?

Use a minimum spanning tree

Or nearest neighbour algorithm

Travelling salesman problem: How can you use a minimum spanning tree to find an upper bound?

Find the minimum spanning tree, this guarantees that each vertex is included

Double the minimum connector so that completing the cycle is guaranteed

Seek ‘shortcuts’

Travelling salesman problem: Why do you want to make the upper bound as low as possible?

To reduce the interval in which the optimal solution is contained

Travelling salesman problem: What can you use to find a lower bound?

Minimum spanning tree

Travelling salesman problem: How can you find the lower bound using a minimum spanning tree?

Remove each vertex in turn, together with its arcs

Find the residual minimum spanning tree and its length

Add to the RMST the ‘cost’ of reconnecting the deleted vertex by the two shortest, district, arcs and note the total

The greatest of these totals is used for the lower bound

Travelling salesman problem: why do you want to make the lower bound as high has possible ?

To reduce the interval in which the optimal solution is contained

Travelling salesman problem: How do you know if you have found the optimal solution when using a minimum spanning tree to find a lower bound?

If the lower bound gives a Hamiltonian cycle, or if the lower bound has the same value as the upper bound

Travelling salesman problem: using a minimum spanning tree to find the lower bound: Why does this generally not give you a solution to the original problem?

It would be necessary to repeat arcs to create a tour