can someone solve this

Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate the performance of a system's memory hierarchy, a user writes a simple test program. The program, known as sum, accepts N as an input parameter, and allocates an array of N 32-bit integer elements in physically contiguous memory. sum contains an inner loop that scans sequentially over the array and computes the sum of all the elements. The program measures the total time taken to execute several thousand iterations of the scan, and uses this to compute the average rate at which the computation proceeded. Write sample assembly code for a performance-optimised implementation of sum's inner loop for a super-scalar RISC processor. You may assume that the array always contains a multiple of eight elements, and you are encouraged to demonstrate your knowledge of techniques such as loop unrolling and instruction scheduling. Indicate how your loop might execute on a processor capable of issuing two integer operations per cycle. [8 marks] In addition to sum, the user writes a similar program called store. Instead of totalling the array, store simply writes to each element, setting its contents to zero. The user invokes the programs over different sizes of array in order to generate the following graph. The x axis indicates the size of the array (in bytes) that the program was operated over, while the y axis shows the average rate at which array elements were processed Ignoring startup effects, describe the behaviour of the memory system, and hence account for the graph. What can you deduce about the workstation's memory hierarchy? [8 marks] 3 [TURN OVER CST.98.8.4 5 Business Studies The figure shows a section of a PERT diagram for a small software project, together with the number of programmer-days each task is estimated to take. (a) What is the critical path in a PERT diagram and why is it important? What is the critical path in the PERT diagram shown below? [5 marks] (b) One analyst and two programmers are assigned to the project, in addition to the manager. How long will the project take? [5 marks] (c) Derive the equivalent GANTT chart for the project. [5 marks] (d) Task 8 slips by 2 days. How does this affect the project? What actions, if any are required, can be taken to alleviate the slippage?n the Rho method and (informally) why it might be hoped that it will do what it is expected to. [6 marks] (c) The extents and manners in which parts of your code rely on random numbers and the consequences of these turning out to be either especially fortunate or especially awkward. [5 marks] (d) A coarse estimate of the total run-time for the factoriser in circumstances when the input number has exactly two large prime factors, and an equally crude estimate of the size that N would need to be before the factorisation process took a whole day of CPU time on a modern desktop workstation. You may suppose that around 1013 basic operations are available in that amount of time. [5 marks] 5 [TURN OVER CST.98.8.6 7 Optimising Compilers (a) Define the notion of an expression being available at a node in a flowgraph in terms of possible execution flows of control; explain carefully the form which available expressions might take in your framework. [4 marks] (b) Demonstrate that calculating exactly which expressions are available at a given node is uncomputable (you may assume that it is uncomputable to determine whether two given boolean expressions involving arithmetic always yield the same result value). [4 marks] (c) Give an algorithm to calculate available expressions and state carefully how the algorithmic result is related to the set of expressions which are available according to your definition in part (a). [4 marks] (d) Justify any discrepancy in (c) by reference to safety of the approximation with respect to the usual use of available expressions in optimisation. [4 marks] (e) On a machine with four registers available for register allocation (by colouring), give a program for which common sub-expression elimination (CSE) results in worse code being generated than if CSE had not been performed, noting any assumptions of timing factors for the target machine which justify the code being worse. [4 mar 8 Artificial Intelligence Give short definitions of any ten of the following terms: (a) Circumscription (b) Situation Calculus (c) Closed World Assumption

Automatic Discovery of Heuristics (f ) Inter-Wave Search (g) Abduction (h) Unique Names Assumption (i) Microworld (j) Maximum Expected Utility (k) Intelligent Agent Architecture (l) Fuzzy Control (m) Constraint (n) Problem Space (or Search Space) (o) Non-Monotonic Reasoning [2 marks each] 7 [TURN OVER CST.98.8.8 9 Database Topics What are the aims of the Object Database Standard ODMG 2.0? [3 marks] Describe the ways in which the Standard contributes to Object-Orientated Distributed Programming, making particular reference to distribution and heterogeneity. [5 marks] What benefits does conformance to the Standard bring to the application developer? It may be helpful to consider (a) schema definition and maintenance (b) transaction management (c) object interchange format (d) interoperation with relational data storage [12 marks] 10 Information Retrieval You work for a company that takes news stories from all over the world and provides reports on specified topics to customers, for example on political developments in the new Republic of Rumbaza during 1997. Your company's staff use a retrieval system to extract the material on which they base their reports from the company's very extensive archive of stories. The retrieval system is a 20-year-old makeshift and is to be scrapped. You are asked to design the new retrieval system. (a) Give a detailed description of the retrieval devices the new system will offer, explaining why they are available and how they will work. What facilities will the user have for modifying his or her search specification in response to system output? [15 marks] (b) What do you regard as the most difficult problem to be tackled, and why? [5 marks] [Assume that the stories in the file are texts betweeith date and source headers in a standardised form.] 8 CST.98.8.9 11 Information Theory and Coding Consider a binary symmetric communication channel, having source alphabet X = {0, 1} with probabilities {0.5, 0.5}. Its output alphabet is Y = {0, 1} and its channel matrix is 1 1 where is the probability of transmission error. (a) What is the entropy of the source, H(X)? [1 mark] (b) What is the probability distribution of the outputs, p(Y ), and the entropy of this output distribution, H(Y )? [3 marks] (c) What is the joint probability distribution for the source and the output, p(X, Y ), and what is the joint entropy, H(X, Y )? [4 marks] (d) What is the mutual information of this channel, I(X; Y )? [2 marks] (e) How many values are there for for which the mutual information of this channel is maximal? What are those values, and what then is the capacity of such a channel in bits? [3 marks] (f ) For what value of is the capacity of this channel minimal? What is the channel capacity in that case? [2 marks] The Fourier transform (whether continuous or discrete) is defined in the general case for complex-valued data, which gets mapped into a set of complex-valued Fourier coefficients. However, we are often concerned with purely real-valued data, such as sound waves or images, whose Fourier transforms we would like to compute. What simplification occurs in the Fourier domain as a consequence of having real-valued, rather than complex-valued, data? [5 marks] 12 Computer Vision Give three examples of problems in computer vision which are formally ill-posed. In each case explain how one or more of Hadamard's criteria for well-posed problems has failed to be satisfied. Illustrate how the addition of ancillary constraints or assumptions, even metaphysical assumptions about how the world behaves, enables one to convert the ill-posed problem into a well-posed problem. Finally, discuss how the use of Bayesian priors can perform this function. [20 marks] 9 [TURN OVER CST.98.8.10 13 Specification and Verification II A simple device CP is informally specified as follows: CP stores values of type . It has two inputs: inp carries values of type and func carries 2-bit words; it has an output line outp carrying the value stored. CP is a state machine whose next state depends on the value input at func: if func=0 the value stored is unchanged if func=1 the value on inp replaces the value stored if func=2 the value stored is transformed by a function f2 : if func=3 the value stored is transformed by a function f3 : Define a predicate CP that formalises this specification in higher order logic. [4 marks] Write down logical models of the following components: a combinational multiplexer that routes one of four -valued inputs to a single output, depending on the value of a 2-bit control input; [3 marks] a unit-delay register that holds values of type . [3 marks] Draw a schematic diagram of an implementation of CP built from these components. [3 marks] Write down a formula that expresses the correctness of your implementation. [4 marks] Discuss briefly how you would go about proving your correctness formula. You need not give a detailed proof, but you should aim to convince the reader that given time you could produce one. [3 marks] 10 CST.98.8.11 14

Multimedia applications may be characterised by their requirement for timely completion of their computation or data processing in order to function usefully. Why are traditional operating systems unable to deliver such guarantees? Comment on the features which an operating system should implement in order to support such applications successfully, considering issues of memory management, device access, and scheduling techniques. [20 marks] 9 Computation Theory What is meant by saying that a model for computation offers unlimited data storage but is restricted to finite logic? [3 marks] How would you record the configuration during computation within such a model? Illustrate your answer by considering both Turing machines and register machines. [5 marks] Suppose you are given a k-symbol Turing machine having searching states. Show how to represent the transition from the configuration at time t to the configuration at time t + 1 by a system of arithmetic equations. Hence show that any Turing machine computation may be simulated by a register machine having a suitable program. [12 marks] 5 [TURN OVER CST.98.3.6 10 Numerical Analysis I Define relative error, machine epsilon (macheps). [2 marks] Consider IEEE single-precision arithmetic. How are the 32 bits arranged in terms of sign, exponent and significand? How is the exponent stored? Explain the terms normalized number, denormal number. What is the hidden bit and how is it used? How are negative numbers stored? What does NaN stand for? Give an example of an operation that yields a NaN value. [6 marks] Given that emax = 127, show the bit pattern representing each of the following numbers. [Draw lines to separate the sign, exponent and significand. You may use "0 . . . 0" to represent long strings of zeros.] 0 1.0 1.0 + macheps 4.0 4.0 + macheps 1.125 2 31 a NaN value [give one example] x, the smallest representable number greater than 216 [9 marks] In the last case, what is (a) the value of the least significant bit in the significand of x, and (b) the relative error if rounding error causes 216 to be stored as x?

t yield unexpected results in languages that have a wide variety of numerical data types. To what extent is it possible to eliminate such problems in future languages? [6 marks] 7 Compiler Construction Explain a possible implementation method for Java-style or ML-style exceptions and handlers. [8 marks] Consider a simple arithmetic expression e of abstract syntax: e ::= x | n | e + e 0 | e e 0 | e e 0 | e/e0 | e where x ranges over a set of (global) variables, addressable by name, and n ranges over integer constants. Write a procedure in pseudo-code or a language of your choice which takes an expression e and prints (one-per-line) stack-machine instructions of the form pushvar x pushnum n add ; pop two items and push their sum sub ; pop two items and push their difference mul ; pop two items and push their product div ; pop two items and push their quotient neg ; replace top item with its negation which, when executed, have the net effect of pushing just the value of e onto the stack. Each line of code emitted should contain a comment giving the number of items on the stack after its execution, thus the first push and the last instruction would both be commented with "1 item".

Describe how a disk-based transaction log might be implemented, and what the atomic operation used in this technique is. [3 marks] (c) The below snippet of C code uses pthreads for concurrent execution. It uses a mutex M and a condition variable C to ensure that the run critical code function only executes when the condition boolean is true. L1: pthread_mutex_lock(&M); L2: run_critical_code (); L3: if (!condition) L4: pthread_cond_wait(&C, &M); L5: if (!condition) L6: pthread_cond_broadcast(&C); L7: pthread_mutex_lock(&M); Unfortunately, there are four bugs in the code that prevent it from working correctly. List each of the four bugs and describe how each bug affects programme execution. Write down a new version of the code snippet with the four bugs corrected.

We will extend our language SLANG and the JARGON virtual machine with data type definitions such as type int_list = Nil | Cons of int * int_list type int_tree = Leaf of int | Node of int * int_tree * int_tree (Note that we will not consider polymorphic types.) We ctions such as let tail (l : int_list) : int_list = match l with | Cons(x, l') -> l' end end let is_nil (l : int_list) : bool = match l with | Nil -> true | l' -> false end end let sum (x : int_tree) : int = match x with | Leaf y -> y | Node(y, t1, t2) -> y + (sum t1) + (sum t2) end end The semantics of the match expression: Match clauses are attempted from first to last. If no match is found then there is a run-time error and the program halts (we don't have exceptions). (a) Ignoring lexing and parsing, what changes to the compiler's front-end would this require? [3 marks] (b) Discuss possible runtime representations of values of types such as int_list and int_tree. [3 marks] [continued . . . ] 4 CST1.2019.4.5 (c) Assuming your runtime representation uses tags, do you need distinct tags for Cons(x, l) and Node(x, t1, t2)? Justify your answer. [4 marks] (d) Suppose that our language allows nested patterns such as match t with | Node(x, Leaf y, t2) -> e1(x, y, t2) | Node(x, t1, Leaf y) -> e2(x, t1, y) | Node(x, Node(y, t1 t2), t3) -> e3(x, y, t1, t2, t3) end but our front-end generates abstract syntax that cannot contain nested patterns. How would you represent the code above in the same language without nested patterns? [4 marks] (e) Carefully describe the code you would generate for the JARGON virtual machine for the body of the function sum defined above. If you need to extend the virtual machine with new instructions, then define their semantics. (You do not need to remember the exact syntax of the JARGON instructions as long as you clearly explain what your code is doing.) [6 marks] 5 (TURN OVER) CST1.2019.4.6 4 Compiler Construction This question explores how exceptions might be added to SLANG and the JARGON virtual machine. We will raise an exception with raise e where e is an expression. We will "trap" an exception with the following expression. try e with f end If e evaluates to a value v, then v is the result of the try-expression. Otherwise, the evaluation of e raises an exception E and the try-expression continues by evaluating the function application f(E). To simplify things we will assume that each f is an identifier. Uncaught exceptions at the top-level will result in a runtime error. (a) Do we need to define a fixed type for exceptions? Justify your answer. [3 marks] (b) What typing rule or rules would you implement for the expression raise e? Justify your answer. [3 marks] (c) A compiler may rewrite expressions in order to optimise generated programs. For example, here are two rewrite rules to simplify conditional expressions: code replacement 1 if true then e1 else e2 e1 2 if false then e1 else e2 e2 For each of the rules below, argue that it is, or is not, a valid optimisation rule. code replacement 1 raise (raise e) raise e 2 e1 + (raise e2) raise e2 3 try (raise e) with f end f(e) 4 try e with (fun x -> raise x) end e [6 marks] (d) Carefully describe the stack-oriented code you would generate for both the raise- and try-expressions. [8 marks] 6 CST1.2019.4.7 5 Further Java A programmer designs a client-server booking system for a meeting room. The role of the server is to distribute bookings between clients when they connect. Clients open a socket connection to the server regularly for a short period. When a client connects, the client first sends to the server an instance of Message which contains any new bookings made by the client; in response, the server sends an instance of Message containing all bookings made by other clients since the client last connected; the server then closes the connection. The key parts of the Message and Booking classes are defined as follows: public class Message implements Serializable { private final String uniqueClientId; private final java.util.List bookings; ... } public class Booking implements Serializable { private final String uniqueClientId; private final java.util.Date startTime; private final java.util.Date endTime; private final String description; ... } (a) Write a Java implementation of the server, using a single thread to serve each client in turn. You may assume the existence of a static method processBookings, which accepts a list of new bookings from a specified client and returns a list of bookings to be sent back to the client. You may assume suitable accessor methods for Message and Booking; you do not need to handle exceptions. [8 marks] (b) The programmer decides to extend the booking system with vector clocks. (i) Write down a suitable data structure for a vector clock in Java. [2 marks] (ii) Describe in words how the system can be modified to incorporate vector clocks and allow clients to compute a partial order of Message objects. Discuss how vector clocks are initialised and updated. [6 marks] (iii) The programmer wants to use vector clocks to determine which booking occurred first, allowing clients to mark any subsequent bookings as in conflict and therefore cancelled. Describe when the vector clock algorithm cannot determine which booking is first, how this is detected, and propose a solution which resolves the ambiguity.

Why is a computer's memory implemented as a hierarchy of memories and yet the programming model represents physical memory as a flat linear address space? [5 marks] (d) What is the difference between a direct-mapped and a set-associate cache, and how do their cache-line replacement policies differ? [5 marks] (e) Contemporary commercial processors use a register file to store intermediate results. Historically accumulators or operand stacks were used instead of a register file. What are the advantages of a register file over an accumulator and an operand stack? [5 marks] 3 (TURN OVER) CST1.2019.5.4 3 Computer Design (a) Describe each of the four models defined by OpenCL's specification. [4 marks] (b) Describe the different types of memory available to OpenCL kernels. [4 marks] (c) Contrast how calls to a kernel, e.g. DAXPY, are invoked and grouped for execution in OpenCL compared with CUDA. [4 marks] (d) Describe, with the aid of a diagram, how a GPU executes data-parallel kernels efficiently, including the two main pieces of hardware support. [4 marks] (e) Describe the trade-offs between using a GPU or a specialised accelerator for tasks containing data-level parallelism. [4 marks] 4 CST1.2019.5.5 4 Computer Networking The TCP transport protocol is an example of an ARQ. (a) Provide a definition of an ARQ. [1 mark] (b) Describe the design and operation of a simple ARQ for a lossy communication channel. [3 marks] (c) When and why does a simple ARQ at the transport layer have a significant negative impact upon application performance? [3 marks] (d) Describe what additions are required to a simple ARQ to support windowing. When and why will an ARQ which supports windowing provide better application performance than a simple ARQ? [5 marks] (e) Describe two situations when the performance of a windowed ARQ is no better than a simple ARQ. [4 marks] (f ) Would the QUIC protocol, when based upon UDP rather than TCP, overcome the two situations you outlined when answering Part (e)? [4 marks] 5 (TURN OVER) 5 Computer Networking (a) You need to urgently deliver 500 TByte of data from Zurich to London. (i) NoWayNet is offering a 10 Gbit/s reliable delivery service between Zurich and London (about 776km). Should you use either NoWayNet, or an overnight package delivery? Why? [2 marks] (ii) A new company, UnlikelyComms, is offering a 400 Gbit/s reliable delivery service between Zurich and London, but it takes a very indirect 2600 km path. Should you use UnlikelyComms? [2 marks] (iii) Following your successful urgent delivery of 500 TBytes of data, this has become an hourly task. Alongside the need to regularly deliver 500 TByte data between Zurich and London, you have an interactive virtual reality system; it requires six displays each needing 50 Gbit/s and an end-to-end latency of less than 5ms. Fortunately, a startup, FlyByNight, boasts an offering with an effective bandwidth of over 16 Tbit/s, using a special transport with no end-to-end latency at all. The downside is it can only transfer data in 500 TByte units, once every 4 minutes. Explain whether FlyByNight is, or is not, suited to your two workloads. [4 marks] (b) Ethernet standards enable 1Gbit/s over 4 pairs of twisted cabling, yet the physical media has a bandwidth much less than 1GHz, e.g., 250MHz is common. (i) Explain how such high data rates are achieved, and [4 marks] (ii) explain how physical media errors are reduced or eliminated. [2 marks] (c) Explain, with the aid of diagrams, how Code-Division Multiple Access permits two or more pairs of nodes to communicate over a common medium (e.g., wireless) simultaneously. [6 marks] 6 CST1.2019.5.7 6 Computer Networking (a) Provide five examples of resource-multiplexing in computer networks. In each case state the layer of the network stack where this takes place, which resource is multiplexed and the multiplexing mechanism. [2 marks each] (b) A relative has contacted you for help; they believe the Internet is broken. The fault turns out to be that a piece of network-protection software had installed a specific IP address entry for an (alternative) default DNS server. (i) What should have provided the correct DNS entry? [1 mark] (ii) By concentrating on how DNS is intended to work, describe why network applications may not work correctly. [3 marks] (iii) How would you diagnose this problem? [2 marks] (c) DNS substitution may also be used maliciously. (i) Outline how spyware might use an (alternative) DNS entry. [2 marks] (ii) Describe a network-centric method for overcoming such treachery. [2 marks] 7 (TURN OVER) CST1.2019.5.8 7 Concurrent and Distributed Systems (a) In the Network Time Protocol (NTP), a client (C) and a server (S) exchange (request, reply) messages to compute corrections to the time at C. Assume the time at S is always correct, and that C is synchronised to S at 13:30:00. (i) Thirty days later the time at S is again 13:30:00 but C now believes the time to be 13:28:30. Define and compute skew and drift for C. [2 marks] (ii) NTP estimates the offset and delay using four timestamps (T0, T1, T2, T3) from a request-reply message exchange. Two such exchanges occur between C and S, producing timestamps (310.000, 400.100, 400.102, 310.202) and (311.000, 401.150, 401.160, 311.410) respectively, denoting all timestamps as seconds since a common fixed point. Show on a diagram the point in the message exchange at which each timestamp T0 . . . T3 is taken. Give definitions for offset and delay, and compute both for each set of timestamps. Which of the two offsets you have computed would you prefer to use to adjust the time at C, and why? [5 marks] (iii) What happens to your estimates of offset and delay if network delays are no longer symmetric?

) Explain three additional checks that a web server may implement to reduce this risk? [6 marks] 8 CST1.2019.4.9 7 Security (a) In a Linux shell session, you can see the following information: $ ls -la drwxr-xr-x 2 root root 4096 Jun 3 13:29 . drwxr-xr-x 25 root root 4096 Jun 3 13:29 .. -rwxr-xr-x 1 root root 4675 Jun 3 13:29 script.pl Consider how you need to change the file access-control information shown above in order to achieve the following additional goals: Only members of the group staff who are not also members of the group interns can execute script.pl. When script.pl is called, it should be able to switch between using the access privileges of the caller and those of the user primary. All members of group staff should be able to read the contents of script.pl. What would "ls -la" output after you have applied these changes? [6 marks] (b) Sending a password over a network connection is vulnerable to replay attacks by eavesdroppers. Briefly describe three other forms of unilateral (or one-pass) authentication suitable for human keyboard entry that reduce that risk with the help of a hardware token, and name one advantage of each. [6 marks] (c) The Windows NT operating-system family offers two variants of many API functions that receive a string: one for strings using ASCII (or one of its 8-bit "code page" extensions) and one for 16-bit Unicode strings. Linux and many Internet protocols instead use an ASCII-compatible encoding of Unicode called UTF-8. (i) Briefly explain how UTF-8 is decoded. [4 marks] (ii) What particular security risk can emerge when UTF-8 is used in a system along with another Unicode encoding, such as the 16-bit wide characters on Windows, and how can this be avoided? [4 marks] 9 (TURN OVER) CST1.2019.4.10 SECTION B 8 Semantics of Programming Languages Consider the following C-like language, tinyC. It has locally-scoped mutable variables, and functions that take a single argument. Its operational semantics is defined as a transition system over configurations he, E, si where E is an environment {x1 7 n1, .. , xj 7 nj }, mapping the variable names currently in scope to their addresses, and s is a store {n1 7 v1, .. , nk 7 vk}, mapping each currently allocated address to either an integer n or undef. In this question n ranges over 0 . . . 2 631. Programs p consist of finite sets of definitions with distinct names.

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. [3 marks] (ii) Provide an implementation of the take/3 predicate. [4 marks] (iii) Give the complete sequence of answers (in the correct order) generated by perm([1,2,3],A). [3 marks] (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. [2 marks] (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. [3 marks]

Write short implementation for each of the following predicates. two arguments can be unified. [1 mark] (ii) fail/0 is never true. [1 mark] (iii) numequal/2 is true if and only if its arguments, interpreted as numerical expressions (assume integer values and no use of division), are numerically equal. For example, numequal(1+3,2+2) is true. [1 mark] (iv) member/2 is true if and only if its first argument is within the list that is its second argument. [1 mark] (b) Given the following code, list all solutions, in order, for the query c(X,Y,Z). a(1). a(2). b(a). c(A,B,C) :- a(A),d(B,C). c(A,B,C) :- b(A),d(B,C). d(B,C) :- a(B),!,a(C). d(B,_) :- b(B). [4 marks] (c) The recursive clause of a bubblesort predicate is reproduced below (assume that append/3 is defined already). Define two different base clauses for this predicate, one of which should use a green cut. When the first argument is unified with a list containing only integers, both of your answers should produce no additional solutions on backtracking. Explain how your complete bubblesort predicate works, including the purpose of the red cut. bubblesort(X,Y) :- append(A,[H1,H2|B],X), H1 > H2, !, append(A,[H2,H1|B],X1), bubblesort(X1,Y). [6 marks] (d) The power set of a set S is the set of all subsets of S. We will represent sets using lists (ignore list order and assume no duplicates). Write a predicate ps(+S,-PS) that unifies PS with the power set of S, and explain how it works. Include the code for all predicates that you use.

A sequential circuit has been built, and it behaves slightly erratically. When switched on it produces on its three output wires one of the following patterns: 000 001 100 110 011 000 010 101 111 010 or The second pattern is not intended to arise. Deduce the circuit details and propose a modification that ensures that in due course the circuit will always settle into the cycle shown in the first pattern.Two gamblers play a game which involves tossing a fair coin. After t2 tosses the first gambler has scored k wins. If there is no record of the sequence of tosses, what probability distribution describes the situation after t1 tosses (t1 < t2)? If the game is tied after eight tosses, show that the probability that it was tied after four is 18 35 .

(a) In image compression we use three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values; (ii) quantising those values; (iii) symbol encoding the resulting values. Explain each mechanism, describe the way in which it helps us to compress the image, and describe how the mechanism is implemented in the baseline JPEG compression method. [10 marks] (b) Describe the limitations of human vision in terms of: (i) spatial resolution, (ii) luminance, (iii) colour, and explain the implications that each of these has on the design of display devices, including numerical estimates of the limits beyond which a human cannot discriminate.

(a) A continuous communication channel adds Gaussian white noise to signals transmitted through it. The ratio of signal power to noise power is 30 decibels, and the frequency bandwidth of this channel is 10 MHz. Roughly what is the information capacity C of this channel, in bits/second? [5 marks] (b) Explain the comb function, comb(t) = X(t), its role in the sampling theorem, its self-Fourier property, and the constraint on the spacing of the comb's tines that is required in both the signal domain and consequently in the Fourier domain in order to reconstruct exactly, from discrete samples, a signal having no frequency components higher than W.

(a) Explain the steps and the complexity of the Hirschberg algorithm and illustrate them with an example. [7 marks] (b) Give one example why the multiple alignment, as implemented in the software Clustal, needs a guide tree. [5 marks] (c) Explain what an amino acid exchange propensity matrix is and how you would construct it. [3 marks] (d) Explain with an example why a compression algorithm is often needed in genome assembly. [5 marks] 3 Computer Systems Modelling Consider a M/M/1 queueing system with an arrival rate > 0 and a service rate > 0 where = / < 1. (a) Derive the distribution for N, the total number of customers present in the queueing system in equilibrium. [6 marks] (b) Suppose that the queueing system is in equilibrium. For each of the following terms define the quantity and determine its value: (i) utilization (ii) throughput (iii) mean number of customers present in the system (iv) mean time spent by a customer in the system [8 marks] (c) Now suppose that the arrival rate and service rate are both scaled by a factor of s > 0. For each of the four quantities in part (b) determine their new values and explain your findings.

Describe the process of specifying a major piece of software: the main documents produced, their immediate purpose and their ongoing role in the software life cycle. Describe the role that formal methods can play at each stage of the software life cycle. Explain any disadvantages of the uses of formal methods that you have discussedProve or disprove each of the following statements, stating clearly any well known results that you use. (a) The set of strings over the alphabet {0, 1} that contain exactly twice as many occurrences of 0 as of 1 is a regular language; (b) Let L be a regular language over an alphabet . Then the language consisting of those u such that there is some v with uv L, is also a regular language; (b) Any finite subset of {a, b} is a regular language; (d) For any regular expressions r and s, the regular expressions (r s ) and (r|s) always denote the same language. [20 marks] 28 Unix Case Study What is an i-node and what information is contained in it? Describe how named files are mapped to i-nodes. How is the information associating disc blocks with i-nodes represented? What restrictions are placed on name to i-node links to simplify file system recovery

(a) In Mini-ML, define the relation of specialisation between (i) type schemes and types, A ( ) 0 [1 mark] (ii) type schemes and type schemes, A ( )A0 ( 0 ) [2 marks] (b) What is meant by the principal type scheme of a closed expression in Mini-ML? [2 marks] (c) State the Hindley-Damas-Milner Theorem for the Mini-ML typeability problem. [2 marks] (d) Define what is meant by a Mini-ML typing problem. Outline a type inference algorithm for Mini-ML that operates on typing problems. You should explain what is a solution and a principal solution for a typing problem, state the properties of the output of the algorithm and explain its overall structure. How does the algorithm make use of fresh type variables and of unification? Illustrate your answer by describing how the algorithm operates on function application expressions.

(a) Describe briefly six factors which might influence or constrain the design of a new processor. [6 marks] (b) The performance of a superscalar processor is often enhanced with hardware to support the following: branch prediction register renaming out-of-order execution the speculative reordering of load instructions strided prefetching (i) Sketch an assembly language program that would benefit from the use of all of these techniques when executed on a superscalar processor. Briefly describe how each of the techniques helps to improve the performance of your program. [10 marks] (ii) Briefly outline two example programs for which the adoption of the techniques listed would not provide a significant performance improvement.

. Write program that insert number from the keyboard, and find out the number is prime or not? Write complete C++ program to ask the user to enter 4 integers. The program must use a function to find the LARGEST integer among them and print it on the screen. Write c++ program to calculate the sum of all the elements in an array. : Write C program to print the Fibonacci series using for loop?

(a) (i) Suppose that FX(x) is a distribution function. Show the inverse transform result, namely that, if U is a random variable uniformly distributed in the interval (0, 1) then X = F 1 X (U) is a random variable with distribution function P(X x) = FX(x). [4 marks] (ii) Discuss the notion of a pseudo-random number generator for uniform random variables. Describe suitable algorithms for generating pseudorandom numbers. [6 marks] (iii) Using the inverse transform result in part (a)(i) derive a method to generate a stream of independent pseudo-random numbers from an exponential distribution with parameter > 0. What are the true mean and variance of these numbers in terms of ? [4 marks] (b) (i) Suppose that you conduct a simulation experiment to estimate the mean, , of a random quantity X from a sample of n values X1, X2, . . . , Xn. How would you estimate ? [2 marks] (ii) Now suppose that your simulation also yields a sample of n values Y1, Y2, . . . , Yn of the random quantity Y where E(Y ) = Y is a known number. How would you use the method of control variates to improve your estimator of ? Your answer should mention all quantities that may need to be estimated and in what way you will improve the estimation of

(a) Why does the formal security definition for collision-resistant hash functions require a key s and a security parameter n, even though most commonly used standard secure hash functions lack such input parameters? [4 marks] (b) If hs : {0, 1} {0, 1} `(n) is a collision-resistant hash function, do the following constructions Hs also provide collision-resistant hash functions? Explain your answers. [2 marks each] (i) Hs(x) = hs(x) k x (i.e. append x) (ii) Hs(x) = hs(x) k LSB(x) (i.e. append least significant bit of x) (iii) Hs(x) = hs(x | 1) (bitwise-or, i.e. set least significant bit of x to 1) (c) Use Euler's theorem to calculate 51 mod 8. [4 marks] (d) The standard Digital Signature Algorithm (DSA) uses a cyclic subgroup G Z p of the integers modulo a prime p, with prime order q, where q divides p 1. (i) Give two advantages of using a multiplicative subgroup of prime order, as opposed to just using Z p , in cryptographic schemes based on the Discrete Logarithm problem. [2 marks] (ii) Why is it possible to choose q substantially smaller than p, and what is an advantage of doing so?

(a) SoC design involves dividing work between hardware and software as well as deciding the number of general-purpose and custom processors and co-processors to be used. What main factors influence these design decisions and the associated manual partition of envisaged workload over these resources? [5 marks] (b) A lossless compression algorithm converts fixed-size, 1 kByte blocks of data to a variable-sized block that is normally shorter. Suggest a suitable signature (argument and return types) for a software function that implements the algorithm. Draw a diagram showing the external wiring to the neighbouring SoC components for an appropriate, high-performance, hardware implementation. State any assumptions that guide your design approach. [6 marks] (c) A synchronous hardware module has separate input and output ports that each convey 32-bit words. Handshaking is required on both ports since it is unpredictable whether the module or its environment are ready to exchange data in either direction at any time. Give a diagram or RTL module definition for such a component and precisely describe the handshaking protocol in words. State the maximum throughput of your protocol. [5 marks] (d) Why might it be useful to have a formal specification of your protocol from part (c) during design and testing? What, if anything, might we infer about the number of words stored inside the module from the protocol? [4 marks] 13 Topical Issues (a) Compare and contrast the Internet of Things (IoT) with the conventional internet. [4 marks] (b) Describe how Bluetooth Low Energy (BLE) was designed to address the following IoT-related issues. Your answers should consider both BLE advertising and data channels. (i) Reduce the overall power consumption of peripherals. [6 marks] (ii) Handle radio channel contention from other IoT devices

We have a basic search problem, consisting of a set S of states, a start state s0, a goal test G(s) that returns True if s S is a goal and False otherwise, and a function exp(s) that returns the set of states obtained by expanding state s. (a) Describe in detail the Graph Search algorithm for solving a problem of this type. How does it differ from the related Tree Search algorithm? [8 marks] (b) Give a detailed description of the Recursive Best First search algorithm, and explain why it might be used in preference to the A? (a.) You have received a shipment of hardware random-number generators, each of which can output one 128-bit random number every 10 milliseconds. You suspect that one of these modules has been tampered with and that it actually produces only 30-bit random numbers internally, which are then converted via a pseudo-random function into the 128-bit values that it outputs. (i) How does this form of tampering reduce the security of a system that uses a generated 128-bit random number as the secret key of a block cipher used to generate message authentication codes? [2 marks] (ii) Suggest a test that has a more than 0.5 success probability of identifying within half an hour that a module has been tampered with in this way. [6 marks] (b) Explain briefly (i) the encryption and decryption steps of Cipher Feedback Mode; [3 marks] (ii) why some operating systems ask the user to press a special key combination (e.g., Alt-Ctrl-Del) before each password login; [3 marks] (iii) how a secure hash function can be used to implement a one-time signature scheme; [3 marks] (iv) what happens if the same private key of the scheme from (iii) is used multiple times, to sign different messages

address all