Computer Systems Modelling Consider a birth death model with birth rates n in states n = 0, 1, . . . and death rates n in states n = 1, 2, . . .. (a) State the detailed balance conditions for the equilibrium probability pn of being in state n, for n = 0, 1, . . . and explain how they are derived. [2 marks] (b) Using the detailed balance conditions derive an expression pn and state any condition needed to ensure that the equilibrium distribution exists. [4 marks] (c) Now consider the M/M/1 queue with arrival rate and service rate and explain how it can be modelled as a birth death model. [2 marks] (d) For the M/M/1 queue derive the form of pn, the equilibrium distribution of the number of customers present, and state any conditions needed to ensure the existence of the equilibrium distribution. Derive the mean value of the equilibrium distribution. [4 marks] (e) Now consider a M/M/1 model with the modification that customers waiting in the queue are impatient and will only wait for an exponentially distributed amount of time with rate parameter before departing the queue without service. (i) Explain how you could modify your birth death model in this situation and write an expression for pn. [4 marks] (ii) Let be the probability that a customer receives service and derive an expression for using Little's law applied to the server. You may leave your expression in terms of the value p0. [4 marks] 3 (TURN OVER) CST.2015.9.4 3 Computer Vision (a) In human vision, photoreceptors (cones) responsible for colour are numerous only near the fovea, mainly in the central 10 degrees. High spatial resolution likewise exists only there. So then why does the visual world appear to contain colour information everywhere in the field of view? Why does it also seem to have uniform spatial resolution? Why does the world appear stable despite all our eye movements? Discuss the implications for computer vision principles that might be drawn from these observations. [5 marks] (b) Explain why such a tiny number of 2D Gabor wavelets as shown in this sequence are so efficient at representing faces, and why such wavelet-based encodings are able to deliver impressive accuracy performance in "appearance-based" algorithms for face recognition. Number of Wavelets 16 52 116 216 original [5 marks] (c) Explain the "receptive field" concept in vision, and what is accomplished by the lateral signal flows within both of the plexiform layers of the mammalian retina, in terms of spatial and temporal image processing and coding

Consider a binary symmetric channel with error probability p that any bit may be flipped. Two possible error-correcting coding schemes are available. (i) Without any error-correcting coding scheme in place, state all the conditions that would maximise the channel capacity. Include conditions on the error probability p and also on the probability distribution of the binary source input symbols. [2 marks] (ii) If a (7/4) Hamming code is used to deliver error correction for up to one flipped bit in any block of seven bits, provide an expression for the residual error probability Pe that such a scheme would fail. [2 marks] (iii) If instead repetition were used to try to achieve error correction by repeating every message an odd number of times N = 2m + 1, for a positive integer m followed by majority voting, provide an expression for the residual error probability Pe that the repetition scheme would fail. [2 marks] (c) Gabor wavelets are an important class of complex-valued functions for encoding information with maximal resolution simultaneously in the frequency domain and the signal domain. Using an expression for their functional form, explain: (i) their spiral helical trajectory as phasors, shown here with projections of their real and imaginary parts; (ii) the Uncertainty Principle under which they are optimal

(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 2 CST1.2018.5.3 2 Computer Design The RISC-V base ISA instruction formats are reproduced below. Each immediate subfield is labelled with the bit position (imm[x ]) in the immediate value being produced, rather than the bit position within the instruction's immediate field as is usually done. 31 25 24 20 19 15 14 12 11 7 6 0 funct7 rs2 rs1 funct3 rd opcode R-type imm[11:0] rs1 funct3 rd opcode I-type imm[11:5] rs2 rs1 funct3 imm[4:0] opcode S-type imm[31:12] rd opcode U-type (a) In assembler, what is an immediate? [2 marks] (b) Give examples of load, branch and arithmetic instructions in assembler that use an immediate. Note that it is not critical for the RISC-V assembler syntax to be perfect, but for each instruction please explain your answer. [3 marks] (c) For a pipelined processor implementation, why is it an acceptable design choice for the bit position of immediates to vary between instruction formats? [2 marks] (d) For a pipelined processor implementation, why is it advantageous to have the source registers in the same bit position independent of the instruction format? [2 marks] (e) Why can there be many more register-to-register instructions with no immediates than instructions with immediates? [3 marks] (f ) For a pipelined implementation of the RISC-V ISA, the sequential instruction execution model needs to be preserved. Cases where the pipelined implementation might deviate from this sequential model are often referred to as hazards. For a simple pipelined implementation, what hazards might exist and how might they be resolved? [8 marks] 3 (TURN OVER) CST1.2018.5.4 3 Computer Design (a) A processor's main memory is usually implemented using DRAM. (i) Describe a typical DRAM cell. [2 marks] (ii) Show, with the aid of a diagram, how DRAM is organised, making reference to devices, ranks, banks and arrays. [4 marks] (iii) Describe the difference between an open-page and closed-page row-buffer policy and the types of access patterns they benefit. [2 marks] (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. [2 marks] (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. [6 marks] (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. [2 marks] (iv) Give two benefits of adding this extra owned state to the basic MSI protocol. [2 marks] 4 CST1.2018.5.5 4 Computer Networking (a) Describe two drawbacks of layering. Provide an example for each. [4 marks] (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. [8 marks] (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. [8 marks] 5 (TURN OVER) CST1.2018.5.6 5 Computer Networking (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? [2 marks] (b) Compare the link state and distance-vector protocols in terms of message complexity, processing complexity and robustness. [6 marks] (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. [3 marks] (ii) Later, the School opens a fourth department D with 30 hosts. Provide possible IPv4 subnet masks to accommodate all four departments. [2 marks] (iii) Finally, the School opens a fifth department E of similar size to B. Provide possible IPv4 subnet masks to accommodate all five departments. [4 marks] (iv) Are there any practical problems with your answer to Part (c)(iii)? Briefly discuss an alternative solution to accommodate all five departments. [3 marks] 6 CST1.2018.5.7 6 Computer Networking (a) Briefly describe the main differences and similarities between routers and switches. [4 marks] (b) Consider the network shown in the figure below with four nodes. Cost links are shown in the diagram. Give the distance-vector routing tables for node C in the following two consecutive steps. (i) Step 0: C knows the distances to its immediate neighbours and [1 mark] (ii) Step 1: information from step 0 is exchanged as per the distance-vector algorithm. [3 marks] C B E D 1 2 2 5 2 (c) (i) What is the problem that the Karn-Partridge algorithm aims to solve? [2 marks] (ii) Karn and Partridge proposed the use of exponential backoff in the TCP timeout value. Why is it that an exponential increase in the timeout value is more efficient than a linear increase for example? [2 marks] (d) What is the difference between congestion control and flow control in TCP? [2 marks] (e) Assume that three TCP flows f1, f2, f3, share a single link. The bandwidth of the link is 200 Mbps. The desired bandwidth of each flow is: f1 60 Mbps, f2 80 Mbps, and f3 100 Mbps. (i) What would be the max-min bandwidth allocation of the flows? [2 marks] (ii) Propose a way to "cheat" max-min fairness so that f3 increases its allocated bandwidth as computed in Part (e)(i).. Consider the following processes linked by PCQs forwarding console input to the application, and output back to the console: Console SSH Client SSH Server Application PCQ4 PCQ5 PCQ6 PCQ1 PCQ2 PCQ3 Each queue has a fixed limit of N ( 1) bytes. A PCQ is readable if there is a non-zero number of bytes in its buffer. A PCQ is writable if there are fewer than N bytes of data in its buffer. Four (simplified) I/O system calls are used: b = readbyte(pcq) Read one byte of data from pcq; blocks if pcq is empty. writebyte(pcq, b) Writes one byte of data to pcq; blocks if pcq is full. waitread(pcq1, ..) Block until at least one argument is readable. pollread(pcq) Returns true if pcq is readable. With crypto omitted, SSH client and server workloops are implemented as: 1: while (1) { 2: waitread(input1, input2); // Wait for input on either PCQ 3: if (pollread(input1)) { 4: b = readbyte(input1); 5: writebyte(output2, b); 6: } 7: if (pollread(input2)) { 8: b = readbyte(input2); 9: writebyte(output1, b); 10: } (a) What is the maximum amount of data buffered across all PCQs? [2 marks] (b) Applications often echo user keypresses, printing input characters as they process them. If the user hits the 'A' key, at most how many times will PCQ semaphores be signaled before the character is printed on the console? [2 marks] (c) The system operator sets N to 1 and pastes a long list of commands into the console. Part way through, the SSH Server and Application processes hang. Succinctly explain what happened, describing PCQ3 and PCQ6 starting states, initial line number for the SSH Server, and event sequence. [6 marks] (d) Explain why, on a busy system, key press echoes might be delayed when a high-priority user interacts with a low-priority application. Propose a solution, describing how each of the above system calls should be changed, and any additional state required. Describe limitations that might apply. [10 marks] 8 CST1.2018.5.9 8 Concurrent and Distributed Systems The Bully Algorithm allows a set of nodes to elect a unique leader in the presence of node failures. For the purposes of this question, assume that: the set of nodes is known in advance by all nodes; each process knows its own identifier; processes fail and restart cleanly; node failure can be reliably detected; and message delivery is reliable unless the destination node has failed. Our network contains eight nodes (1-8), which are connected via three switches (A-C): Link X Link Y Node 1 Switch A Switch B Switch C Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 (a) In the absence of node or switch failures, which node will be elected leader using the Bully Algorithm? [1 mark] (b) A new Node 9 is added to the network, attached to Switch C. Which node will be elected leader using the Bully Algorithm? [1 mark] (c) If there is a network partition between Switches B and C, what node will be elected leader using the Bully Algorithm? [2 marks] (d) To address the concern about network partition, the authors of a distributed system introduce a majority rule: for a node to declare itself leader, it must receive OK messages from a majority of nodes (including itself). Which combinations of links can fail while still permitting a successful election, and, for each of those combinations, which node is elected leader? [4 marks] (e) One key metric used in evaluating distributed algorithms is the number of messages generated. What is the worst-case cost (using O-notation) in messages with n nodes participating in the Bully Algorithm? Explain why this is the case. [2 marks] (f ) The Bully Algorithm provides a strong invariant that a node can identify that it is the unique leader in a distributed system. However, that leadership status can be preempted (revoked) without node failure. Explain how this may occur. [4 marks] (g) Describe how a distributed application can utilise elected leadership status to safely allocate unique transaction IDs. Explain why this works, considering in particular: (1) the steady state; (2) leader change due to leader crash; and (3) leader change due to leadership revocation.

(a) Write down simplified sum of products (SOP) and product of sums (POS) expressions for the following Boolean functions: (i) X = A B C [3 marks] (ii) Y = (A + B + C).(A + D).(A + C) [3 marks] (b) Using a four variable Karnaugh map, fill it with 1s and 0s to find a function that illustrates each of the following situations. Write down the number of terms and the number of literals for each situation. (i) The minimised SOP and POS forms have the same number of terms and literals. [3 marks] (ii) The minimised POS form has fewer terms and literals than the minimised SOP form. [3 marks] (c) For the following Boolean function, F = A.B.C + A.C.D + A.C.D + B.C.D + B.C.D show how it may be implemented using: (i) one 16:1 multiplexor (ii) one 8:1 multiplexor and one or more NOT gates [8 marks] 2 CST.2015.2.3 2 Digital Electronics (a) Draw a diagram showing the structure of an n-channel MOSFET and describe how the Drain to Source current can be controlled. [4 marks] (b) Draw the circuit diagram of a NOT gate that comprises an n-channel MOSFET and a resistor R. [2 marks] (c) For the NOT gate in part (b), plot the relationship between the input voltage, Vin, and the output voltage, Vout . The power supply voltage, VDD = 10 V, R = 500 , and the MOSFET has the characteristics given in the following figure. [6 marks] IDS (mA) 24 20 16 12 8 4 0 4 6 8 10 12 VDS (V) VGS=3V VGS=4V VGS=5V VGS=6V VGS=7V VGS=8V VGS=0V 2 (d) For the NOT gate in part (c), calculate the power dissipated by resistor R when Vin = 8 V. [3 marks] (e) (i) Describe how the power dissipated by resistor R can be reduced. State any potential problems with your proposed solution. [3 marks] (ii) Present a modified circuit for a NOT gate that eliminates the problem of static power dissipation in resistor R. [2 marks] 3 (TURN OVER) CST.2015.2.4 SECTION B 3 Operating Systems (a) What is an access control list? [4 marks] (b) What is a capability in the context of access control? [4 marks] (c) How is file access control in Unix implemented, and what simplifications are made over one of the general mechanisms you have described above? [6 marks] (d) What is the principle of minimum privilege and which approach, access control lists or capabilities, lends itself better to supporting a minimum privilege regime? [6 marks] 4 Operating Systems (a) What is a page fault? [2 marks] (b) What is a segment fault? What might be a sensible response to a segment fault on a stack segment? [2 marks] (c) Describe the actions that follow after a page fault occurs. You should include those performed in hardware prior to a handler being started, and those that are taken within the handler. Your answer should include how segment faults might be detected and handled. [8 marks] (d) What is page thrashing and how might it be avoided? [4 marks] (e) Why is handling a page fault more complex than handling an interrupt or software trap?This question is concerned with the design of the embedded software in a device for switching audio and video streams in a lecture theatre. Correct operation of the overall system involves complex timing dependencies. For example, in this (fictional) system, the video projectors operate most reliably if the input signal is already connected when they power up, whereas the audio amplifier should only be powered up when there is no input signal present. (a) Create outline sketches of two different UML diagrams that would be most useful in defining and refining the key design elements of this system as described above. [8 marks] (b) Describe a formal specification approach that could be used to verify that individual components of the design, when combined, will exhibit the overall properties required. [6 marks] (c) If it becomes necessary to replace a functional component after implementation of the system is complete, describe the approach that could be taken at different points in the resulting upgrade project to ensure that the modified system continues to exhibit the desired properties. [6 marks] 5 (TURN OVER) CST.2015.2.6 6 Software and Interface Design This question is concerned with the user interface of a system for switching audio and video streams in a lecture theatre. This system should be usable by the following people: lecture theatre technical support staff who define standard configurations; regular lecturers who may personalise these configurations; and also visiting lecturers who might only use the system once. (a) Create outline sketches of two different UML diagrams that would be most useful in defining and refining the key design elements of this system as described above. [8 marks] (b) Describe an interaction design approach that can be used to determine whether the proposed user interface will exhibit the overall usability properties required.

We consider the Steiner Tree Problem defined as follows. We are given an undirected, connected graph G = (V, E) with a non-negative cost-function c : E R+. Further, we are given a set S V of terminals. The goal is to find a minimum-cost subgraph of G that connects all terminals, where the cost of a subgraph is the sum of the costs of its edges. Consider the following algorithm: Let H = (V, E0 ) be the metric completion of G, where E 0 = {{u, v}: u, v V } and c({u, v}) is the cost of the shortest path from u to v in G. Compute a Minimum Spanning Tree T on the subgraph H[S] induced by the set of terminals S. Replace every edge {u, v} in T by the edges of a shortest path from u to v in G, and return the solution. (i) Prove an upper bound of 2(1 1 |S| ) on the approximation ratio of this algorithm. [Hint: You can use an approach similar to the analysis of Approx-TSPTour.] [6 marks] (ii) Construct an example which provides a matching lower bound on the approximation ratio. [3 marks] 4 CST.2015.7.5 3 Bioinformatics (a) Compute the global alignment and the best score of the following sequences CGTGAA, GACTTAC with the following parameters: match score = +5, mismatch score = 3, gap penalty = 4. [4 marks] (b) If the sequences have different base composition or length, what parameter values would you choose in order to determine multiple alignment of the sequences? Justify your answer. [4 marks] (c) Discuss the main features of the Burrows-Wheeler transform (BWT) using the following example: T = GATTACA$. Also explain the reversibility of BWT. (d) Discuss the use of clustering in the analysis of gene expression microarray data. [4 marks] (e) Discuss the UPGMA algorithm as applied to the following distance matrix of the species A, B, C and D. species A B C B 2 C 4 4 D 6 6 6 [4 marks] 4 Business Studies (a) Explain the concept of Net Present Value (NPV) and include a description of how it is calculated. [5 marks] (b) You are asked to help prepare a bid, under the Private Finance Initiative (PFI) to develop, install and maintain for 4 years, a patient information system for a hospital. The hospital Trust will pay the bid amount in 5 equal annual payments at the beginning of each year. Your development team estimates development and installation will cost 1M and maintenance 100k per annum. Which of the following bids: 1500k, 1600k or 1700k should your team submit, assuming a discount rate of 10% per annum? Show your working. [10 marks] (c) Draw up a cash flow for this project. How much funding is needed assuming a loan interest rate of 10% per annum?