(a) Consider two clusters A and B each hosting multiple applications. All applications send bursty traffic between A and B over a link E. Under what conditions is circuit switching more efficient to use as opposed to packet switching? (b) Compare the link state and distance-vector protocols in terms of message complexity, processing complexity and robustness. (c) Cambridge University is about to open a new School with three new departments A, B and C. The IPv4 address prefix of the new School is 128.232.1.0/24 and it is expecting each department to have the following number of hosts: Department A: between 40 and 60 hosts Department B: between 100 and 120 hosts Department C: between 20 and 30 hosts (i) The university wishes to allocate a subnet for each department. Give possible IPv4 subnet masks for each new department. (ii) Later, the School opens a fourth department D with 30 hosts. Provide possible IPv4 subnet masks to accommodate all four departments. (iii) Finally, the School opens a fifth department E of similar size to B. Provide possible IPv4 subnet masks to accommodate all five departments

provide answers to all questions

(a) A processor's main memory is usually implemented using DRAM. (i) Describe a typical DRAM cell. (ii) Show, with the aid of a diagram, how DRAM is organised, making reference to devices, ranks, banks and arrays. (iii) Describe the difference between an open-page and closed-page row-buffer policy and the types of access patterns they benefit. (b) The MOSI cache coherence protocol adds a new owned (O) state to the basic MSI protocol.When a cache holding a line in M state snoops a read request from another cache, it transitions to O state and forwards the data to the requestor. Subsequent snoops for read requests are also fulfilled by this owner cache. An owned line is dirty and only one cache can hold a line in O state at any time. (i) Describe the difference between cache coherence and memory consistency. (ii) Draw a state transition diagram for the MOSI protocol, using a new action Forward to indicate data being forwarded from one cache to another. (iii) Draw a table showing how the state of a line in one cache limits the states the same line can have in a different cache.

A company that sells both spreadsheets and word processors has received complaints from users in the banking industry. The users often copy data from spreadsheets into letters offering special finance terms to individual customers. The default behaviour of the word processor "paste" command is simply to insert the numeric value, whereas a special option (in the "paste special . . ." dialog) inserts a recalculating formula. The special option is used so regularly that users have requested an extra item on the pop-up (right click) menu. (a) How would you estimate the increase in operation speed that might result from this change? [6 marks] (b) How would you confirm the actual speed increase after constructing a prototype? [4 marks] (c) The design team suggest an alternative - that the word processor should be enhanced with sufficient calculation functions that a spreadsheet is not needed at all. What factors should be taken into account in order to assess the effect this would have on user tasks? [10 marks] 2 VLSI Design (a) Sketch stick diagrams of memory cells for: (i) read-only memory; [3 marks] (ii) static memory; [3 marks] (iii) dynamic memory using standard CMOS; [3 marks] (iv) dynamic memory for dense layout. [3 marks] (b) Extend your design for parts (ii) and (iii) to accommodate four read ports. What would inhibit such an extension for design (iv)? [6 marks] (c) State two considerations that are becoming increasingly important in memory design as feature sizes decrease.

(a) A team plays several seasons with 20 matches in each season. If the team is at home, the probability of winning is 0.7. The probability of winning away is 0.4. No games are draws. Home and away games usually alternate: ignoring the end of the season, there is a probability of 0.75 that a home game is followed by an away game, and also a probability of 0.75 that an away game is followed by a home game. At the start of the season, there is an equal chance of a home or an away game. Show how this information can be partially modelled as a Hidden Markov Model (HMM), treating home and away as hidden states. Give the parameters of the HMM. (b) What aspect of the scenario described is not correctly covered by the HMM? (c) If the team's results are 'win, lose, win' at the start of the season, what probability estimate for 'home, away, home' is given by this HMM? (d) You are given a complete record of individual games, including a record of the opponents. The win/loss ratio varies depending on the opponent. Explain how you could use such information to derive the parameters of a more complex HMM (treating home and away as hidden states, as before). (e) It is suggested that you could use an HMM to predict the results of next season's games, since it is known who the opponent will be and whether the match will be at home or away. How might you do this? How successful do you think this would be, compared to predicting whether a sequence of matches were home or away based on a sequence of match results?

(a) Given an active high reset signal, how is an asynchronous reset described in SystemVerilog? [2 marks] (b) For each of the following six always_ff blocks, what sequence or error will be produced and why? You should assume clk is a clock and that all registers are reset to zero at the start (as they are for FPGAs). [3 marks each] logic [2:0] rb, rc, rd, re, rf, rg; always @(negedge clk) $display("rb=%d rc=%d rd=%d re=%d rf=%d rg=%d", rb, rc, rd, re, rf, rg); always_ff @(posedge clk) rb <= (rb<6) ? rb+1 : 0; always_ff @(posedge clk) begin if(rc>=6) rc <= 0; rc <= rc+1; end always_ff @(posedge clk) begin rd <= rd+1; if(rd>=6) rd <= 0; end always_ff @(posedge clk) begin if(re>=6) re = 0; re = re+1; end always_ff @(posedge clk) if(rf<6) rf <= rf-14; else rf <= 0; always_ff @(posedge clk) casex(rg) 3'b0??: rg<=rg+1; 3'b11?: rg<=0; endcase .

: Write program that first gets a list of six integers from input. The first five values are the integer list. The last value is the upper threshold. Then output all integers less than or equal to the threshold value. Write program that first gets a list of integers from input. The input begins with an integer indicating the number of integers that follow. Then, get the last value from the input, and output all integers less than or equal to that value. Assume that the list will always contain less than 20 integers. Write program that first gets a list of integers from input. The input begins with an integer indicating the number of integers that follow. Then, get the last value from the input, and output all integers less than or equal to that value.

We wish to model the unobservable state of an environment using a sequence S0 S1 S2 of sets of random variables (RVs) where at time i we are in state Si and observe a set of RVs Ei . The distributions of the RVs do not change over time, and observations depend only on the current state. (a) Define a Markov process, the transition model and the sensor model within this context. [3 marks] (b) Assuming that evidence E1:t = e1:t = (e1, e2, . . . , et) has been observed define the tasks of filtering, prediction and smoothing. [3 marks] (c) Derive a recursive estimation algorithm for performing filtering by combining the evidence et obtained at time t with the result of filtering at time t 1. [8 marks] (d) How does a hidden Markov model differ from the setup described? [1 mark] (e) Show how for the case of a hidden Markov model your filtering algorithm can be expressed in terms only of matrix operations. [5 marks] 9 Bioinformatics (a) Present the aim of phylogeny algorithms: (i) Describe the main differences between Parsimony, Distance and Likelihood-based algorithms. [5 marks] (ii) Describe the input and the output of a distance-based algorithm. [5 marks] (iii) Discuss the complexity of the Neighbour-Joining algorithm. [5 marks] (b) Describe with one example the Needleman-Wunsch algorithm

Give a polymorphic lambda calculus (PLC) type list that contains a single free type variable and which corresponds to the ML datatype of polymorphic lists: datatype 'a list = Nil | Cons of 'a * ('a list) [2 marks] Give PLC expressions Nil, Cons and iter of appropriate types that encode the ML constructors Nil and Cons and the ML function iter given by fun iter x f Nil = x | iter x f (Cons(h, t)) = f h (iter x f t) You should prove the PLC typings you claim for these expressions. [13 marks] Show that iter has -conversion properties corresponding to the above declaration of the ML function iter.

(a) Explain the term positive semi-definite. If A is a real square matrix show that AT A is symmetric and positive semi-definite. [3 marks] (b) How is the l2 norm of A defined? State Schwarz's inequality for the product Ax. [2 marks] (c) Describe briefly the properties of the matrices U, W, V in the singular value decomposition A = UWVT . [3 marks] (d) Let x be an approximate solution of Ax = b, and write r = bAx, e = xx. Derive a computable estimate of the relative error kek/kxk in the approximate solution, and show how this may be used with the l2 norm. [8 marks] (e) Suppose A is a 7 7 matrix whose singular values are 102 , 104 , 1010 , 1016, 1022, 1029, 1056. Construct the matrix W+ that you would use (i) if machine epsilon ' 1015, and (ii) if machine epsilon ' 1030 . [4 marks] 13 Specification and Verification II (a) Discuss the challenge of modelling transistors in a way that is both tractable for formal verification and accurate enough to be useful. [5 marks] (b) Discuss the accuracy of the simple switch model of transistors and discuss how the model can be improved. [5 marks] (c) Outline how transistor circuits that use precharging can be formally modelled in higher order logic. Briefly discuss potential inaccuracies of such models. [5 marks] (d) Describe how to specify that a bit-level circuit with 4-bit inputs a and b and an 8-bit output prod performs multiplication.

(a) Describe two drawbacks of layering. Provide an example for each. (b) (i) Explain the single-bit parity error-detection code using a single byte of data. How many bit errors can this code detect? (ii) Based on the single-bit parity error-detection code devise a new code to detect and correct a single 1-bit error in 4 bytes of data. How many parity bits do you require? You may assume that parity bits are error-free. (c) Consider a wireless network. For each of the following cases, state whether the packet transmission would be successful; assume no collision avoidance. Explain your answers. (i) Nodes A and B are in range of each other; no other node is within range. Node A sends a packet to B. (ii) Nodes A and B are in range of each other; nodes B and C are in range of each other; A and C are not in range of each other. Both A and C send a packet to B simultaneously. (iii) Nodes A and B are in range of each other; nodes B and C are in range of each other; A and C are not in range of each other. C is transmitting and A wants to send a packet to B. (iv) Nodes A and B are in range of each other; nodes B and C are in range of each other; A and C are not in range of each other. A is transmitting and B wants to send a packet to C.

(a) Summarise the basic principles behind strictness analysis including: what language paradigm it can be applied to, the representation of compile-time values expressing strictness, how these may be calculated and how the results of such calculations can be used to optimise programs. [8 marks] (b) A program contains the following user function definitions. Give corresponding strictness functions assuming that if-then-else takes an integer as its first argument. (i) fun f(x) = 42 [1 mark] (ii) fun g(x) = g(x+1) [1 mark] (iii) fun h(y,z) = if f(7) then y else z [2 marks] (iv) fun k(x,y,z) = pif(x,y,z) where pif(e, e0 , e00) is a primitive which evaluates its three arguments in parallel, returning e 0 if e evaluates to a non-zero integer, returning e 00 if e evaluates to zero and also returning e 0 if e 0 and e 00 evaluate to the same integer even if e is still being evaluated. [4 marks] (c) "Any Boolean expression be containing variables {x1, . . . , xk} but not containing negation can be expressed as the strictness function for a userdefined function fun u(x1, . . . , xk) = e." Argue that this statement is true, showing how to construct some such e from a given be. [Hint: you may assume be has been written in DNF form (v11 v1m1 ) (vn1 vnmn ) where vij are members of {x1, . . . , xk}.]

(a) Compare and contrast the request routing mechanisms of Gnutella and Pastry. [10 marks] (b) It has been said: "Unstructured peer-to-peer systems are better than structured peer-to-peer systems because they implement searching and complex queries." Describe how a structured system might be able to implement search. 6 Advanced Graphics (a) Compare and contrast B-spline and subdivision representations of curves. (b) Explain how B-spline basis functions are derived from the knot vector. (c) Derive the quadratic uniform B-spline basis function (use the knot vector [0, 1, 2, 3]). (d) Describe an algorithm to give the first intersection point of a ray with a closed cylinder of finite length aligned along the z-axis