Computer Design (a) For a MIPS-32 processor executing a jump to subroutine, how are state and control passed between the function and the caller? Indicate what state is passed, but details of particular register numbers are not required. [5 marks] (b) On the MIPS-32 processor the flow of control can be changed using branch or jump instructions, or by three other mechanisms. What are the three other mechanisms for changing the flow of control and what are they used for? [6 marks] ( [5 marks] (d) Some instruction sets make all instructions conditional (e.g. the ARM) or have conditional move instructions (e.g. IA32). How can thelse conditional instructions be used to avoid control hazards? [4 marks] 4 CST.2009.5.5 5 Concurrent Systems and Applications (a) Reflection. (i) Give Java code fragments demonstrating two different ways of obtaining a Class object that describes an array of java.lang.Strings. [2 marks] (ii) Given an object x, write a Java expression that uses reflection to create a new object of the same datatype as x. [2 marks] (iii) The clone() method creates an exact copy of an object, including all of its fields. Briefly describe how you might implement this functionality using reflection, ignoring inherited fields. Assume that the object is not an array, has a zero-argument constructor, and contains only primitive fields. (You need not give code for an actual complete implementation.) [4 marks] (b) Generics. (i) Suppose a class B is a subclass of A. Is the class Set a subclass of Set? Explain why or why not, with regard to type safety. [2 marks] (ii) The default clone method returns an Object that must be cast to the correct type. Using generics, give a declaration of a static myclone method that takes a single argument of any type and returns an object of the same type. [2 marks] (iii) The Contraster interface is used to compare two objects. Its declaration is: interface Contraster { boolean greaterThan(T obj1, T obj2); } Suppose we want to declare a class SortedList whose constructor takes a single Contraster argument that will be used to compare its elements. Give a declaration for the constructor that permits the choice of contraster implementation to be as general as possible, and explain your reasoning. [4 marks] (c) Reference objects. The get() method of the PhantomReference class always returns null. Why is this so, and why must a PhantomReference always be used together with a ReferenceQueue? [4 marks] 5 (TURN OVER) CST.2009.5.6 6 Concurrent Systems and Applications (a) The following method is intended to return unique integer values to callers: volatile int x = 0; int getNext() { x = x + 1; return x; } (i) Two threads call getNext concurrently on the same object. Explain how both threads can receive the result 1. [1 mark] (ii) Explain the semantics of the synchronized keyword in Java, and illustrate this by correcting getNext (you may ignore the possibility of integer overflow). [6 marks] (iii) Explain the meaning of the volatile modifier. Explain whether or not you need to use it with your new implementation of getNext. [2 marks] (b) The following method is intended to implement a barrier for synchronization between four threads. The first three threads to call the barrier method are meant to block. These threads are all unblocked when the fourth call is made. int barrierCount = 0; void synchronized barrier() throws InterruptedException { barrierCount ++; if (barrierCount < 4) { wait(); } else { notifyAll(); } } (i) A programmer finds that some threads return early, although there have been fewer than four calls to barrier. How can this happen? [2 marks] (ii) Rewrite barrier so that threads wait correctly. [2 marks] (iii) Explain whether or not it would be correct to use notify in place of notifyAll in your solution. [2 marks] (iv) If a thread is interrupted while waiting within barrier then the call to wait will fail with InterruptedException. Rewrite barrier so that, if one thread is interrupted when using a barrier, then any future (or concurrent) calls to that barrier will also fail with InterruptedException.

1 Distributed Systems For a large-scale distributed system or application: (a) Describe alternative approaches to creating unique names. Include a discussion of the information conveyed by a name. [5 marks] (b) Discuss name to location binding under the headings (i) availability of the binding service [5 marks] (ii) consistency of the naming data [5 marks] (iii) mobility of named objects [5 marks] 1 [TURN OVER CST.98.12.2 2 Computer Design Early computers (and early microprocessors) were accumulator machines. RISC computers replaced the accumulator with a register file. (a) What is a register file and why is it preferable to an accumulator? Illustrate your answer by writing a loop to calculate factorial of 10 for an accumulator and a RISC processor (you may invent instruction sets and assume that a multiply instruction is available). [12 marks] (b) Why is the Intel x86 processor family often referred to as being an extended accumulator machine? [4 marks] (c) The Intel x86 LOOP instruction decrements the CX register and, if the result is not zero, jumps to a given label. Why is a compiler likely to find it hard to exploit this instruction, especially for nested loops? [4 marks] 3 Digital Communication I How can packet loss occur in a network? [5 marks] Outline a way in which packet loss can be reduced. Can it be eliminated completely? [5 marks] How does an ARQ system deal with packet loss? [5 marks] "An ARQ implementation should keep as much data in transit as the receiver is willing to receive." Discuss. [5 marks] 2 CST.98.12.3 4 Computer Graphics and Image Processing Describe an algorithm for clipping a line against a rectangle. [9 marks] Show that it works using the above three examples. [3 marks] x y 1 1 2 2 B(0,0) A(0,1) B'(3,2) A' 30 The above diagram shows a complicated 2D transformation applied to a unit square. The overall transformation can be described in terms of a number of simpler transformations. Describe each of these simple transformations and give a matrix representation of each using homogeneous coordinates. [6 marks] Use the matrices from the previous part to find the (x, y) coordinates of point A0 , the image of point A under the overall transformation. [2 marks] 3 [TURN OVER CST.98.12.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? [5 marks] Task 1 3 days Task 2 10 days Task 3 5 days Task 4 5 days Task 5 7 days Task 6 5 days Task 10 5 days Task 7 5 days Task 8 7 days Task 9 5 days Task 11 5 days Task 12 25 days Analysis Code Test Analysis 2 Code 2 Test 2 Integrate Specify final tests Code test harness Test the test harness Final tests Management 4 CST.98.12.5 6 Introduction to Security Some banks issue their Automatic Teller Machine (ATM) card customers with a randomly selected personal indentification number (PIN). Others issue their customers with an initial PIN only, and let the customers choose their own PIN the first time they use the card in an ATM. Describe the advantages and disadvantages of these approaches. [5 marks]write good project work and guidance on any of the following topics

Advanced Algorithms Advanced Computer Architecture Algorithms Algorithms 1 Algorithms 2 Artificial Intelligence Bioinformatics Business Studies Comparative Architectures Compiler Construction Complexity Theory Computation Theory Computer Design Computer Networking Computer Vision Concepts in Programming Languages Concurrent and Distributed Systems Cryptography Data Science Databases Denotational Semantics Digital Electronics Digital Signal Processing Discrete Mathematics E-Commerce Economics, Law and Ethics Formal Models of Language Foundations of Computer Science Foundations of Data Science Further Graphics Further HCI Further Human-Computer Interaction Further Java Hoare Logic and Model Checking Information Theory Interaction Design Introduction to Graphics Introduction to Probability Logic and Proof Machine Learning and Bayesian Inference Machine Learning and Real-world Data Mobile and Sensor Systems Numerical Analysis Object-Oriented Programming Operating Systems Optimising Compilers Principles of Communications Programming in C Programming in C and C++ Prolog Quantum Computing Randomised Algorithms Security Semantics of Programming Languages Software and Security Engineering

Again, some banks compute the customer PIN by encrypting the account number using DES and a key known only to their central systems and ATMs, taking the first four hex digits of the result, replacing the digits A, . . . , F with 0, . . . , 5 respectively, and finally, if the first digit of the result is 0, replacing it with a 1. What is the probability that a criminal can get the PIN right given three guesses? [5 marks] Yet other banks have used DES, and a key known only to their central systems and ATMs, to encrypt the PIN (whether randomly generated or customer selected); they then write the result on the magnetic strip on the customer's card, so that the ATM can verify it without reference to the central system. Describe the disadvantages of this arrangement. [5 marks] In order to prevent attacks based on manipulating magnetic strips, banks in some countries have moved to using smart cards. What effect would you expect such a move to have on the incidence of card-based fraud?