ssf  Define the terms opaque type and concrete type. [5 marks]
The following is a shortened version of one of the definition modules described in
the Modula-2 user manual:

Provide a suitable specification for type Semaphore as it might appear in the
associated implementation module. [5 marks]
Write a fragment of Modula-2 code which uses a variable of type Semaphore and
exploits the three procedures given above. Explain what the code does when each
of the three procedures is invoked. [10 marks]
1 [TURN OVER
CST.93.10.2
2 Modula-2
What is a Modula-2 union? [3 marks]
A Modula-2 program includes the following declarations:
TYPE

The variable test is of type Node, a record in which one field is either of type
NumType or of type OpType, the latter representing a dyadic operator together with
pointers to its two operands.
The procedure MakeNumNode takes a single CARDINAL parameter and returns a
pointer to a Node which includes a NumType field. The procedure MakeOpNode
returns a pointer to a Node which includes an OpType field.
The effect of the example assignment statement is to assign to test a syntax tree
which represents the expression 4*(7-2).
Provide a suitable declaration for type Node. [5 marks]
Write the procedures MakeNumNode and MakeOpNode. [6 marks each]
2
CST.93.10.3
3 Common Lisp
Consider trees that have two kinds of nodes. A node is either a leaf, labelled by a
number, or a branch, and has one or more subtrees. For example:
3 9
1
8
7 2
5
One imagines that the edges from each branch node are numbered from left to right
starting from 0. A list of these numbers thus designates the path from the root to
a node. In the tree shown above, the path (2 1 1) designates the path to the node
labelled 2.
(a) Describe a good representation for such trees in Lisp. [3 marks]
(b) Write a Lisp function getnode such that (getnode path tree) returns the node
of tree designated by path, assuming that the tree contains such a node.
[5 marks]
(c) Write a Lisp function maxpath such that (maxpath tree) returns the maximum
of the leaf nodes in the tree, together with the path to that node. For the tree
shown above, maxpath should return 9 as the maximum and (0 1) as the path.
[12 marks]
4 Programming Language Compilation
Discuss the merits of translating the abstract syntax tree representation of a
program into assembly language by means of
(a) an ad hoc recursive tree walking program [10 marks]
(b) an algorithm based on tables automatically generated from tree translation
rules [10 marks]
5 Operating Systems
Contrast UNIX pipes with a general, asynchronous message-passing facility as a
basis for inter-process communication between processes which run in separate
address spaces. [20 marks]
3 [TURN OVER
CST.93.10.4
6 Operating System Functions
Describe the functionality you would expect to find in the file system directory
service of a multi-user operating system. [10 marks]
Describe two ways in which multiple names for the same file can be supported, and
what problems arise as a result. [10 marks]
7 Data Structures and Algorithms
Show that comparison-based sorting uses at best about n log n comparisons if there
are n things to be sorted. [5 marks]
Compute the expected inefficiency ratio from using linear insertion as against an
O(n log n) sort on lists of 16 and 32 objects. This is the ratio by which the expected
number of comparisons exceeds the theoretical minimum. [5 marks]
Show that binary insertion may reasonably be expected to be an O(n log n) sort.
[5 marks]
About how many comparisons would you expect to take place when sorting 1024
7-bit values by binary insertion? [5 marks]
8 Data Structures and Algorithms
Describe and justify an algorithm for determining the length of the shortest path
between all pairs of vertices in a directed graph with lengths. [8 marks]
Design and provide an estimate of the size of a data structure by which the actual
paths could be retrieved after the calculation above. [12 marks]
9 Graphics I
RasterOp is the name given to an operation which generates, from a number of
rasters of pixel values, another raster of pixel values.
Describe suitable versions that could be used
(a) to move a window on screen while preserving background [12 marks]
(b) to blend two images in proportions given by a mask [8 marks]
4
CST.93.10.5
10 Numerical Analysis I
In the IEEE binary standard (IEEE 754) what do the parameters p (precision),
emin and emax specify? How is the value of an exponent e stored? [3 marks]
Explain the terms normalised number , denormal number , hidden bit and NaN .
[4 marks]
In terms of the stored bit-pattern, how can each of the following be recognised: ±0,
±∞, denormal number, NaN. [4 marks]
Suppose for some special-purpose hardware that a floating-point implementation is
to be provided using only one byte for each representable number. Suppose also
that, as far as possible, the principles of IEEE binary arithmetic are to be adhered
to. If a sign bit of 0 represents a positive number, p = 4, emin = −2 and emax = 3
what should the following bit patterns represent?
00000000 00000001 00110000 11110000 11110001 [5 marks]
Consider the evaluation under IEEE arithmetic of the functions
(a)
x
2 + 2
x
2 + 1
(b) ln(x
2 + 2)
where x and the function values are representable numbers, but x
2
is not. Show
how you would formulate the evaluation of (a) and (b) to avoid this problem.
[4 marks]
5 [TURN OVER
CST.93.10.6
11 Discrete Mathematics
Let g : A → B be a function with domain A and range B. Show that the relation
R defined by
xRy ⇔ g(x) = g(y)
is an equivalence relation on A. [4 marks]
Let f(n, r) be the number of surjections from a set A having n elements to a set B
having r elements. Show that
f(n, r) = r

f(n − 1, r − 1) + f(n − 1, r)

. [8 marks]
Evaluate f(n, r) in the cases:
(a) r = 2 [3 marks]
(b) r = (n − 1) [5 marks]
12 Proving Programs Correct
Explain the difference between partial and total correctness and give examples to
illustrate the difference. [4 marks]
Does the usual FOR-rule for partial correctness work for total correctness? Justify
your answer. [4 marks]
Does the usual WHILE-rule for partial correctness work for total correctness?
Justify your answer. [4 marks]
Explain why it is necessary to assume that expressions are free of side effects for
the Assignment Axiom to be sound. [4 marks]
Explain how arrays can be reasoned about using Hoare logic and discuss some of
the pitfalls of na¨ıve approaches

Describe in detail the use of the bilinear transformation s → 2 T z − 1 z + 1 for the design of digital filters from analogue filters. Discuss the advantages and disadvantages of the method. [8 marks] It is required to design a second order maximally flat digital low-pass filter having a 3dB cut-off frequency of 0.2fs where fs is the sampling frequency. The design is to be based on the analogue Butterworth filter defined by: |H(jω)| 2 = 1 1 + ω ωc 2N where N is the filter order and ωc is the 3dB cut-off frequency. It can be shown that the s-domain transfer function for the second order Butterworth filter is given by: H(s) = 1 1 + √ 2 s ωc + s ωc 2 Calculate the coefficient values for the corresponding digital low-pass filter and draw its block diagram. [12 marks] 1 [TURN OVER CST.93.9.2 2 Digital Communication II Describe the Asynchronous Transfer Mode (ATM). [5 marks] What are the benefits and drawbacks of the choice of ATM over normal packet switching? [5 marks] An ATM switch can be built with a set of buffering input and output ports and an unbuffered interconnection network. Describe with examples the desirable attributes of such a network. [10 marks] 3 Computer System Modelling Consider a transaction system with 20 workstations and 4 fileservers, each with 2 discs. The system is monitored and it is found that, for each transaction, on average: 40 ms of workstation CPU is consumed 6 ms of fileserver CPU is consumed 10 ms of fileserver disc is consumed. The system is arranged so that asymmetry in disc access is limited to 3 : 2 from highest to lowest, as is fileserver-usage asymmetry. Workstation usage is balanced. Perform a bottleneck analysis of the system for throughput and response time. State any assumptions made. [10 marks] Give an estimate of the response time when the system is handling (a) 10 (b) 100 (c) 1000 transactions per second. Note: a balanced system with K devices and N customers has a utilisation U = N N + K − 1 [10 marks] 2 CST.93.9.3 4 Graphics II Compare object-space and image-space visibility tests in synthesising an image for display. [12 marks] Describe one visibility test in detail. [8 marks] SECTION B 5 Designing Interactive Applications Explain the term user's conceptual model. How is the user's conceptual model formed? [4 marks] Describe Fitts' law and Hick's law and explain how each might influence the design of an information display. [4 marks] The receptionist at a small research laboratory is required to field incoming messages and make sure that they reach the recipient in a timely manner. Some messages arrive by word of mouth, others by phone, courier, e-mail or FAX. There are about 100 recipients, most of whom are researchers. They spend a large proportion of their time in meetings of one sort or another, some of which are held in offices, the remainder in conference rooms. The receptionist endeavours to avoid interrupting important meetings unnecessarily. It is proposed to build a system based upon Active Badge technology to improve message handling activities in the laboratory. Each member of staff wears an active badge. An existing Location Server provides client applications with up-to-date information about the location and movements of each active badge. Imagine you have to develop a requirements specification that might reasonably arise from your own investigations. Write down three or four key requirements. [2 marks] On one side of paper, draw up the screen layout for your proposed application and annotate it with the rationale for each key design decision. [10 marks] 3 [TURN OVER CST.93.9.4 6 Optimising Compilers Consider a flowgraph, containing 3-address instructions, which represents a sourcelevel routine. Let e be an expression (e may be considered to be a right-hand side 3-address instruction, i.e. either x or x op y where x and y are variables). We say that e is very busy at a node n if all paths from n compute the expression e at least once and each such computation yields the same value as evaluating e at n would (i.e. no modification of its variables occurs between n and the first occurrence of e on any path from n). Let V B(n) be the set of very busy expressions at n. (a) Give data flow equations for V B(n). [4 marks] (b) Give the relationship, if any, to the set Avail(n) of expressions available at n including the direction (forwards/backwards) of the analyses. Indicate whether either inclusion V B(n) ⊆ Avail(n) or Avail(n) ⊆ V B(n) holds. [4 marks] (c) Sketch an algorithm to compute V B(n), briefly commenting on any initialisation. [4 marks] Suppose now that we compile a program in a call-by-need functional language into 3-address code using closures (i.e. λ().e0 ) to represent laziness. Given a functional definition f(x, y, z) = e we have notions of f being strict in, or needing, its second parameter y. Point out similarities and differences between these notions and that of y (or y()) being very busy at some, to be determined, point in the 3-address code form of e. [8 marks] Hint: you may find it helpful to consider separately (a) a case where e uses only the conditional function and strict primitive functions such as + (b) a case such as f(x, y) = g(x, y + 1) 7 Artificial Intelligence II Discuss any two methods for computing information about the three-dimensional layout of surfaces in a scene, given one or more images of the scene. Illustrate your answer with appropriate mathematical relationships and fragments of computer programs. [20 marks] 4 CST.93.9.5 8 Database Topics Describe the differences between navigational and algebraic data manipulation. [6 marks] What problems would arise when incorporating an algebraic style of data manipulation into a persistent programming language such as PS-ALGOL? How might they be solved? [14 marks] SECTION C 9 Natural Language Processing Write on four of the following topics, describing the problems they raise and their significance for natural language processing. [5 marks each] (a) Worst-case (exponential) syntactic ambiguity (b) Semantic interpretation of embedded propositions (such as John thinks the prime minister is a grey man) (c) Focus and anaphoric reference (d) Unification as a technique for expressing syntactic rules (e) Defeasible reasoning for interpreting utterances (f ) Natural prosody for speech synthesis from text 5 [TURN OVER CST.93.9.6 10 Semantics Explain what is a well-founded binary relation, and state the principle of wellfounded induction. [3 marks] Show that the binary relation C on the integers which is given by m C n if and only if n < m 6 100 is well-founded. [2 marks] Consider the ML declarations fun f(x) = if x > 100 then (x − 10) else f(f(x + 11)); fun g(x) = if x > 100 then (x − 10) else 91; Prove, by induction on the well-founded relation C, that f and g determine equal integer-valued functions. Hint: for the induction step you may find it helpful to consider separately the cases x > 100, x = 100, 90 6 x < 100 and x < 90. [15 marks] 6 CST.93.9.7 11 Types Describe the relation of β-reduction between expressions in the second order lambda calculus λ2. Explain the Church-Rosser and strong normalisation properties of this relation. How do they lead to a procedure for deciding whether two closed, typable λ2 expressions are β-convertible? [8 marks] If α is a type variable and σ is a λ2 type, the 'existential type' ∃α.σ is defined to be ∀β.((∀α.σ→β)→β), where β is a new type variable not occurring in σ. Show that there is a closed λ2 expression, Pair, of type ∀α.(σ→∃α.σ). [5 marks] Given valid λ2 type assertions Γ ` E : ∃α.σ Γ, x : σ ` N : σ 0 where α and β do not occur free in Γ or σ 0 , show how to construct a λ2 expression Case(E, α, x, N) such that (a) Γ ` Case(E, α, x, N) : σ 0 , and (b) if Γ ` M : (α 7→ τ )σ where τ is a type not containing free occurrences of β, then Case(PairτM, α, x, N) β-reduces to (x 7→ M)(α 7→ τ )N. (Here (α 7→ τ ) denotes the operation of substituting τ for the type variable α and (x 7→ M) denotes the operation of substituting the expression M for the identifier x.) [7 marks] 7 [TURN OVER CST.93.9.8 12 Concurrency Define the notion of observation equivalence (≈) for CCS agents. [5 marks] Find definitions of CCS agents A, B, C and D with the following transition graphs. A ? ? ? ? τ τ τ b b a ? B ? ? ? τ a τ b b a C ? ? ? τ b b a τ a a D ? b [5 marks] For each pair (P, Q) of these four agents A, B, C, D, determine whether or not P is observation equivalent to Q. (You may use the fact that ≈ is an equivalence relation.) [10 marks]

Show that an N-point Discrete Fourier Transform (DFT) X(p) = N X−1 n=0 x(n)e −j2πnp/N may be evaluated in terms of two N 2 -point DFTs if N is even. [6 marks] Without giving a detailed mathematical derivation, discuss how this result may be used to give the Fast Fourier Transform algorithm. Discuss the advantages of the algorithm compared with direct evaluation of the DFT. [5 marks] Discuss briefly the use of window functions in discrete spectrum analysis. [3 marks] The generalised Hamming window function is defined by w(n) = α − (1 − α) cos(2πn/N) for 0 6 n < N = 0 otherwise where 0 6 α 6 1. Obtain an expression for the DFT of this window function. [6 marks] 1 [TURN OVER CST.93.8.2 2 Digital Communication II Define the layers of the OSI Reference Model and briefly describe their primary functions. [7 marks] Using this model, describe the significant differences between the protocols of a traditional file transfer mechanism and a distributed file system. [9 marks] How is security supported by the two mechanisms? [4 marks] 3 Computer System Modelling The state diagram for a Markov chain showing transition rates is shown below. Solve for state occupancy probabilities. 4 6 3 2 a b c [5 marks] The steady state distribution for the number of jobs in an M/M/1 queue, k, is pk = (1 − ρ)ρ k k = 0, 1, 2, . . . where ρ = λ/µ < 1. Here λ and µ are the mean arrival rate and mean service rate respectively. Find the first and second moments of this distribution and hence verify that the variance of the number of the jobs in the system is given by ρ (1 − ρ) 2 [10 marks] What does this result show about the predictability of system performance at high loads? [5 marks] 2 CST.93.8.3 4 Developments in Technology EDSAC (1949) was the first practical stored-program computer in operation. Although it had no subroutine jump instruction, a method for using subroutines was devised by David Wheeler. Quote and explain the instruction sequences for subroutine entry and return. [12 marks] Describe the corresponding instruction sequences that you would use in a modern processor. [8 marks] SECTION B 5 Designing Interactive Applications Distinguish the terms needs analysis and requirements analysis. Provide an example to illustrate the difference. [3 marks] What is a strong requirement? Provide counter-examples and explain why each example is not a strong requirement. [4 marks] What role does a functional specification play in a requirements specification? Give a one-sentence example. [3 marks] The receptionist at a small research laboratory is required to field incoming messages and make sure that they reach the recipient in a timely manner. Some messages arrive by word of mouth, others by phone, courier, e-mail or FAX. There are about 100 recipients, most of whom are researchers. They spend a large proportion of their time in meetings of one sort or another, some of which are held in offices, the remainder in conference rooms. The receptionist endeavours to avoid interrupting important meetings unnecessarily. It is proposed to build a system based upon Active Badge technology to improve message handling activities in the laboratory. Each member of staff wears an active badge. An existing Location Server provides client applications with up-to-date information about the location and movements of each active badge. Sketch out the methods you would employ to establish the users' needs for the proposed system. Describe the categories of information you would pass on to the designer and illustrate each with one or two examples. [10 marks] 3 [TURN OVER CST.93.8.4 6 Optimising Compilers Many modern architectures have provision for only 32-bit values in registers. However, ANSI C requires code such as extern void g(int); extern void f(int x) { char c = x; c += 1; g(c); } to have the effect that a call to f() causes g() to receive a parameter value as though c were stored in memory, i.e. in the range CHAR MIN to CHAR MAX. You may assume that char holds 8-bit values and the range is either -128..127 or 0..255. While this example clearly requires range reduction following the incrementation of c, it is claimed that this is not always necessary. One brutal technique to allocate char variables to registers is to treat them as int variables and achieve ANSI C conformance by range reduction just before each reference in the same manner that load-byte hardware might. Develop an optimisation technique which might reduce the amount (static or dynamic) of such range reduction in code like: extern char p(int v[100]) { unsigned char r = 0; int i; for (i=0; i<100; i++) r = (r<<1 ^ r) + v[i]; return (r & 128) != 0; } Little credit will be given for mere hand-compilation. [20 marks] Hints: 1. Consider similarities to live variable analysis. 2. Consider whether register reads or writes occur more often. 4 CST.93.8.5 7 Artificial Intelligence I A sliding-tile puzzle consists of three black tiles, three white tiles and an empty space, thus: B1 B2 B3 W1 W2 W3 There are three legal ways of moving a tile, each with an associated cost: slide into the adjacent empty location — cost 1 jump over one tile into the empty location — cost 1 jump over two tiles into the empty location — cost 2 The goal is to have all the white tiles to the left of all the black tiles and to achieve this at minimum cost. The final position of the empty space is not important. (a) Represent the problem using the following knowledge representation schemes: (i) production system rules [5 marks] (ii) a semantic network [5 marks] In one sentence, describe the different emphases of these two schemes. [1 mark] (b) State two possible heuristics to help solve this problem. [2 marks] (c) For a planner to solve this puzzle, what operators (i.e. planning actions) would be needed? [7 marks] 8 Database Topics Explain the ways in which the data modelling concepts 'IS-A', 'IS-PART-OF' and 'IS-AN-INSTANCE-OF' have been addressed in database design methodology. Your discussion should include the network, relational and functional data models, as well as object-oriented databases. [20 marks] 5 [TURN OVER CST.93.8.6 SECTION C 9 Natural Language Processing Describe the main differences between formal languages (such as logics or programming languages) and a natural language (such as English). [8 marks] What different requirements do these differences place on techniques for (a) syntactically parsing (b) semantically interpreting natural, as opposed to formal, languages? [6+6 marks] 10 Semantics State the principle of fixed point induction. [4 marks] D is a cpo of 'integer streams': it comes equipped with a continuous function in : (Z × D)⊥ → D that possesses a continuous inverse out : D → (Z × D)⊥. (Thus the composition of in and out in either order is the appropriate identity function.) Moreover D has the property that the identity function idD ∈ (D→D) is the least fixed point of the continuous function δ : (D→D) → (D→D) which maps f ∈ (D→D) to δ(f) ∈ (D→D), where for each d ∈ D δ(f)(d) = in([(n, f(x))]) if out(d) = [(n, x)] in(⊥) if out(d) = ⊥ Let mapS : D → D be a continuous function satisfying that for all d ∈ D mapS(d) = in([(n + 1, mapS(x))]) if out(d) = [(n, x)] in(⊥) if out(d) = ⊥ Using fixed point induction for δ, show that there is at most one solution d ∈ D to the equation d = in([(0, mapS(d))]) Hint: if d1 and d2 are both solutions, consider the property of f ∈ (D→D) given by 'f mapS = mapS f and f(d1) v d2'. [16 marks] 6 CST.93.8.7 11 Types Explain what is meant by the statement 'every closed, typable expression in ML possesses a principal type'. Does a similar property hold for the second order lambda calculus λ2? [4 marks] What is meant by a type scheme in ML? Give the rules for inductively defining ML type assertions of the form Γ ` M : ρ where ρ is a type scheme, Γ is a finite function from identifiers to type schemes, and M is an ML expression built up from identifiers using let-expressions, lambda abstractions and function applications. [9 marks] This fragment of ML is augmented by fixed-point expressions fix x.M, which are typed according to the rule Γ, x : ρ ` M : ρ Γ ` fix x.M : ρ (FIX) (Free occurrences of x in M become bound in fix x.M.) Show that the closed expression fix x.λy.(xx)y is typable in this augmented system. Hint: find a type scheme ρ for which x : ρ ` λy.(xx)y : α→β holds. [4 marks] Is the expression typable if the use of the rule (FIX) is restricted by requiring ρ to be a type rather than a type scheme? [3 marks] 7 [TURN OVER CST.93.8.8 12 Concurrency State the expansion law for observation congruence between CCS agents. [4 marks] A counter which can assume any of the natural numbers as its state is specified as a CCS agent by: Count0 def = inc.Count1 + zero.Count0 Countn def = inc.Countn+1 + dec.Countn−1 for n > 0 It is required to implement the counter by linking together several copies of an agent C and one agent B, where C def = inc.(C _ C) + dec.D D def = d.C + z.B B def = inc.(C _ B) + zero.B Here the linking, P _ Q, of two agents P and Q is an abbreviation for (P[f] | Q[g]) \ L where L = {i 0 , z0 , d0 } and f(`) = i 0 if ` = i z 0 if ` = z d 0 if ` = d ` otherwise and g(`) = i 0 if ` = inc z 0 if ` = zero d 0 if ` = dec ` otherwise (a) Use the expansion law to prove that D _ C ≈ C _ D and D _ B ≈ B _ B. (You may assume without proof that τ.P ≈ P, for any P.) [5 marks] (b) Letting C (0) stand for B and C (n) (when n > 0) stand for (C _ · · ·(C _ (C | {z } n copies of C _ B))· · ·) show that D _ C(n) ≈ C (n) . Deduce that C (n) satisfies the defining equations for Countn up to observation congruence. (You may assume without proof that B _ B ≈ B, that observation equivalence is a congruence relation for the operation of linking and that linking is associative up to observation equivalence. State carefully any other general principles you use.)