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.