You can solve this Part (a) after read Network (a) Consider the following electrical network and corresponding oriented graph.

Component 1 is a voltage source providing 6 volts, components 2 and 3 are resistors with resistances 10 and 15 ohms, respectively, and component 4 is a capacitor with capacitance 0.5 farads.

(i) Using the spanning tree whose edges correspond to components 2 and 3, find the fundamental cycle and cutset matrices (where the components are taken in the order 2, 3, 1, 4).

(ii) Write down all the component equations.

(iii) Combine the results of parts (b)(i) and (b)(ii) into a matrix equation of the form

Hx = y +Kx.

(iv) Find the state equation.

You may use Gaussian elimination if you wish, but you may find it easier to work directly with the individual component, cycle and cutset equations.

You can solve this part after read graph 4

(b) Consider the following image displayed on a 4-screen (with the rows numbered from top to bottom, and columns numbered from left to right).

(i) Draw the pruned quad tree that stores this image.

(ii) Explain how you would modify the pruned quad tree in part (a)(i) to obtain the pruned quad tree that represents the image reflected about the top-left to bottom-right diagonal. Draw the pruned quad tree that represents this reflected image.

(iii) The north neighbour algorithm can be modified to give the west neighbour of a pixel. State which pairs of quadrants are opposites, and which pairs of quadrants take the role of lower quadrants in the west neighbour algorithm.

(iv) On your quad tree for part (a)(i), mark the path arising from the steps of the west neighbour algorithm when determining the west neighbour of the pixel in row 6, column 5.

(c) This part of the question is intended to give you practice in understanding and communicating mathematical ideas that have been presented in an informal way. When faced with the task of sorting a list of names into alphabetical order, many people scan through the list for the name nearest the beginning of the alphabet, then write it down in a new list and cross it out in the old list. Then they repeat the process for the next name, and so on.

If you had such a list to sort, extending over two pages (say with fifty names on each), then an alternative approach would be to first sort the two pages separately before merging the two sorted lists together.

Write a short account (400-600 words) commenting on these two methods, explaining why the alternative approach is likely to be considerably quicker for a list of 100 names.

Your account should contain:

• a comparison of the informal methods described above with the more formal sorting algorithms described in Graphs 4 ;

• a discussion of the number of comparison and writing operations that these two methods are likely to require.