Miller-Rabin test to check whether a number N is composite. This will involve computing a N1 mod N for some value of a. [10 marks] Carry out the steps for N = 65 and a = 1, 2, 8 and 12. on what each partial result tells you about N and which cases (if any) help you to decide whether N is prime or what its factors might be. Preetend throughout the calculation that you do not know that 65 = 513. Proceed as though 65 were a huge number, imagining that you do not know at the outset whether it is prime or composite and that you are certainly unable to spot any factors.

Optimising Compilers Briefly summarize the main concepts of strictness analysis including the kind of languages to which it applies, and the way in which both system-provided and user-defined functions f yield strictness properties f # (relate the types of f and f #). Give the strictness functions corresponding to the following ternary functions: (a) f1(x,y,z) = x*y + z (b) f2(x,y,z) = if x=9 then y else z (c) f3(x,y,z) = pif x=9 then y else z where pif e1 then e2 else e3 is the parallel conditional: it behaves similarly to the standard conditional in that if e1 evaluates to true or false then it yields e2 or e3 as appropriate; however, evaluation of e2 and e3 occurs concurrently with e1 to allow the pif construct also to terminate with the value of e2 when e2 and e3 both terminate with equal values (even if e1 computes forever). Comment briefly how your strictness property for f1 would change if the multiplication returned zero without evaluating the other argument in the event that one argument were zero.

A lease is a concurrency primitive similar to a lock (only one node may hold a lease at any time); the difference is that a lease times out if it is not renewed for some time. After timing out, another node can acquire the lease. (a) Briefly summarise how leader election works in the Raft consensus algorithm, and discuss the commonalities and differences between leader election and a lease. (b) In a partially-synchronous system with crash-recovery failures, is it possible to guarantee that a lease is always held by exactly one node? Justify your answer. [5 marks] (c) You are asked to design a lease algorithm for a system in which the set of nodes is not known in advance, and may change over time. Can the Raft leader election algorithm be used here? Why/why not? [2 marks] (d) A colleague proposes the following lease algorithm: There are three servers, each storing a value that is initially null. Assume every client has a unique ID clientId 6= null. Every 10 seconds, each client that wants to acquire the lease, or currently holds the lease, sends a request (acquire, clientId) to all three servers. When a server with current stored value v receives (acquire, n): If v = null v = n, or if its value was last set more than 30 seconds ago, then it sets its value to n and replies true. This counts as "setting the value", even if the value does not change. If its value was last set to v 6= n less than 30 seconds ago, it leaves its value unchanged and replies false. If a client receives two or more true responses from the servers, it now holds the lease, otherwise it does not hold the lease. Discuss the strengths and weaknesses of this algorithm. What faults does it tolerate? What assumptions does it make for its correctness? How might the algorithm be improved to avoid some assumptions or weaknesses?

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.

Consider the transformations used in the construction and rendering of a threedimensional model on a screen. (a) List the three principal transformations in the processing pipeline and explain their roles. [6 marks] (b) Why is it convenient to represent the transformations as matrices? [2 marks] (c) What are homogeneous coordinates? Explain how they are used in modelling these transformations as matrices. (d) Derive the matrix to represent a perspective transformation for a viewer at the origin of a point in three dimensions to a point on a screen in the plane z = d.

(e) Perspective in classical art has vanishing points towards which parallel lines converge. Explain mathematically why this is the case and show how to calculate the location on the screen of the vanishing point for lines in a particular direction. [5 marks] [Hint: It may be helpful to represent lines parametrically in vector form as P(s) = A + sV where V is a direction and A is any point on the line.] 4 Computer Graphics and Image Processing Consider a curve defined by polynomial parametric segments Pi(s) for i = 1, 2, . . . m that interpolates a set of points {Ai}0im in three dimensions. (a) What is meant by Ck continuity at the junction of two segments? [3 marks] (b) What is the least order of the polynomials that must be used to achieve Ck continuity at the junctions? [2 marks] (c) Derive the Overhauser formulation for a set of weighting functions w2(s), w1(s), w0(s) and w1(s) so that the cubic curve segment joining Ai1 and Ai can be expressed as Pi(s) = w2(s)Ai2 + w1(s)Ai1 + w0(s)Ai + w1(s)Ai+1 for 1 < i < m. [10 marks] (d) Extend this formulation to give a set of parametric patches Pi,j (s, t) for 1 < i < m and 1 < j < n interpolating a surface through an array of points {Ai,j}0im,0jn.

Hoare Logic and Model Checking We consider the CTL temporal logic over atomic propositions p AP: StateProp ::= | > | | 1 2 | 1 2 | 1 2 | p | A | E , PathProp ::= X | F | G . (a) Alice (a), Bob (b), and Carol (c) are bank tellers. They sit at their till (t), until they need to give money to their customers, which they can do in gold (g) or silver (s) coins, which are stored in two different vaults. Each vault needs two tellers to turn keys simultaneously, but if it determines that there are more than two tellers present, it locks itself and phones the police. Once they have retrieved the coins, they can return with coin (r). This yields atomic propositions AP = Pers Loc, where Pers ::= a | b | c and Loc ::= t | g | s | r, so that for example a state labelled with {at, bs, cr} is one where Alice is at her desk, Bob is waiting to open the silver vault, and Carol is returning with coin. Give CTL formulas for (i) Alice repeatedly serves clients with coins. [2 marks] (ii) When Bob picks a vault, he stays there until it gets opened. [2 marks] (iii) Carol is always able to serve clients with coins. [2 marks] (iv) The vaults never lock. [2 marks] (b) Explain why Carol's property cannot be expressed in LTL. [2 marks] (c) A chemist is trying to determine what can be synthesised from the chemicals they have. They know all possible reactions: 2 H2 + O2 2 H2O, C + O2 CO2, etc. (i) Describe a model of reactions from given starting quantities. [3 marks] (ii) Keeping track of the exact amount of chemicals is challenging, so the chemist looks only at whether each is present. Describe such an abstract model, and give a simulation relation between the two models. [4 marks] (iii) State, for each of these two properties, which of the models (i) and (ii) is such that if the property holds for it, then it holds for the other: 1/ that dangerous chemicals like CO are never synthesised; 2/ that desirable chemicals like pure gold (Au) can be synthesised. Explain why. [3 marks] 9 CST2.2021.9.10 9 Information Theory (a) A long-term and self-replicating data storage system based on DNA sequences is being developed. Advantages include huge information density ( 1019 bits/cm3 ) and extreme persistence: dinosaur DNA can still be extracted from fossils. The letters A,C,G,T each occur with equal probability, independently, without sequence constraints. Consider sequences consisting of 100 such letters. (i) How many sequences are possible, and with what probabilities? [2 marks] (ii) Random variable X selects such a sequence. Calculate H(X), the entropy of X, starting from Shannon's definition. [2 marks] (iii) Sequence replication may be corrupted such that the last two letters are reproduced randomly in the post-replication sequences, denoted Y . What is the conditional entropy H(X|Y ), and what is the mutual information I(X; Y ) for this error-prone replication process? [4 marks] (b) Financial markets generate daily asset valuations like the time-series f(t) in the left panel, reflecting the dynamics of greed and fear. But underlying such fluctuating indices there may exist meaningful trends, such as a business cycle (right panel). Write an auto-correlation integral that can extract the coherent quasi-periodic signal on the right from noisy valuations f(t), and explain how computing the Fourier transform F() of f(t) makes it efficient. [5 marks] 0 0 Figure a sine wave in noise and b autocorrelation (c) Brain tissue contains about 105 neurones per mm3 , and each neurone has a single output axon whose length r (in dimensionless units) before terminating at synapses to other neurones has probability density distribution p(r) = e r . 0 1 2 3 r 0 1 p(r ) = e r Note: Z 0 e r dr = 1 (i) Define differential entropy h for continuous random variables in terms of general probability density distribution p(x), and then calculate the value of h in bits for this axonal length distribution p(r) = e r . [5 marks] (ii) If the axon's branching terminals make altogether about 1,000 synapses (connections) with different neurones within the axonal tree's 1 mm3 volume, uniformly distributed, roughly how many bits of entropy describe the uncertainty of whether a neurone gets such a connection? [2 marks] 10 CST2.2021.9.11 10 Machine Learning and Bayesian Inference Consider the following Bayesian Network: A B C D E All random variables (RVs) are Boolean. For an RV R we denote R = T by r and R = F by r. We have Pr(a) = 0.1, Pr(b) = 0.2, Pr(d|b) = 0.7 and Pr(d|b) = 0.4. For the remaining RVs we have A B Pr(c|A, B) F F 0.2 F T 0.2 T F 0.5 T T 0.6 C B D Pr(e|C, B, D) F F F 0.3 F F T 0.5 F T F 0.6 F T T 0.3 T F F 0.1 T F T 0.2 T T F 0.1 T T T 0.9 In this question you must use the Variable Elimination algorithm to compute Pr(A|e). You should begin with the factorisation Pr(A|e) = Pr(A) X B Pr(B) X C Pr(C|A, B) X D Pr(D|B) Pr(e|B, C, D). You should express factors as tables of integers, leaving any necessary normalisation until the final step in Part (d). (a) Define conditional independence of two RVs X and Y with respect to a third RV Z. [2 marks] (b) Deduce the factor FE,D(B, C) corresponding to the summation over D. [8 marks] (c) Deduce the factor FE,D,C (A, B) corresponding to the summation over C. [6 marks] (d) Complete the computation to find the distribution Pr(A|e). [4 marks] 11 CST2.2021.9.12 11 Mobile and Sensor Systems (a) Contrast the measurement of biosignals from conventional medical devices with those from smartphone and wearable device sensors. [5 marks] (b) A researcher wishes to screen users for the hand tremor symptom via a smartphone app. They recruit a cohort of people with diagnosed tremor and a control cohort about which nothing is known. The researcher has a smartphone that collects data from its sensors. They give it to each participant and ask them to hold it as still as they can while sitting. The researcher then uses the data captured to develop a tremor classifier that has sensitivity 0.97 and specificity 0.99. (i) Why is getting a high specificity a particular priority for a smartphonebased screening app? [4 marks] (ii) Explain why the prevalence of the disease must also be taken into account in deciding whether to deploy this app, illustrating your answer by considering tremor prevalences of 0.1% and 5%. [3 marks] (iii) The smartphone app is deployed. It asks users to test their tremor monthly at home, when sitting and trying to hold their phone still. Why might the screening be less effective than expected from the collected data? [3 marks] (iv) The researcher changes the app to do background tremor screening. The app now constantly monitors for the user holding the phone appropriately. When it observes this it captures sensor data and applies the tremor classifier. Discuss the advantages and disadvantages of this approach compared to the previous approach. [5 marks] 12 CST2.2021.9.13 12 Optimising Compilers The following excerpt from a program in C-style code is optimised with a compiler using code-motion transformations. The function read() returns a signed integer from the user. l0: a = read(); l1: b = read(); l2: p = &a; l3: q = &b; l4: r = &p; l5: if (read() > 0) { l6: a = b + 5; l7: } else { l8: i = 0; l9: while (i < 10) { l10: c = b + 5; l11: **r += *q; l12: i += 1; l13: } l14: a += c; l15: } l16: print(a); (a) Describe loop-invariant code motion (LICM) and which expresion(s) in the loop above it should move. [2 marks] (b) Describe a simple data-flow analysis and a way of using it to identify loopinvariant expressions. Use this to analyse the code above. [5 marks] (c) Explain whether all expressions described in Part (a) are found through the analysis in Part (b). [2 marks] (d) Describe an analysis that can aid in making LICM more precise in this example. [3 marks] (e) Apply the analysis from Part (d) to the code above and redo the analysis from Part (b) to show which expressions described in Part (a) are now found. [4 marks] (f ) Describe another code motion transformation that could be applied to the code after LICM and show the final code after its application. [4 marks] 13 CST2.2021.9.14 13 Principles of Communications (a) Multicast routing provides IP packet delivery from a source to a set of receivers. One clear use case for this is for large scale content distribution (e.g. software updates). In such a case, we would expect the end-to-end protocol to provide flow and congestion control. How might such a reliable multicast transport protocol be designed? [10 marks] (b) Mobile systems move. In cellular networks, this is can be handled by the radio access network, and measuring signal strength to determine to which cell a handset is best assigned. In the Internet, the IP layer typically hides this information. How might we combine information across layers to make mobile IP routing more efficient? In your discussion, pay attention to problems of software layering, and also of managing the dynamics (e.g. route flapping) in such systems. [10 marks] 14 CST2.2021.9.15 14 Quantum Computing (a) Find the eigenvectors, eigenvalues and spectral decomposition of the observable A = 0 1 1 0 and give the outcome of measuring the expectation of the observable on the states: (i) |0i (ii) 1 2 (|0i |1i) (iii) 1 2 |0i + 3 2 |1i [8 marks] (b) A quantum mechanical system has Hamiltonian H = H1 + 2H2 It is desired to use a quantum computer to approximately simulate the operator e iHt for some t. It is possible to build quantum circuits U1 and U2 to perform the operations U1 = e iH1t U2 = e iH2t Give a circuit, U, consisting of one of more instances of U1 and U2 that approximates e iHt such that e iHt U = O(t 3 ). Show your calculations to verify that the circuit does indeed achieve this. [8 marks] (c) Quantum Phase Estimation can be used to estimate the ground state energy of quantum mechanical systems. The Inverse Quantum Fourier Transform is a key component of Quantum Phase Estimation. Give the circuit for the 2-qubit Inverse Quantum Fourier Transform using only gates from the set {H, CT, CNOT}, where CT is a controlled T gate. [4 marks] 15 CST2.2021.9.16 15 Types (a) In a simply-typed lambda calculus augmented with first-class continuations, booleans, a list type and its iterator (i.e., fold, but not full recursion), write a function every : (X Bool) List X Bool such that every p xs returns true if every element of xs satisfies p, and false otherwise. This function should also stop iterating over the list as soon as it finds a false element. You may use SML- or OCaml-style notation if desired, but explain any notation used beyond the basic lambda calculus. [4 marks] (b) In the monadic lambda calculus with state, suppose we change the typing rule for reading locations to not cause a monadic effect: If we suggest changing the monadic lambda calculus to permit treating reads as pure: l : X ; ` !l : X (i) Is this rule still typesafe? Informally but carefully justify your answer. [2 marks] (ii) Is the following common subexpression elimination transformation sound? Either give an argument why it is, or supply a counterexample and explain why it shows it is not. [6 marks] let x = return e1; let x = return e1; let y = e2; =====> let y = e2; let z = return e1; [z/x]e3 e3 (c) In System F augmented with existential types, give an existential type for the interface of the natural numbers, and give an implementation for it. [8 markssuch that a = qb + r and 0 r < b. [6 marks] (b) Prove further that the highest common factor of a and b is equal to the highest common factor of b and r. [2 marks] (c) Derive Euclid's algorithm for finding the highest common factor of two numbers. [3 marks] (d) Determine the algorithm's efficiency by finding a limit for the number of divisions required in its execution expressed as a function of a. [3 marks] (e) Find all values x, y Z satisfying 72x + 56y = 40. [3 marks] (f ) Find all values z Z satisfying 56z 24(mod 72). Express the answer in the form z a(mod m). [3 marks] Computer System Modelling A database system has a central processor and three (different) discs. Measurements are taken for 1000 transactions on a lightly loaded system and the following observations are made. The CPU scheduler initiated or resumed transaction processing 10,000 times. The total CPU usage was 25 seconds. Disc 1 made 5000 transfers with an average transfer time of 10 ms. Disc 2 made 2000 transfers with an average transfer time of 50 ms. Disc 3 made 2000 transfers with an average transfer time of 20 ms. Derive the visit counts, service times and transaction service demands. What is the bottleneck device? What is the maximum throughput of the system measured in transactions per second? [6 marks] Describe two balanced systems which bound the throughput of the system. What is the maximum throughput of these systems? [7 marks] Recall that the throughput of a balanced system with K devices, N customers and service demand D per device is X(N) = N (N + K 1) 1 D How many transactions do you expect to be in the system with a throughput of 7 transactions per second? [7 marks] 4 CST.2000.9.5 8 Neural Computing Give evidence supporting the view that the main computational load that has shaped the evolution of the human brain is "social computation", with sexual success being the ultimate measure of the value of an algorithm or neural design feature. Say what implications this has for: The cognitive skills and perceptual faculties that have been selected for in brain evolution, as contrasted with the goals which are the traditional focus of AI. The design of face recognition algorithms, which aim to interpret facial expression, gesture, and intent, as well as gender and identity. The construction of the theory that other persons have minds, too. Models of action, planning, and interaction between self and others. [8 marks] Comment on whether this "social computation" view of human brain evolution implies that brain science is less relevant to the goals of computer science than is usually thought. [2 marks] Answer any five of the following seven short questions: (a) Roughly what is the total number of neurones in the human brain? (b) Roughly what is the total number of synapses in the human brain? How does this compare with the total number of stars in our galaxy, and with the total number of galaxies in the known universe? (c) Why is nerve impulse propagation described as "saltatory", and what purposes are achieved by this method of signalling? (d) What is the approximate speed of nerve impulse propagation in warm-blooded animals, in metres/sec? (e) Why is "white matter" white, what cells are responsible for this, and what purpose do they serve?