Algorithms

Question 1

How many comparisons are required in the first pass of a bubble sort with (n) items

Answer 1

(n - 1) passes.

Question 2

Name the three types of bin packing

Answer 2

First fit
First fit decreasing
Full bin

Question 3

State the order of the bubble sort

Answer 3

Quadratic

Question 4

If an sort has quadratic order, and takes 5 seconds to complete when it has 20 items, how long will it take when it has 30 items?

Answer 4

11.25 seconds

Question 5

If the size of a problem is increased by some factor “k”, then an algorithm of linear order will take approximately…

Answer 5

“k” times as long to complete

Question 6

If the size of a problem is increased by some factor “k”, then an algorithm of quadratic order will take approximately…

Answer 6

“k^2” times as long to complete

Question 7

If the size of a problem is increased by some factor “k”, then an algorithm of cubic order will take approximate…

Answer 7

“k^3” times as long to complete

Question 8

When two numbers compared in a bubble sort are equal, should you swap them or leave them?

Answer 8

Leave them

Question 9

What is the rule for choosing the pivot value in the quick sort?

Answer 9

((n + 1) / 2) th value (rounding up)

Question 10

Where should you put values equal to the pivot in the quick sort?

Answer 10

Values equal to the pivot can go to either side of the pivot - it is probably best to just leave them on their original side

Question 11

What is a “walk” in graph theory?

Answer 11

A walk is a route through a graph along edges from one vertex to the next

Question 12

What is a “path” in graph theory?

Answer 12

A path is a walk in which no vertex is visited more than once

Question 13

What is a “trail” in graph theory?

Answer 13

A trail is a walk in which no edge is visited more than once

Question 14

What is a “cycle” in graph theory?

Answer 14

A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 15

What is a “Hamiltonian cycle” in graph theory?

Answer 15

A Hamiltonian cycle is a cycle that includes every vertex

Question 16

What is the valency, degree or order of a node

Answer 16

The valency, degree or order of a node is the number of arcs incident to it

Question 17

What additional terms describing order might you see associated with the valency of nodes in digraphs?

Answer 17

In-degree (the number of arcs coming into the node) or out-degree (the number of arcs leaving the node)

Question 18

Describe Dijkstra’s algorithm briefly

Answer 18

Begin by giving the start node order label 1, to denote that it was the first node labelled
In the next box, give it final distance label 0
a) Label adjacent nodes with the sum of the final distance label of the node just labelled and the weight of the edge that joins them - this is a temporary distance label
Choose the node with the lowest temporary distance label, make that distance label its final distance label, and give it an order label
Return to step a) until all nodes are labelled

Question 19

Describe the planarity algorithm, and to what it can be applied

Answer 19

The planarity algorithm determines whether a graph is planar - it can only applied to graphs containing a Hamiltonian cycle

Method:
Identify a Hamiltonian cycle and draw a polygon with the edges and vertices that constituted the cycle

Draw all the remaining edges from the original graph inside the polygon

Make a list of all edges inside the polygon

a) Choose any unlabelled edge in the list and label it “I” - if all edges are labelled, the graph is planar

b) Look at any unlabelled edges that cross the edge just labelled:
If there are none, go to a)
If any of these edges cross each other, the graph is non-planar
If none of these edges cross each other, give them the alternate label to the edge just labelled (“O”, if not “I”)
Return to b)

Question 20

Describe the formation of the objective function in the Big M method, where the aim is to minimise P = x - y + z, and there are two artificial variables

Answer 20

Minimise P by maximising Q = - P - M(a1 + a2)
So Q = -x + y - z - Ma1 - Ma2
Then substitute out a1 and a2 by rearranging the constraint equations to get the objective function in terms of x, y, z and M

Question 21

Describe the formation of the objective function for the two stage simplex method

Answer 21

For the first stage of the method, minimise the sum of the artificial variables
The objective function will be I = - (a1 + a2 + a3 + …)
The substitute out the artificial variables by rearranging the constraint equations to get the objective function in terms of x, y and z
For the second stage, once the artificial variables are eliminated, complete the algorithm in the usual manner

Question 22

What is the formula for finding the lower bound for the number of workers required to complete a project within its critical time

Answer 22

[Sum of all activity times] / [Critical time of the project]