Given e A[x] and a A, let e[x := a] denote the element of A resulting from

interpreting occurrences of x in e by a, interpreting the expressions of the form

p a0 q by a0 and interpreting expressions of the form (ee0 ) using @.

(i) Give the clauses in a defifinition of e[x := a] by recursion on the structure of

e. [2 marks]

(ii) For each e A[x] show how to defifine an element xe A with the property

that

@(xe, a) = e[x := a] (7)

for all a A. [6 marks]

(d) Recall the usual encoding of Booleans in -calculus. Using Part (c)(ii), show

that in any combinatory algebra A there are elements True, False A and a

function If : A A A satisfying

@(If (a, b), True) = a

(11)

@(If (a, b), False) = b

(12)

for all a, b A

[5 marks]

7CST1.2021.6.8

7

Data Science

(a) Let xt be the number of new COVID infections on date t. We anticipate

approximately exponential growth or decay, xt+1 (1 + )xt , and we would

like to estimate from a dataset (x1, . . . , xT ).

(i) Find the maximum likelihood estimator for for the model

Xt+1 Poisson

You have available a 20 Gbyte disc on which you need to hold an indexed sequential

fifile consisting of variable length records each having a 20 byte key. Records,

including the key, are typically 500 bytes long but never exceed 1000 bytes. The

total size of all the records is never more than 10 Gbytes.

(a) Suggest, in detail, how you would represent this fifile on the disc. You should

choose an organisation that allows

(i) effiffifficient insertion of new records,

(ii) effiffifficient updating of existing records identifified by key, and

(iii) effiffifficient inspection of all records in key order.

[14 marks]

(b) If the total size of the database is 10 Gbytes, estimate, for your organisation

of the fifile, how many disc transfers would be needed to access a record with

a given key, and estimate how many transfers would be required to read the

entire database in sequential order. [6 marks]

2 Computer Design

Modern dynamic random access memories (e.g. DRAM, SDRAM and RAMBUS)

all support burst mode read and write access.

(a) Give an outline of the bus activity for a burst mode read access. [4 marks]

(b) Explain the difffference between a direct mapped cache and an associative cache.

[4 marks]

(c) What cache line replacement policies are typically used for a direct mapped

cache and a set associative cache? [4 marks]

(d) Why are caches able to exploit burst mode accesses, and why is a write buffffer

often used? [4 marks]

(e) What is bus snooping and what does it achieve? [4 marks]

2CST.2002.5.3

3 Digital Communication I

Consider the real-time transport of audio across a network.

(a) What are the advantages of digitising the audio? [5 marks]

(b) What are the disadvantages and how can they be mitigated? [5 marks]

(c) What characteristics of the end-to-end channel across the network would be

desirable, and how are these difffferent from those which would be desirable for

time-insensitive data? [5 marks]

(d) Discuss the applicability of asynchronous and synchronous multiplexing in

carrying real-time audio traffiffiffic. [5 marks]

3

[TURN OVERCST.2002.5.4

4 Concurrent Systems and Applications

(a) The suspend() and resume() methods defifined on java.lang.Thread can be

used to block and unblock a designated thread. Explain why these methods

should not be used. [4 marks]

(b) Defifine a Java class Barrier that pairs together two difffferent kinds of thread

(A and B) in a concurrent system. It should support two methods,

enterA(Object o) and enterB(Object o). A call to one enter method

blocks until a call is made to the other. At that point both invocations

continue, enterA returning the value passed to enterB and vice versa.

[8 marks]

(c) A number of barbers and customers have to co-ordinate their actions in a

barbers' shop. Each barber has a chair in which a customer sits while receiving

a haircut and in which that barber dozes when he has no customer. There is

plenty of waiting space.

Defifine Java classes Barber, Customer and Shop to model this situation. The

class Customer should support two methods:

(i) Barber getHaircut(Shop s) - request service at s, blocking until the

customer is served and returning the allocated barber;

(ii) void leaveChair(Barber b) - signal that b can take another customer.

The class Barber should support two corresponding methods:

(i) Customer getCustomer(Shop s) - wait to be allocated a customer at s;

(ii) void finishedCustomer(Customer c) - signal to c that the haircut is

fifinished and wait for c to leave the chair.

[8 marks]

4CST.2002.5.5

SECTION B

5 Comparative Programming Languages

This question concerns the representation of parse tree nodes for expressions

composed of integer constants, identififiers, and integer operators for addition,

subtraction, multiplication and division. In a typeless language, such as BCPL,

each node can be implemented as a vector whose fifirst element holds an integer

identifying the node operator. The size of the vector and the kinds of value held in

the other elements then depends on this node operator.

(a) Complete the description of how you would represent such integer expressions

in a typeless language. [5 marks]

(b) Suggest how you would represent such integer expressions in C and either ML

or Java. [10 marks]

(c) Brieflfly discuss the relative merits of your C data structure compared with that

used in the typeless approach. [5 marks]

6 Compiler Construction

(a) Assuming a Java type is given to each variable, state a method by which an

overloaded operator (such as +,- etc.) in a Java program can be determined

to be an int, real or other operator. [3 marks]

(b) Explain, using pseudo-code as appropriate, how to convert a syntax-tree into

stack code such as that used in the JVM. For the purposes of this question, you

only need consider trees representing bodies of void-returning functions, and

these bodies only as consisting of a list of statements of the form int x = e;

or x = e; where x ranges over variables and e over expressions; expressions

contain variables, integer constants, the binary operator + and static method

invocations. [10 marks]

(c) Show how a sequence of simple stack code instructions, such as those used

in your answer to part (b) above, can be translated into a sequence of

instructions for a register-oriented architecture of your choice, for example

ARM or Pentium. [7 marks]