Computer-Aided Software Engineering tools are designed to help developers manage complexity. What are the two main types of complexity such a tool must deal with? [4 marks] What are the tools traditionally used to manage each type of complexity? [6 marks] For each type, describe briefly one case history in which a serious failure was caused.

A Java programmer is attempting to write a class BigNo which is intended to handle integers of arbitrary size. An integer is represented as a list of single digits arranged so that the least significant digit is at the head of the list. In outline, class BigNo is declared thus: class BigNo { private int dig; private BigNo rest; public BigNo(int n) { this.dig = n%10; if (n/10 == 0) this.rest = null; else this.rest = new BigNo(n/10); } private BigNo add(int c) . public BigNo add(BigNo that) . private BigNo add(BigNo that, int c) { if (this.rest == null) return that.add(this.dig+c); if (that.rest == null) return this.add(that.dig+c); int d = this.dig + that.dig + c; return new BigNo(d%10, this.rest.add(that.rest,d/10)); } The final return statement refers to a constructor which is not shown. Why are two constructors needed? Provide the missing constructor. Does it have to be public? [4 marks] Why are there three add() methods? Explain why one is public and two are private. Provide bodies for the two add() methods for which only heading lines are shown. [6 marks] Provide a suitable toString() method. [4 marks] Suppose jack and jill are BigNo representations of the integers 46 and 57 respectively. Describe carefully the effect of the call jack.add(jill)

Write brief notes on the facilities for lightweight concurrency in Java. You should cover the following topics, using code fragments to illustrate your answer: (a) creating a thread (b) mutual exclusion (c) signalling (d) asynchronous interruption (e) managing priority [4 marks each] 4 Compiler Construction With reference to a strictly-typed block-structured programming language, write brief notes on the following topics: (a) the allocation and recovery of records stored in a heap (b) the implementation of variables of union type (c) the allocation of arrays with non-manifest bounds (d) the implementation of labels and GOTO commands.

Consider the following two separation-of-duty policies: (a) A transaction needs approval from two people, one in group A and one in group B. (b) A transaction needs approval from two distinct users of the system. Which of these is harder to implement using the standard Unix access control mechanisms, and why? [10 marks] Sketch an implementation of the easier policy using Unix mechanisms. [5 marks] Describe at least two alternative mechanisms that might be used to implement the other policy. [5 marks] 6 Data Structures and Algorithms Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted. [6 marks] Describe another algorithm that will find the same element, but with a guaranteed worst case time of O(n). [7 marks] Give a rough estimate of the number of comparisons each of your methods would perform when k = 50, operating on a set of 100 random 32-bit integers. [7 marks] 7 Computer Design Gordon Moore's law originally applied to memory size (in bits), but also applies to processor speed (in MIPS). However, main memory access latency does not follow Moore's law. (a) What is Moore's law? [4 marks] (b) Why doesn't main memory latency decrease in proportion to processor cycle time? [6 marks] (c) What mechanisms are used to hide poor main memory access times and why do these mechanisms work?

(a) A software module controls a car park of known capacity. Calls to the module's procedures enter () and exit() are triggered when cars enter and leave via the barriers. Give pseudocode for the enter and exit procedures (i) if the module is a monitor [8 marks] (ii) if the programming language in which the module is written provides only semaphores [4 marks] (b) Outline the implementation of (i) semaphores [4 marks] (ii) monitors [4 marks]

Eight sensors each feed eight bits of information to a circuit which processes the information. It is decided that instead of using 64 signal lines, the data will be multiplexed onto eight data lines with three address lines used to indicate the sensor using the data lines. In fact, the sensors will be continually cycled through in order. (a) A three-bit counter is required to cycle through the values for the address lines. Design it. You may assume the availability of a clock signal. [7 marks] (b) An 8:1 multiplexer has eight data inputs, three control inputs and an output. The value of the control inputs determines the data input which is selected as the output. Design an 8:1 multiplexer. [5 marks] (c) Show how these components would be used to build the required system. [5 marks] (d) How would you modify the scheme if there were 256 sensors continually cycled through in order?

Let A be a set, R be a relation on A. What conditions must be satisfied for the following? (i) R is a partial order on A [3 marks] (ii) R is a total order on A [1 mark] (iii) R is a well-founded relation on A [2 marks] x A is a minimal element for R if y A,(y, x) R y = x. x A is a maximal element for R if y A,(x, y) R y = x. For each of the sets A = N (natural numbers) and A = Z (integers) we define relations: (a) R1 = 6, the standard ordering (b) (a, b) R2 if and only if q A such that aq = b (c) (a, b) R3 if and only if p A such that ap = b, where | p | N is a prime Explain with reasons which of conditions (i)-(iii) is satisfied when a relation Rj is defined on either N or Z. Identify the maximal and minimal elements in each case.

One of the most important contributions of the theory of computation has been to establish that the halting problem is not decidable. Give a clear statement of this result (you are not asked to prove it). [5 marks] Define a configuration of a 2-register machine at a particular point during the execution of some program. [3 marks] By considering the total number of configurations or otherwise, show that it is not possible to compute an upper bound for the contents of the two registers during halting computations as a function of the program code and the initial contents of the two registers

The parameters for IEEE Double Precision are: = 2, p = 53, emin = 1022, emax = 1023. Explain the terms significand, sign bit, exponent, normalised number, denormal number, hidden bit, precision as used in IEEE arithmetic. What values does the hidden bit have for normalised and denormal numbers? [8 marks] In which order are the significand, sign bit and exponent stored? How is the exponent stored? Deduce how many bits are required to store the Double Precision exponent. How many bits are required to store a Double Precision number? [5 marks] Deduce the meaning of the following Double Precision bit patterns (where dots indicate a number of zeros): (a) 01111111111100 . . . 00 (b) 11000000000000 . . . 00 (c) 01111111111110 . . . 00 (d) 11111111111100 . . . 01 (e) 10000000000000 . . . 00 (f ) 00000000000010 . . . 00 (g) 00111111111100 . . . 00

(a) When numerically computing the solution to an ordinary differential equation (ODE) that involves higher-than first-order derivatives: (i) What is to be done about the higher-than first-order terms, and how can this be accomplished? [4 marks] (ii) Illustrate this step for the following ODE, in which functions r(x) and q(x) are known and we seek to compute the solution y(x): d 2 y dx2 + q(x) dy dx = r(x) [4 marks] (b) (i) State the incrementing rule for the Euler method of numerical integration, in terms of: f(xn), the estimate of the solution f(x) at the current point xn f(xn+1), the new estimate of f(x) for the next point xn+1 the integration stepsize h, which is the interval (xn+1 xn) f 0 (xn), the expression given by the ODE for the derivative of the desired solution f(x) at the current point xn [4 marks] (ii) What might happen to your solution if the stepsize h is too large? [2 marks] (iii) What might happen to your solution if you make the stepsize h too small? [2 marks] (iv) What is the primary advantage of the Runge-Kutta method over the Euler method for numerical integration of ODEs? [2 marks] (v) Under what conditions might you wish to make the stepsize h adaptive rather than fixed? How should you adapt it?