Modelling With Algorithms

Question 1

What is an adjacency (incidence) matrix?

Answer 1

A matrix with each row and column representing a vertex, and the elements represent the number of edges (or weight) from one vertex to the other.

Question 2

What is an admissable set?

Answer 2

The admissible set of an inequality is the set of points where the inequality is satisfied.

Question 3

What is an allocation problem?

Answer 3

A matching problem in which each edge is weighted (perhaps representing cost), and the problem is to find a matching which minimises the total weight of the edges used. An allocation problem can be formulated as a linear programming problem.

Question 4

What is the augmented form of a linear programming problem?

Answer 4

When the inequality constraints are written as equalities by introducing slack variables.

Question 5

What is a bipartite graph?

Answer 5

A graph with two sets of nodes. Each edge connects both sets.

Question 6

What is a complete graph?

Answer 6

A graph where every node is connected directly to every other node.

Question 7

What is a connected graph?

Answer 7

A graph in which a path exists between each pair of nodes.

Question 8

What is a critical activity?

Answer 8

An activity with no float. Any delay to the critical activity will delay the project as a whole. A critical activity must lie on a critical path.

Question 9

What is a cycle?

Answer 9

A cycle is a close path (the last node is the first node).

Question 10

How do you do Dijkstra’s algorithm?

Answer 10

Label the starting node S with a permanent label of 0.

For all nodes that can be directly reached from S, assign temporary labels equal to their direct distance from S.

Select the node with the smallest temporary label and make its label permanent.

Put a temporary label on each node that can be reached directly from the node which has just received a permanent label. The temporary label is the sum of the permanent label and the direct distance from it. If there is an existing temporary label at a node, it should be replaced only if the new sum is smaller.

Select the minimum temporary label and make it permanent.

Continue this procedure until the destination node has a permanent label.

To find the shortest path, trace back from the destination, including any arc whose length is equal to the difference between the permanent labels at either end of the arc.

Question 11

What is the first-fit algorithm?

Answer 11

A bin-packing algorithm:

Taking the boxes in the order listed, place the next box to be packed in the first available slot that can take the box.

Question 12

What is the first-fit decreasing algorithm?

Answer 12

A bin-packing algorithm:

Reorder the boxes in order of decreasing size

Apply the first-fit algorithm to this reordered list.

Question 13

What is the float?

Answer 13

The float on an activity is the amount of time by which it may be delayed without affecting the overall time for completion of the project.

Question 14

What is a heuristic algorithm?

Answer 14

A heuristic, or heuristic algorithm, is a method which will usually find a good, if not the best, solution to a problem. An efficient heuristic algorithm will consistently find a good solution to the problem it addresses.

Question 15

What is the independent float?

Answer 15

This is spare time associated with a particular activity. An activity can be delayed by an amount up to its independent float without delaying the start of any other activity, or the overall completion time of the project.

Question 16

What is interfering float?

Answer 16

This is spare time associated two or more activities. If an activity is delayed by an amount up to its interfering float, it may delay the other activities with which it shares interfering float, but it will not delay the overall completion time of the project.

Question 17

What is Kruskal’s algorithm?

Answer 17

An algorithm for finding the minimum spanning tree of a network:

Select the shortest arc of the network.

At each subsequent stage, select from those arcs which have not yet been selected, the shortest arc which does not link nodes between which a path has already been created. If at any stage there is a choice of shortest arcs, choose arbitrarily between them.

Continue until all nodes are connected.

Question 18

What is the order/degree of a node?

Answer 18

The number of edges connecting to it.

Question 19

What is Prim’s algorithm?

Answer 19

An algorithm for finding the minimum spanning tree of a network:

Select an arbitrary node, then connect it to the nearest node.

Now connect the nearest node that is not already connected, to those already in the solution.

Repeat until all nodes have been connected.

Question 20

What is quick sort?

Answer 20

• First split the list into two sub-lists, one containing those numbers less than or equal to the first number in the list (called the pivot), the other containing those greater than it.
• Place the pivot number between the two sub-lists (do not reorder the sub-lists).
• Repeat the process on sub-lists containing two or more numbers until there are no such sub-lists. The list is then sorted.

Question 21

How do you do simplex?

Answer 21

Re-arrange objective function so all variables on left hand side

Set out in tableau

Pivot:

• Pivot column is most negative element in objective row
• Use ratio test to find pivot element
• Dive pivot row by pivot element
• For each row, subtract or add multiples of pivot row so pivot column element is zero

Repeat pivot until no negatives in objective row