answer all questions promptly

What is the maximum segment length of a 100Base-FX netdwork,Thelast character('X', etc) refers to the line code method used. Line code is a pattern of voltage, current or photons used to represent the digital data transmitted on the transmission line.Fast Ethernetcable is sometimes referred to as100BaseXwhere X can be replaced by two variants i.e. FX and TX.In most of the Fast Ethernet applications, theindividual devicesare connected bytwisted-pair copper wiresi.e.100BaseTX(maximum segment length is only 100 meters) and thee optical fibers are used fortransmission over longer distances(as maximum segment length is 2f000 meters of 100baseFX). So,100baseTX to 100Base FXconvertor is required for sending the signal from the sender end over the optical fiber. Similarly, at the receiver end,100baseFX to 100Base TXis required. A combinational logic circuit takes a 4-bit unsigned binary integer number at its inputs labelled D3 , D2 , D1 and D0 , where D3 is the most significant bit. For decimal input 1, 2, 3, 5, 7, 11 and 13, the output S is to be at logic 1, and it is to be at logic 0 otherwise. (i) Write down the truth table for the required combinational logic function. (ii) Using a Karnaugh map, determine the simplified Boolean expression for the output S in terms of the inputs D3 to D0 in a minimum sum-of-products form. (iii) Describe what is meant by an essential term in a Karnaugh map. Write down the essential terms for the Karnaugh map in (ii). (iv) Using a Karnaugh map, this time determine the required simplified Boolean expression for the output S in a minimum product-of-sums form. [10 marks] (b) Provide a circuit diagram which implements the following Boolean function using only NAND gates F = (A + D).(B + C + D).(A + B + C) that has the don't care states: A.B.C.D, A.B.C.D, A.B.C.D and A.B.C.D [4 marks] ( (a) Show how two NOR gates may be connected to form an RS latch. Describe its operation and give a table relating its inputs to its outputs. How could you use this circuit to eliminate the effect of contact bounce in a single pole double throw switch supplying an input to a digital logic circuit? [6 marks] (b) The state sequence for a particular 4-bit binary up-counter is as follows: Show how four negative edge triggered T-type flip-flops (FFs) with outputs labelled QA , QB , QC and QD can be used to implement a ripple counter having the specified state sequence. Show any combinational logic necessary assuming that the FFs have asynchronous reset inputs available. [4 marks] (c) Using the principles of synchronous design, determine the next state combinational logic expressions required to implement a counter having the state sequence specified in part (b ). Assume that D-type FFs are to be used and that unused states do not occur. [4 marks] (d) Explain carefully what happens if the counter in (c ) starts in state 1 1 1 0 . In general, how can start-up problems be overcome in the design of synchronous state machines? [4 marks] (e) What are the advantages and disadvantages of the synchronous design in part (c ) compared with the alternative design in part (b )? [2 marks]

3 (TURN OVER) CST.2014.2.4 SECTION B 3 Operating Systems One goal of a multiuser operating system is to protect each user's information and activity from damage caused by accidental or deliberate actions of other users of the system. (a) Describe a mechanism that operating systems use to reduce the opportunity for a user process to prevent another user's process from making progress. In your description include any particular hardware features that are relied upon. [3 marks] (b) Describe two alternative mechanisms that operating systems could use to reduce the opportunity for a user process to access or corrupt the information being used by another user's process. In your descriptions include any particular hardware features that are relied upon. [6 marks] (c) Describe how an operating system might attempt to ensure that long-term user information (that is, information which exists beyond process execution) is not interfered with or misused by other users. Your description should be clear about when actions are performed and the resources they consume. [5 marks] (d) To what extent are the mechanisms described above useful in single user systems? [3 marks] (e) How do operating systems ensure that they are not themselves overly-restricted by these mechanisms? [3 marks] 4 CST.2014.2.5 4 Operating Systems (a) Describe the difference between blocking and nonblocking input/output operations. How can an operating system improve the performance (as seen by a process) of blocking operations? [4 marks] (b) A privileged process is given raw access to a slow disk device. It reads a page from the disk (using a blocking operation), processes the information and repeats. Suppose a read takes 3 units of time and the processing 2 units of time, so that reading a block and processing takes 5 units of elapsed time. Assuming the machine is otherwise idle, how can this elasped time be reduced? State any assumptions about hardware features you are making. [5 marks] (c) Describe how polled I/O works and state its disadvantages. Under what conditions is polling a sensible approach? Describe an alternative approach. (You may find it helpful to provide a few lines of psuedo code.) [4 marks] (d) What advantages does direct memory access (DMA) provide? Describe its operation as seen by a device driver in the operating system. (You may find it helpful to write a few lines of psuedo code.) [5 marks] (e) To what extent does heterogeneity in I/O systems add complexity to an operating system? [2 marks] 5 (TURN OVER) CST.2014.2.6 SECTION C 5 Software and Interface Design (a) Define briefly, for each of the following techniques, what its purpose is and how it is conducted.

(i) Regression testing (ii) A/B testing (iii) Unit testing (iv) Load testing [12 marks] (b) Although each of these techniques can provide new information of value to a software project, costs can be reduced if information is available earlier in the design cycle. For each of the four techniques in part (a), suggest a method by which some of the resulting information could be obtained earlier in the project. [8 marks] 6 CST.2014.2.7 6 Software and Interface Design The following is an extract from a design brief written by the client for one of the 2014 Cambridge group design projects. What I'd like is some sort of database of recipes to which I can send queries such as "Find me something that doesn't contain cabbage or tomatoes that takes less than 30 minutes to prepare", or "I've got kohlrabi in the veg box AGAIN, are there any recipes I haven't tried that might make something edible out of it?", or "I've actually got a couple of hours free to cook this weekend, what was that complicated Ottolenghi recipe I flagged two weeks ago to try later?". The database needs to cope with the fact that ingredients can have different names but mean the same thing: e.g. "flour" and "plain flour", and that "1/4 lb" and "4oz" are the same thing and equal to "100g" (and not 113g). It would be great if once I've chosen this week's menu, it could produce a shopping list I can plug into www.myfavouritesupermarket.com, and it needs to be usable by non-engineers. (a) For each of the following software project phases, suggest a design model or representation that would be a helpful aid in the design process. For each of these, sketch an example to show what this model looks like, based on some part of the above design brief. (i) Inception phase (ii) Elaboration phase (iii) Construction phase (iv) Transition phase [12 marks] (b) For each of the sketched examples in part (a), describe how the design work so far could be evaluated before proceeding to the next phase. [4 marks] (c) Choose two of the above design models, representations or evaluation methods, and explain how they would be done differently if the design project was following an agile rather than spiral project management approach. [4 marks] 7 (TURN OVER) CST.2014.2.8 SECTION D 7 Discrete Mathematics (a) Let m be a fixed positive integer. (i) For an integer c, let Kc = { k N | k c (mod m) }. Show that, for all c Z, the set Kc is non-empty. [2 marks] (ii) For an integer c, let c be the least element of Kc.

Prove that for all a, b Z, a b (mod m) iff a = b. [4 marks] (b) (i) State Fermat's Little Theorem. [2 marks] (ii) Prove that for all natural numbers m and n, and for all prime numbers p, if m n mod (p 1) then k N. km k n (mod p). [6 marks] (c) (i) Use Euclid's Algorithm to express the number 1 as an integer linear combination of the numbers 34 and 21. [3 marks] (ii) Find a solution x N to 34 x 3 (mod 21). [3 marks] any bugs that it may contain. Give more meaningful identifiers for the variables c and s. Give appropriate comments for the four positions marked "COMMENT HERE". Explain why the method returns a value and what the value means. [8 marks] 0 boolean delete(self, key) 1 # HEADER COMMENT HERE (1) 2 if self.u == 2: 3 if self.A[key] == 0 4 # COMMENT HERE (2) 5 return False 6 else: 7 c = self.cluster[high(key)].delete(low(key)) 8 if c: 9 # COMMENT HERE (3) 10 s = self.summary.delete(high(key)) 11 # COMMENT HERE (4) 12 return s 13 else: 14 return False 3 (TURN OVER) CST.2014.3.4 3 Programming in C and C++ (a) Write a C function revbits() which takes a single 8-bit char parameter and returns a char result by reversing the order of the bits in the char. [4 marks] (b) Write a C function revbytes() taking two parameters and returning no result. The first parameter is a pointer to memory containing n contiguous bytes (each of type char), and the second is the number of bytes. The function should have the side effect of reversing the order of the bits in the n contiguous bytes, seen as a bitstring of length 8n. For example, the first bit of the first char should be swapped with last bit of the last char. [6 marks] (c) You have been assigned the following seemingly working C code, which processes files controlling the behaviour of a system. You observe that, after obtaining several ERR_MALFORMED errors, subsequent calls to fopen fail due to too many files being open: int process_file(char *name) { FILE *p = fopen(name, "r"); if (p == NULL) return ERR_NOTFOUND; while (...) { ... if (...) return ERR_MALFORMED; process_one_option(); ... } fclose(p); return SUCCESS; } (i) Explain how to fix the program using facilities in C. [2 marks] (ii) Now suppose the function above was part of a system written in C++ (but still using the C file-processing commands such as fopen and fclose), and that process_one_option() might raise one or more exceptions. Using a class with a destructor, show how to fix the "too many files open" bug above. [8 marks] 4 CST.2014.3.5 4 Compiler Construction This question concerns the run-time call stack. (a) What is a run-time stack and why is it important to a compiler writer? [3 marks] (b) The implementation of a run-time call stack typically uses a stack pointer and a frame pointer. What are their roles and why do we need two pointers? [3 marks] (c) For some compilers the activation records (stack frames) contain static links. What problem are static links used to solve and how do they solve this problem? [3 marks] (d) (i) Consider a programming language that does not allow functions to be returned as results, but does allow the nesting of function declarations. Using ML-like syntax, we have the following code in this language. let fun f(x) = let fun h(k) = k * x fun g(z) = h(x + z + 1) in g(x + 1) end in f(17) end Draw a diagram illustrating the call stack from the call of f up to and including the call of function h. Make sure all function arguments are included in the diagram and clearly indicate static links. [5 marks] (ii) Using your diagram, explain how the code generated from the body of function h can access the values associated with the variables k and x. In each case make it clear what information is known at compile-time and what information is

computed at run-time. [6 marks] 5 (TURN OVER) CST.2014.3.6 5 Compiler Construction Functional programmers will often rewrite a recursive function such as fun fact1 n = if n <= 1 then 1 else n * (fact1 (n -1)) to one such as fun fact2 n = let fun aux (m, a) = if m <= 1 then a else aux(m-1, m * a) in aux (n, 1) end using an accumulator (the parameter a of aux) and tail recursion. (a) Clearly explain the optimisation such programmers are expecting from the compiler and how that optimisation might improve performance. [4 marks] (b) The desired optimisation can be performed by a compiler either directly on the source program or on lower-level intermediate representations. Treating it as a source-to-source transformation, rewrite fact2 to ML code that has been transformed by this optimisation. You will probably use references and assignments as well as the construct while EXP do EXP. [8 marks] (c) Suppose that the programmer used instead a function as an accumulator. fun fact3 n = let fun aux (m, h) = if m <= 1 then h(1) else aux(m-1, fn r => m * (h r)) in aux (n, fn x => x) end Will your optimisation still work in this case? Explain your answer in detail. [8 marks] 6 CST.2014.3.7 6 Concepts in Programming Languages (a) Write a LISP program for detecting whether a LISP interpreter treats the language as being dynamically scoped (as was the case in historical LISP) or as being statically scoped (as is the case in modern LISP). You may use pseudo-code and should explain your answer in detail. [4 marks] (b) You manage two junior programmers and overhear the following conversation: A: "I don't know why anyone needs a language other than Java, it provides clean thread-based parallel programming." B: "Maybe, but I write my parallel programs in a functional programming language because they are then embarrassingly parallel." Discuss the correctness of these statements and the extent to which they cover the range of languages for parallel programming. [6 marks] (c) Explain why the SML interpreter accepts the declarations datatype 'a FBtree = node of 'a * 'a FBtree list; fun dfs P (t: 'a FBtree) = let exception Ok of 'a; fun auxdfs( node(n,F) ) = if P n then raise Ok n else foldl (fn(t,_) => auxdfs t) NONE F; in auxdfs t handle Ok n => SOME n end; while it does not accept the declaration exception Ok of 'a; [4 marks] (d) Consider the declarations structure Z = struct type t = int; val z = 0 end; structure A = Z : sig type t ; val z: t end; structure B = Z :> sig type t = int ; val z: t end; structure C = Z :> sig type t ; val z: t end; in the SML Modules language. Explain the behaviour of the SML interpreter on inputting each of the expressions Z.z = A.z; Z.z = B.z; Z.z = C.z; [6 marks] 7 (TURN OVER) CST.2014.3.8 7 Further Java Five housemates run a "status" server on their home network. The server stores the current status of each housemate as a string of text. For example, housemate Eva might set her status to "Gone to the exam hall." Messages are passed between clients and the server as text strings sent over TCP. The new line character is used exclusively as the last character in every message. On connection with the server, a client can either (i) query the status of a user by sending the user's name to the server as a string (and the server responds with the current status message), or (ii) set the status of a user by sending the user's name followed by a colon and the new status message. For example, "Eva:Gone to the exam hall." sets the status message for Eva. (a) Implement a status server in Java. The server should run indefinitely, responding to client requests. Once a client request has been fulfilled, the server should close the connection. You may assume current status messages are lost if the server is restarted and you do not need to handle exceptions. [8 marks] (b) One housemate suggests the server and client should communicate by serialising Java objects rather than sending messages as text. (i) Describe in words the changes you would make to your server implementation to send messages as serialised Java objects. [3 marks] (ii) List two advantages and two disadvantages of an implementation based on serialised Java objects versus sending messages as text. [4 marks] (c) Another housemate suggests that the server should not close the client's connection after answering the request. Instead the

connection should remain open until the client sends another request or closes the connection. Describe in words what changes you would need to make to your implementation in part (a) to achieve this and comment on the advantages and disadvantages of this idea. [5 marks] 8 CST.2014.3.9 8 Prolog You are asked to write a Prolog program to work with binary trees. Your code should not rely on any library predicates and you should assume that the interpreter is running without occurs checking. 3 2 7 4 2 5 (a) Describe a data representation scheme for such trees in Prolog and demonstrate it by encoding the tree shown above. [3 marks] (b) Implement a Prolog predicate bfs/2 which effects a breadth-first traversal of a tree passed as the first argument and unifies the resulting list with its second argument. For example, when given the tree shown above as the first argument the predicate should unify the second argument with the list [3,2,7,4,2,5]. [4 marks] (c) Explain why the bfs/2 predicate might benefit from being converted to use difference lists. [2 marks] (d) Implement a new predicate diffbfs/2 which makes use of a difference list to exploit the benefit you identified in part (c). Your predicate should take the same arguments as bfs/2. [6 marks] (e) A friend observes that a clause in diffbfs/2 will need to contain an empty difference list and proposes two possible ways of representing it, either []-[] or A-A. Consider your implementation of diffbfs/2. For each use of an empty difference list, justify your choice and explain what can go wrong using the alternative form. [2 marks] (f ) Is your implementation amenable to last call optimisation (LCO)? If so, explain why. If not, give details of the minimal changes you would make to make LCO possible. [3 marks] 9 (TURN OVER) CST.2014.3.10 9 Software Engineering (a) Describe the main lessons learned from the report into the collapse of the London Ambulance Service. [12 marks] (b) To what extent have the developments in software tools and management practices of the last twenty years improved the situation, and which of the lessons do we still have to be careful of today? Evil Robot's dream of lasting romance remains, alas, just a dream. His latest obsession is a toasted sandwich-maker called SN00005833. In order to win her affections he plans to buy her a chocolate muffin from her favourite shopFat Finbar's World of Cakebefore stealing a bunch of flowers from the local cemetery, giftwrapping the presents, and presenting both gifts to her. Evil Robot's internal systems have been constructed using the situation calculus and a theorem prover. (a) Describe the situation calculus, concentrating on the fundamental elements that you would expect to see independently of any specific problem. [5 marks] (b) Suggest two logical formulae that might appear in Evil Robot's knowledge base in order to describe the initial state for the above problem. [2 marks] (c) Give two examples of a possibility axiom that might appear in the knowledge base. [4 marks] (d) Give two examples of a successor-state axiom that might appear in the knowledge base. One of these should in addition address the ramification problem. Explain how it does this. [6 marks] (e) Give one example of a unique names axiom and one example of a unique actions axiom that might appear in Evil Robot's knowledge base for this problem. Explain why such axioms are required. [3 marks] 2 CST.2014.4.3 2 Artificial Intelligence I This question relates to binary constraint satisfaction problems (CSPs). A CSP has a set X = {x1, . . . , xn} of variables, each having a domain Di = {v1, . . . , vni } of values. In addition, a CSP has a set C = {C1, . . . , Cm} of constraints, each relating to a subset of X and specifying the allowable combinations of assignments to the variables in that subset. (a) Give a general definition of a solution to a CSP. [1 mark] (b) Given a binary CSP, define what it means for a directed arc xi xj between variables xi and xj to be arc consistent. [2 marks] (c) Give an example of how a directed arc xi xj can fail to be arc consistent. Explain how this can be fixed. [2 marks] (d) Describe the AC-3 algorithm for enforcing arc consistency. [5 marks] (e) Prove that the time complexity of the AC-3 algorithm is O(n 2d 3 )

where d is the size of the largest domain. [3 marks] (f ) Suggest a way in which the concept of arc consistency, also known as 2-consistency can be extended to sets of three, rather than two variables. In the remainder of the question we will refer to this as 3-consistency. [1 mark] (g) Give an example of how a set of three variables might fail to be 3-consistent, and show how 3-consistency might then be imposed. [2 marks] (h) Suggest a modified version of the AC-3 algorithm that can be used to enforce 3-consistency. [4 marks] 3 (TURN OVER) CST.2014.4.4 3 Computer Graphics and Image Processing Given a sequence of points (Vi) n i=0 on a plane, consider the problem of interpolating a smooth curve through all of the points in order by constructing a sequence of polynomial parametric functions, one for each interval [Vi , Vi+1] n1 i=0 . (a) What is meant by Ck continuity at the junction between two curve segments? [2 marks] (b) Explain how the degree of the polynomial function for a curve segment constrains the continuity at its two ends. What continuity can be achieved at each end of a cubic segment? [4 marks] (c) Derive a cubic parametric function for the interval [Vi , Vi+1] where 0 < i < n1. [10 marks] (d) What special provision would have to be made for the segments [V0, V1] and [Vn1, Vn]? [4 marks] 4 CST.2014.4.5 4 Computer Graphics and Image Processing Given a model of a scene represented as a set of triangles in three-dimensional space defining its surfaces, consider the problem of rendering it on a raster display. Write brief notes on: (a) the data that would be stored for each triangle; [2 marks] (b) perspective projection from an arbitrary viewpoint; [5 marks] (c) clipping the data to a suitable viewing frustrum; [5 marks] (d) identifying pixels on the screen within a triangle; [3 marks] (e) resolving hidden surfaces using a z -buffer. [5 marks] 5 (TURN OVER) CST.2014.4.6 5 Databases Suppose that an Entity-Relationship model has been constructed that contains two entities S(A, B) and T(C, Amount), where A, B, C and Amount are attributes and the underline indicates a key. Suppose that we also have a many-to- many relationship R between S and T. We might expect that this model would be implemented in a relational schema such as S(A, B), T(C, Amount), and R(A, C). However, the database implementor has noticed that a very common and expensive query is this: given an A-value a, find the sum of all Amount values for records in T related to this a value in S. Therefore, the implementor has decided to "optimise" the database and replace table S with S 0 having schema S 0 (A, B, Sum), where the records in table S 0 will contain the precomputed values for this query. In this way the common and expensive query can be answered by a single key-based read. (Note: Sum should be 0 if no matching records exist.) (a) Explain how the operation insert (a, b) into S can be correctly implemented in the {S 0 , R, T} database. [4 marks] (b) Explain how the operation insert (c, v) into T can be correctly implemented in the {S 0 , R, T} database. [4 marks] (c) Explain how the operation insert (a, c) into R can be correctly implemented in the {S 0 , R, T} database. [4 marks] (d) For an OLTP database, discuss the performance implications of this so-called optimisation. [4 marks] (e) This example illustrates a fundamental trade-off in the design and implementation of database applications. Discuss. [4 marks] 6 CST.2014.4.7 6 Databases (a) We are given a relational schema R(A, B, C, D, E) and told that the following table represents a legal instance of R. A B C D E tuple number 1 2 5 4 3 (#1) 1 4 5 4 4 (#2) 2 4 5 4 5 (#3) 2 5 5 4 3 (#4) Which of the following sets of functional dependencies may hold in R? If a set of dependencies cannot hold, then explain why. You can refer to tuple numbers in your explanation. (i) F1 is the set {A D}. [2 marks] (ii) F2 is the set A, B C E B D, E A [2 marks] (iii) F3 is the set A, B C D, E C A D [4 marks] (b) We are given a relational schema R(Z, W, Y). Suppose that in some (correct) instance of R the query (Z,W(R) Z,Y(R)) R is not empty. What can we conclude about the functional dependency Z W? Explain your answer. [4 marks] (c) In the process of using functional

dependencies to normalise a schema, what is meant by a lossless join decomposition and how is such a decomposition guaranteed? [4 marks] (d) In schema normalisation, is Boyce- Codd Normal Form (BCNF) always to be preferred over 3rd Normal Form (3NF)? Explain your answer. [4 marks] 7 (TURN OVER) CST.2014.4.8 7 Economics, Law and Ethics (a) Describe the provisions of the Data Protection Act. [8 marks] (b) You are designing and are about to launch a mobile phone app which will seek to understand the emotional condition of the user, using multiple inputs such as motion sensing, facial expression recognition, voice stress measurement and the analysis of entered text. Its declared purpose is to enable services to interact more empathically with users. You propose to monetize it by serving ads at times when the user is more likely to buy. Your "backers" have raised a concern that this app will be able to diagnose depression, and that in consequence you may be storing substantial amounts of sensitive personal information. Discuss this problem from the viewpoints of both data protection law and ethics. [12 marks] 8 CST.2014.4.9 8 Security I (a) Windows implements static inheritance for the access-control lists of NTFS files and folders. (i) What does static inheritance mean here and how does it differ from dynamic inheritance? [4 marks] (ii) Five flag bits (ci,oi,np,io,i) in each NTFS access-control entry (ACE) manage how it is inherited. Briefly describe the purpose of each bit. [5 marks] (iii) User mike gives his folder project the following access-control list: project AllowAccess mike: full-access (oi,ci) AllowAccess alice: read-execute (ci,np) AllowAccess bob: read-only (oi) It contains one folder and two text files, none of which have any noninherited access- control entries: project\doc.txt project\src project\src\main.c For each of these three objects, list all inherited access-control entries, showing in parentheses the inheritance-control flag bits that are set (using the same notation as above). [5 marks] (b) Describe the purpose and four typical functions of a root kit. [6 marks] 9 (TURN OVER) CST.2014.4.10 9 Security I Block ciphers usually process 64 or 128-bit blocks at a time. To illustrate how their modes of operation work, we can use instead a pseudo-random permutation that operates on the 26 letters of the English alphabet: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 m A B C D E F G H I J K L M N O P Q R S T U V W X Y Z EK(m) P K X C Y W R S E J U D G O Z A T N M V F H L I B Q As the XOR operation is not defined on the set {A, . . . , Z}, we replace it here during encryption with modulo-26 addition (e.g., C D = F and Y C = A). (a) Encrypt the plaintext "TRIPOS" using: (i) electronic codebook mode; [2 marks] (ii) cipher-block chaining (using IV c0 = K); [4 marks] (iii) output feedback mode (using IV c0 = K). [4 marks] (b) Decrypt the ciphertext "BSMILVO" using cipher-block chaining. What operation should replace XOR? [4 marks] (c) Your opponent is allowed to send you two plaintext messages M0 and M1, each n letters long. You now pick a new private key K, resulting in a new pseudo-random permutation EK : {A, . . . , Z} {A, . . . , Z}. You also pick uniformly at random a private bit b {0, 1} and return a ciphertext C = c0c1 . . . cn, namely the message Mb encrypted with cipher-block chaining using the fresh EK. Finally, your opponent has to guess your bit b. Approximately how large must n be at least for your opponent to have a greater than 75% chance of guessing b correctly? Outline a strategy that your opponent can use to achieve this. In the context of multithreaded algorithms, define work and span, and state the work law and the span law. [3 marks] (b) Prove that the performance of a greedy scheduler is optimal to within a factor of 2. (Proving all intermediate theorems is not required if you state them correctly.) [4 marks] (c) Version A of a multithreaded algorithm takes 500 seconds on a uniprocessor machine and 50 seconds on a 32-processor machine. Version B takes the same time as A on a single processor but only 24 seconds on the 32-processor machine. (i) Define the parallelism of a computation and compute the parallelism of algorithms A and B.

Which of the two has higher parallelism, and by how much? (Hint: use one of the greedy scheduler theorems to derive an approximation for one of the unknowns.) [6 marks] (ii) Estimate the running times of algorithms A and B on a 4-processor and on a 1024- processor machine, explaining how you obtain them. [3 marks] (iii) Sketch possible computation DAGs for algorithms A and B and use them to discuss the results obtained. As the number of processors in the host machine varies, is A or B faster? [4 marks] 2 CST.2014.3.3 2 Algorithms II (a) Consider van Emde Boas (vEB) trees. (i) On its own page for legibility, draw the smallest vEB tree storing keys 0, 3, 6, 7. The correctness of the structure and the accuracy of all fields of all nodes are important. Once done, write each of the keys under the cluster in which it is logically stored. [8 marks] (ii) vEB trees store the minimum and maximum key of a subtree in the root node, but do not store the minimum key in any of the descendent clusters. Explain all the reasons why this provides a performance advantage compared with proto-vEB trees. [4 marks] (b) Consider proto-vEB trees. The following pseudocode attempts to implement a method to delete a key from a proto-vEB node. Give a clear explanation of the strategy that it uses.