```                            Analysis Of Algorithms
----------------------
Questions On Chapter 6
----------------------

1  A particular factory manufactures N different products 1...N. Production
happens in N-day cycles. On day 1, the machines are set up to produce
product 1, and a quantity of product 1 is produced. On day 2, the machines
are changed round to produce product 2, and a quantity of product 2 is
produced. This continues for N days, and then repeats. Suppose that the
cost of changing round the machines is high and needs to be minimised by
making the products in a different order. Suppose that the cost C[i,j] of
changing round the machines from making product i to making product j
is known for each pair of products i and j, and that the optimum order of
the N products is to be found which minimises the total change-round cost
over the N days of a production cycle. Show that this is equivalent to
another well-known problem. How long does it take to solve the problem?

2  Suppose a plotter is being used to plot a scatter diagram - that is a
collection of "random" points on the paper. The plotting takes a long
time because of the amount of time it takes for the plotter's pen to move
from one point to the next. It is suggested that the points be sorted
into some suitable order before plotting begins so as to minimize the
total time taken to produce the plot. Does this correspond closely to
any of the well-known problems in chapter 6? How much time should be
spent looking for a fast algorithm to produce the optimum ordering?

3  Show that the halting problem is NP-hard, i.e. that all problems in the
class NP can be reduced to it. Is the halting problem NP-complete?

4  Give a brief indication of why each of the following problems is in the
class NP:

The longest path problem
The job scheduling problem
The code generation problem
The timetable problem
The digital circuit layout problem

5  In the TSP, each town must be visited only once. Suppose instead we want
to find the shortest tour which visits each town at least once - i.e.
multiple visits are allowed. This is a new problem - the multi-visit TSP
or MTSP. Show that MTSP reduces to TSP, i.e. MTSP <= TSP, i.e. MTSP is no
harder than TSP.
```