he case l = 0 defines the null sequence. In each of the following cases, establish whether the set defined is recursively enumerable: (a) the set of all recursive subsets of N [5 marks] (b) the set of all recursive sequences of natural numbers [2 marks] (c) the set of all finite sequences of natural numbers [5 marks] A finite sequence of natural numbers is specified by a pair (l, x), where l N is the number of elements, and x : [1, l] N is a function that defines those elements. 4 CST.2000.4.5 6 Data Structures and Algorithms Describe in detail both Prim's and Kruskal's algorithms for finding a minimum cost spanning tree of an undirected graph with edges labelled with positive costs, and explain why they are correct. [7 marks each] Compare the relative merits of the two algorithms. [6 marks] 7 Operating System Functions Why is it important for an operating system to schedule disc requests? [4 marks] Briefly describe each of the SSTF, SCAN and C-SCAN disc scheduling algorithms. Which problem with SSTF does SCAN seek to overcome? Which problem with SCAN does C-SCAN seek to overcome? [5 marks] Consider a Winchester-style hard disc with 100 cylinders, 4 double-sided platters and 25 sectors per track. The following is the (time-ordered) sequence of requests for disc sectors: { 3518, 1846, 8924, 6672, 1590, 4126, 107, 9750, 158, 6621, 446, 11 } The disc arm is currently at cylinder 10, moving towards 100. For each of SSTF, SCAN and C-SCAN, give the order in which the above requests would be serviced. [3 marks] Which factors do the above disc arm scheduling algorithms ignore? How could these be taken into account? [4 marks] Discuss ways in which an operating system can construct logical volumes which are (a) more reliable and (b) higher performance than the underlying hardware. [4 marks] 5 [TURN OVER CST.2000.4.6 8 Computation Theory Let N be the natural numbers {0, 1, 2 . . . What is meant by each of the following statements? The subset S N is recursive. The subset S N is recursively enumerable. [5 marks] How would you extend the definition of recursive enumeration to sets of computable functions? [3 marks] A sequence of natural numbers is a total function s : N N. The sequence is recursive if and only if s is computable. A finite sequence of natural numbers is specified by a pair (l, x), where l N is the number of elements, and x : [1, l] N is a function that defines those elements. The case l = 0 defines the null sequence. In each of the following cases, establish whether the set defined is recursively enumerable: (a) the set of all recursive subsets of N [5 marks] (b) the set of all recursive sequences of natural numbers [2 marks] (c) the set of all finite sequences of natural numbers [5 marks] 6 CST.2000.4.7 9 Numerical Analysis I Define the absolute error x and relative error x in representing a number x. How are these errors related? Which type of error is associated with the term loss of significance? Define machine epsilon m.

(a) (i) In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net continues to iterate in response to a given input? [3 marks] (ii) How many stable content-addressable memories would you expect a fully connected Hopfield network consisting of 100 neurons to be capable of storing? [1 mark] (iii) What property of those memory patterns would make it most probable that you could successfully train the network to store the maximum number, and why? [3 marks] (b) Explain how five independent dimensions of visual processing are multiplexed together into the three available spatial dimensions of neural tissue, by the structure of the cubic millimetre hypercolumns in the brain's visual cortex. [5 marks]