Modelling exam Qs

Question 1

Explain why, in the worst case, both packing algorithms have the same order of complexity

Answer 1

For both algorithms (in the worst case) each number has to be compared with all previous numbers/bins (before being placed into a new bin)

Question 2

Explain the purpose of the objective function from an LP formulation

Answer 2

Arcs AE, BD etc… form a cut in the network.

This line of formulation therefore maximises the total flow in the network, so finds the capacity.

Question 3

Explain BD-DH=0

Answer 3

The total flow into each node must be equal to the total flow out of each node (excluding the source and sink). The only arc leading into D is BD and the only arc out of D is DH and hence BD-DH=0.

Question 4

An algorithm has complexity O(n*). When n = 200 a computer takes 0.03s to implement
the algorithm. How long will the computer take to implement the algorithm when n = 20
000?
Explain why your answer is only an approximation.

Answer 4

It is an approximation because O(n^2) indicates an approximate relationship

Question 5

What is a cut?

Answer 5

A partition of the set of vertices into two sets; the source and sink must be in different sets.