A seismic probe bores itself into the seabed, going as deep as it can before running out of fuel. This takes about five minutes. It rotates its spiral drill head at rate R(t) that follows a pre-programmed profile. Its downwards velocity y is proportional to R and to the square-root of the probe's weight w, and is given by y = 3.6 R(t) w. The weight of the probe is the weight of its fuel, which starts at 1500 plus its own intrinsic weight, which is fixed at 35. The fuel weight decreases at a rate of 1.2 R(t). (a) Give the state vector for a forwards FDTD simulation of this system using Euler's Method. [1 mark] (b) Assuming a function is provided that returns R(t), give a program that uses Euler's Method (a straightforward, forward finite-difference simulation) to determine the depth achieved. [4 marks] (c) Describe the errors you might expect if you chose a time step that was inordinately small or inordinately large. What is the maximum time step for Euler's method to remain stable in this system? Suggest, with justification, a suitable time step. [6 marks] (d) Recall that a backwards stencil uses the values at the end of the timestep to determine the rate of change during that timestep. When is this usable and useful in general? this application? Give modified code that implements the backwards stencil method. [6 marks] (e) For the probe to drill as deep as possible, should R(t) generally start small and grow larger? Justify your answer

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 ove Complete the computation to find the distribution Pr(A|e). [4 marks]

Suppose a floating-point representation for unsigned numbers has a three-bit mantissa and a three-bit exponent. Suggest a useful encoding range by stating the minimum and maximum values representable without a hidden bit. [4 marks] (b) Modify your answer to part (a) for when a hidden bit is used. [3 marks] (c) Give roughly the smallest positive IEEE single-precision floating-point number, x, for which sin(x) is not meaningless. [3 marks] (d) Describe four different rules for rounding a floating-point number and say which is generally used and why. [2 marks] (e) Give two techniques for determining the number of steps used in an iteration. (Do not describe iterating until no change.) Say when one technique is preferred to the other. [4 marks] (f ) A scientific library uses the formula (a+b+c)/(d+e) where a . . . e are floatingpoint. Aside from using an IF statement to check for division by zero, what further IF statement(s) should be included to ed precision?

If is a well-founded relation on S, show that every non-empty subset of S contains an element that is minimal for . [4 marks] (c) Let (P, 6) be a finite partially ordered set. A chain X P is a totally ordered subset of P, and an antichain Y P is a subset such that no two distinct elements y, y 0 Y are comparable. The antichains {Yi | 1 6 i 6 k} cover P if P S k i=1 Yi . Prove that the smallest possible number of antichains in a cover of P is exactly the length of a longest chain in P. [Hint: If not, consider the set of minimal elements in a minimal counterexample.] [13 marks] 12 Computation Theory (a) Describe the action of a Turing machine. [4 marks] (b) Define what is meant by a configuration of an N-state, k-symbol Turing machine. [2 marks] (c) Explain briefly how to enumerate all possible Turing machine computations, so that a given computation can be characterised by a single natural number code c. [5 marks] (d) Show that it is not possible to compute the maximum distance travelled by the Turing machine head from its initial position during halting computations as a function of the code c. Any results that you use should be stated clearlysis I For IEEE Single Precision = 2, p = 24, emax = +127, emin = 126. Explain these parameters. Ho bits are required to store the exponent and the significand, respectively? How is the exponent stored? [6 marks] By means of a table, or otherwise, describe how the following quantities are represented: zero, denormal numbers, normalised numbers, infinities and Not a Number (NaN ). [5 marks] Let represent any of the operations + or /. Let x be any normalised or denormal number or 0. Writing n for any NaN value, what do the following evaluate to? (a) x n (b) n (c) x (d) [6 marks] Let z be the smallest representable positive normalised number. What are the values of the following? (e) z (f ) the largest representable number smaller than z

. Examples are a national health service, a national police service and a global company with worldwide branches. Communication must be supported within and between domains and external services may be accessed. For example, health service domains may all access a national Electronic Health Record service; police service domains may all access a national Vehicle Licensing service. (a) (i) Define publish/subscribe communication. [3 marks] (ii) What are the advantages and disadvantages of offering publish/subscribe as the only communication service?

You are a 22nd century historian researching the "FEE" (First Epidemic Era) of 2019-2025, for which records are patchy. You research which government policy was in place in any given week during this historic phase. Policies, in order of severity, are: No restrictions, Tier 1, Tier 2, Tier 3, and Lockdown. (a) From other historic sources, you know the following about sequences of policy levels: if you are in a given policy level, there is a 40% chance you will stay there, a 20% chance that you will be upgraded to the next-highest (more severe) level next week, and a 10% chance that you will be downgraded to the next-lowest (less severe) policy level. The background lockdown probability (which applies if nothing more informative is known about lockdown) is 10%. For each observation sequence, there is also a 5% chance of the sequence ending at any point. Transitions to any other policy level beyond those already described are equally likely. Observation sequences begin with each policy level at equal likelihood. Using the information given above, construct the full transition probability table. [7 marks] (b) You want to estimate which policy was in place for the first six weeks of 2025, but unfortunately, the only information you have about this is a sequence of Covid case numbers for these six weeks: [0 99], [0 99], [> 200], [> 200], [> 200], [100 199]. You know that case loads are associated with policy levels as in the Table below. Describe how you can calculate the sequence of most likely policy levels for these 6 weeks, giving numbers for at least three steps of the calculation. Assume that all policies are equally likely in the week preceding the first week. [8 marks] No Restriction Tier 1 Tier 2 Tier 3 Lockdown 0-99 cases 5% 10% 20% 50% 90% 100-199 cases 15% 40% 40% 30% 9% > 200 cases 80% 50% 20% 20% 1% (c) In which respects is the modelling described above not fully adequate to describe an actual epidemic?

(a) Describe the syntax of the synchronized keyword in Java and explain the effect on the runtime behaviour of a program. (b) Compare and contrast the approaches of using a single mutex to guard access to an entire data structure and using individual mutexes on each unit of storage within the data structure. (c) Consider a queue data structure, based on a linked list. The operations pushTail and popHead are to be provided and it should be possible to execute both concurrently whenever doing so would be safe (but not when it would be unsafe). Provide a Java implementation of the data structure and concurrency control mechanism, including the methods to push new items on the tail of the queue and to pop items from the head. 2 Algorithms II (a) Briefly describe the Dijkstra algorithm for finding shortest paths from a single source and explain why it cannot be used on graphs with negative edge weights. [Pseudocode is not required.] (b) Describe and explain in detail the Johnson algorithm that finds all-pairs shortest-paths by repeatedly applying Dijkstra to each vertex, even in graphs with negative edge weights. [Pseudocode is not required but all phases of the algorithm must be clearly explained.] (c) Some people wonder why it would not be simpler to reweight edges by adding a sufficiently large constant K to each edge weight so as to make all the weights positive. Prove that this cannot work. (d) In Johnson's algorithm, why do we introduce a new vertex s? Could we not use, instead of a new vertex, one of the vertices of the original graph? Either prove that we can or provide a counterexample.

(a) Describe in detail an algorithm that returns the minimum distance from a point to a line segment in two dimensions. Ensure that you include all of your assumptions and all necessary mathematical calculations. [7 marks] (b) A quadratic Bezier curve is defined by three points, P1, P2, P3, and a parameter, t: P(t) = (1 t) 2 P1 + 2t(1 t)P2 + t 2 P3, 0 t 1 Describe an algorithm that draws the quadratic Bezier curve, using straight lines only, to within a tolerance . You may use the algorithm from part (a) and you may assume that you already have an algorithm for drawing a straight line. [8 marks] (c) Consider the control of detail in a curve that is represented by a sequence of many straight line segments. Describe how Douglas and Pucker's algorithm can be used to remove superfluous points. You may use the algorithm from part (a).

(a) Consider a simple random walk, Sn, defined by S0 = a and Sn = Sn1 + Xn for n 1 where the random variables Xi (i = 1, 2, . . .) are independent and identically distributed with P(Xi = 1) = p and P(Xi = 1) = 1 p for some constant p with 0 p 1. (i) Find E(Sn) and Var (Sn) in terms of a, n and p. [4 marks] (ii) Use the central limit theorem to derive an approximate expression for P(Sn > k) for large n. You may leave your answer expressed in terms of the distribution function (x) = P(Z x) where Z is a standard Normal random variable with zero mean and unit variance. [6 marks] (b) Consider the Gambler's ruin problem defined as in part (a) but with the addition of absorbing barriers at 0 and N where N is some positive integer. Derive an expression for the probability of ruin (that is, being absorbed at the zero barrier) when starting at position S0 = a for each a = 0, 1, . . . , N in the t 2

5 Logic and Proof (a) State (with justification) whether the following formula is satisfiable, valid or neither. Note that a and b are constants. h x [q(x) r(x)] r(a) x [r(x) q(a) p(x) q(x)]i p(b) r(b)

(b) Attempt to prove the formula [x y R(x, y)] x z R(x, f(z)) by resolution, with brief explanations of each step, including the conversion to clause form. [4 marks] (c) Give a model for the following set of clauses, or prove that none exists. {R(x, y), R(y, x)} {R(x, f(x))} {R(x, y), R(y, z), R(x, z)}

The Prolog predicate perm(+In,-Out) generates all permutations of the input list In. A programmer implements perm/2 as follows: perm([],[]). perm(L,[H|T]) :- take(L,H,R), perm(R,T). The predicate take(+L,-E,-R) removes one element (E) from the input list L and unifies R with the remainder of L. Thus, the list R has one element fewer than L. (a) Consider the perm/2 predicate: (i) Explain briefly in words the operation of the perm/2 predicate. (ii) Provide an implementation of the take/3 predicate. (iii) Give the complete sequence of answers (in the correct order) generated by perm([1,2,3],A). (b) A student attempts to invoke the query perm(A,[1,2,3]). (i) Explain what happens and why. [5 marks] (ii) Implement a predicate sameLength/2 which is true if the two parameters are lists of the same length. (iii) Using sameLength/2, or otherwise, provide an implementation of safePerm/2 which generates permutations regardless of the order in which the parameters are provided: both safePerm(+In,-Out) and safePerm(-Out,+In) should generate all permutations of In. The order in which these permutations are generated is not important.

Write complete program that uses the functions listed below. Except for the printOdd function, main should print the results after each function call to a file.

Write function called productEven, that takes as its parameter an input file. The function should read two integers and calculate the total product of only even numbers between them.

Write function in the C++called summary that takes as its parameters an input and output file. The function should read two integers find the sum of even numbers, the sum of odd numbers, and the cumulative product between two values lower and upper

How do software engineering tools change as systems scale? Discuss this question with reference to (a) a 2000-line device driver for a safety-critical sensor on board an aircraft; (b) a 100,000-line engine control unit for a diesel engine that adapts it for use in trucks, generators or irrigation pumps; (c) a 1,000,000-line social networking site such as Facebook or MySpace; (d) a 50,000,000-line operating system.

(a) A web server is an application that listens for incoming network connections on TCP port 80. Once a connection is established, the task of processing client requests and sending replies can be handled by an instance of a Worker class which you may assume already exists. Worker implements the java.lang.Runnable interface and has an accessible constructor that takes as argument a java.net.Socket object representing the network connection to a client. Provide the Java code for a webserver which, upon start-up, attempts to listen on TCP port 80 and starts a new Thread running a new Worker for every connection. Your program should print helpful error messages indicating the likely cause of problems when it is unable to proceed as expected. [10 marks] (b) A busy web server might expect to handle concurrent requests to read and update some shared data and could use Timestamp Ordering (TSO) to enforce isolation between concurrent transactions. (i) Explain how TSO enforces isolation. (ii) Is TSO appropriate for a web server application? Explain your reasoning.

Consider the following grammar for expressions (where Id is a terminal symbol representing an identifier resulting from lexical analysis): Expr ::= 1 | 2 | Id | Expr + Expr | Expr / Expr | Expr ^ Expr | (Expr) (a) Explain in what principal respect this grammar is unsatisfactory. (b) Assuming further that + is to be left-associative, ^ is to be right-associative and / is to be non-associative are allowed), re-write the grammar to reflect this. (c) List the terminal symbols and non-terminal symbols, and count the production rules both in the original grammar and in the grammar in your answer to part (b). Indicate the start symbol in both grammars. [2 marks] (d) Define a type or types (in C, Java, or ML) suitable for holding an abstract syntax tree resulting from your answer to part (b). (e) Give a brief and elementary explanation of the principles of how the grammar resulting from part (b) might be used to create a syntax analyser taking a token stream as input (via calls to function lex()) and giving as output an abstract syntax tree corresponding to part (d). Mention both hand-written and automatically-generated syntax analysers. (f ) Summarise any issues related to left- or right-associative operators in the two techniques (in implementing the parser and in constructing the tool) you outlined in part (e).

You work at a social media company, and your task is to detect cyberbullying messages based on the text they contain. You have access to a large number of messages, N, which have been manually labelled as "OK" and "bullying". (a) How can you apply a Naive Bayes classifier to the task and evaluate it? Describe the approach, including how you would estimate the parameters. [3 marks] (b) You decide to use precision and recall instead of accuracy as the evaluation metric for this task. Why does this decision make sense, and how are the metrics calculated? [1 mark] (c) Your colleague wants to hire two more human annotators to re-label your training data. Why might this be a good idea, how would you measure agreement in this task, and do you think this would improve your classifier in any way? [3 marks] (d) Due to repeated media coverage of cyberbullying, your company introduces a new policy stating that as many cyberbullying messages as possible are to be found and deleted, while still making sure the number of non-filtered messages remains high. Some additional manual labour is made available for this change. How does this affect your evaluation strategy, and how can you adapt the classifier to comply better with the new strategy? (Tip: a development corpus could be of use.)

kindly answer all the questions