Trusted software could then be run on the workstation. Discuss the advisability of this approach to workstation design.    (10 marks) b) Explain how distributed inter-process communication (IPC) is supported in the distributed systems        (10 marks) c) Give any five examples of IPC modes in distributed systems and explain how they work           (10 marks) QUESTION TWO (20 MARKS) a) Explain the importance of ensuring the timeliness of messages in cryptographic protocols           (8 marks) b) Give a careful account of the main techniques used for ensuring timeliness, including any environmental assumptions       (6 marks) c) Under what circumstances is it proper to use time values when there is no clock synchronisation        (6 marks) Meru University of Science & Technology is ISO 9001:2015 Certified                                 Foundation of Innovations  Page 1 QUESTION THREE (20 MARKS) a) Define a distributed system and give examples in modern society  (7 marks) b) Using examples explain how distributed systems work    (7 marks) c) A distributed computation may involve related operations n a number of objects which reside at different nodes of a distributed system. Explain why the concept of transaction is suitable for modeling such a computation     (6 marks) QUESTION FOUR (20 MARKS) a) What are the problems of passing data values between different machines with different operating systems        (8 marks) b) Explain how these problems can be solved     (6 marks) c) Explain what is involved in committing a transaction in a distributed system(6 marks) QUESTION FIVE (20 MARKS) A distributed software system follows the client-server model. The microkernel on which it is based supports multi-threaded processes. A remote procedure call (RPC) package is used for client-server interactions. The RPC system runs above an unreliable, datagrambased communications service a) Explain how timers may be used in the RPC protocol to achieve client-server synchronization        (8 marks) b) Discuss how the RPC system may support the location of remote procedures (6 marks) c) Discuss the requirements on the RPC system that follow from the use of multithreaded processes     Question: Early programming languages had relatively poor facilities for type checking, data abstraction, data hiding and encapsulation. Explain the meaning of these terms and discuss their importance. [6 marks] Outline the key features that a language must have to be called object-oriented and briefly discuss to what extent C++, Java and Smalltalk have them. [7 marks] Briefly discuss some of the reasons why C++ programs typically run faster than equivalent programs written in Java or Smalltalk. [7 marks] 6 Compiler Construction It is desired to obtain an unambiguous context-free grammar G0 which generates the same strings as the following grammar G with start symbol S. S -> E E -> ( E ) | [ E ] | E * E | a | b | c ( E ) -> ( + E ) [ E ] -> [ - E ] Define a suitable G0 or explain why G already satisfies the criterion. [6 marks] Write context-free (Type 2) grammar which describes floating-point numbers of the form []dd [.d ][e[]dd ] where d stands for decimal digit and d  stands for zero or more decimal digits. [  ] means that the enclosed item is optionally present in the floating-point number. [7 marks] Sketch a recursive descent parser for the following grammar H with start symbol S. You should assume the existence of a routine lex() which sets variable token to one of '1', '2', '(', ')', '-' or eof. P -> 1 | 2 | (E) E -> P | E - P S -> E eof 

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.

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 Momentarily clarify the job of the attest articulation and why this program will trigger a state disappointment when executed. Supply two altered adaptations of the program that change the trade work definition and, assuming fundamental, its calls, to stay away from this state disappointment. One rendition should be in C, and the other should utilize C++ language highlights. [4 marks] (c) Describe the location space format (featuring four areas of memory) of a ordinary incorporated x86 C program, and how every one of these areas are utilized by C builds. [8 marks] (d) Briefly clarify what indistinct conduct is in the C norm. Under what circumstance(s) would calling the accompanying C capacity result in unclear conduct? int32_t divide(int32_t a, int32_t b) { return a/b; }

(a) Consider vague conduct in C. (I) Define whaonduct. [3 marks] (ii) Briefly clarify why it is critical to have undefined conduct in the meaning of the C language. [1 mark] (b) Compare and differentiation the struct and association catchphrases in C, providing an illustration of a circumstance where it would be more proper to utilize an association rather than a struct. [4 marks] (c) Explain the accompanying C or C++ language ideas. You might find it supportive to utilize short code sections or outlines to show your response. (I) The virtual catchphrase used to qualify a C++ part work and its sway on produced code. [4 marks] (ii) The job of the C preprocessor in the source-code gathering cycle, and why it is a helpful device for investigating. [4 marks] (iii) Templated capacities in C++, giving one advantage and one downside of utilizing them contrasted and involving a void* work in C.

(a) Assuming that it is mapped to a square with texture co-ordinates from (0, 0) to (1, 1), sketch a picture of the procedural texture map generated by the following Java code. Use textual annotations to indicate the colours of the various parts of the picture. [7 marks] Color BLUE = ...; Color GREEN = ...; Color WHITE = ...; Color parametricTexture(double tu, double tv) { double r1 = 2 * Math.sqrt( (tu - 0.25) * (tu - 0.25) + (tv - 0.5) * (tv - 0.5) ); double r2 = 2 * Math.sqrt( (tu - 0.75) * (tu - 0.75) + (tv - 0.5) * (tv - 0.5) ); double f = f(r1) + f(r2); return (f > 0.45 && f < 0.55) ? WHITE : GREEN.times(f).plus(BLUE.times(1 - f)); } private double f(double r) { if (0 <= r && r < 0.333) { return 1 - 3*r*r; } else if (0.333 <= r && r < 1) { return 1.5*(1-r)*(1-r); } else { return 0; } } (b) Write brief notes that explain the following. (i) Explain Perlin Noise, including how it differs from white noise. [3 marks] (ii) Explain Barycentric Co-ordinates, including how they are calculated. Diagrams are encouraged. [3 marks] (c) Given a ray R(t) = O + Dt and a unit sphere S, initially centred on the origin and subsequently transformed by affine matrix M, where M represents the transformation of the sphere from local to world coordinates: (i) state the centre of the sphere in local co-ordinates and in world co-ordinates; (ii) give an expression in terms of t for the local co-ordinates of the intersections between R and S; (iii) give an expression for the world co-ordinates of the same intersections; and (iv) give an expression for the world co-ordinates of the normal at those intersections.

(a) Describe the differences in complexity and usage between parsimony and distance phylogenetic methods. Give an example of the usage of both methods. [6 marks] (b) Describe the differences in complexity and usage between hierarchical clustering and the Markov clustering (MCL) algorithm. [5 marks] (c) Explain how to identify different gene features using Hidden Markov Model methods such as Genescan. [5 marks] (d) Explain how you could identify a regulatory network involving a set of genes.

6 Foundations of Computer Science (a) Explain in detail how a binary search tree represents a dictionary. If reference types are not used, what is the average-case cost of an update operation? [8 marks] (b) A mutable binary tree is either a leaf or a branch node containing a label and references to two other mutable binary trees. Present the ML datatype declaration for mutable binary trees. [2 marks] (c) Describe how to use this datatype to implement (mutable) binary search trees. Give ML code for the lookup and update operations. The update operation must never copy existing tree nodes. (a) Define the terms injective, surjective and bijective, and state the Schroder- Bernstein theorem concerning the existence of a bijection between two sets. [4 marks] (b) What is a countable set? [2 marks] (c) Prove the following assertions: (i) If C is a countable set and f : A C is an injection, then A is countable. [2 marks] (ii) If A and B are countable sets, then A B is countable. [2 marks] (iii) Z and Q, the sets of integer and rational numbers, are both countable. [4 marks] (iv) P(N), the set of all subsets of the natural numbers, is not countable. [2 marks] (v) If U is an uncountable set and f : U V is an injection, then V is not countable.

program that first gets a list of integers from the input and adds them to an array. The input begins with an integer indicating the number of integers that follow a 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.

(a) You are to design a component of a distributed system which takes action on the arrival of an alarm event from another component. Discuss the design issues, relating to the characteristics of distributed systems, of the component and its communication. [4 marks] (b) You are to design a service that takes in streams of messages from distributed sources and notifies its clients when certain specified patterns of messages occur. Discuss the design issues associated with supporting the following operators for constructing message patterns, where A and B represent messages: (i) A OR B; (ii) A AND B (unordered pairs); (iii) A BEFORE B (ordered pairs). [16 marks] 5 Advanced Systems Topics (a) Considerable recent operating system research has focused on extensibility. (i) What is the motivation for this work? [1 mark] (ii) Describe with the aid of examples three different techniques for providing extensibility. In each case comment on the granularity of extensibility provided, and discuss the issues of performance and safety. [5 marks each] (b) Some researchers claim that programming language virtual machines such as the JVM should be extensible. (i) Why might this be desirable? [1 mark] (ii) How could this be safely achieved? Comment on how your solution might differ from those used in the case of operating system extensibility.

(a) The Digital Signature Standard is computed using the following equations: r = (g k mod p) (mod q) s = (h(M) xr)/k (mod q) Describe what the various symbols represent. [4 marks] (b) Write down the equation(s) used to verify a signature. [4 marks] (c) The standard specifies that r must lie strictly between 0 and q. What might go wrong if an implementation does not check this? [4 marks] (d) A designer decides to economise on code size by omitting the hash function computation, that is, replacing h(M) by M. What are the consequences of this optimisation?

(a) Explain in one sentence what is meant by the "phase order problem". [2 marks] For the rest of the question, it is recommended that you restrict attention to a single basic block containing only unary and binary arithmetic instructions, e.g. add#4 dst,src or mul dst,src1,src2 and with no variable written to after being read (SSA form). Consider all such instructions to execute in one cycle. (b) Describe how a directed acyclic graph expressing instruction dependencies suitable for instruction scheduling can be obtained from such a basic block. [4 marks] (c) Briefly describe how a (register interference) graph can be obtained from such a basic block. Also state a requirement for colouring this graph with registers. [4 marks] (d) Consider the two programs (where the first four lines are the same): add t1,a,b add t1,a,b add#2 t2,c add#2 t2,c add#3 t3,c add#3 t3,c mul t4,t2,t3 mul t4,t2,t3 sub z,t1,t4 sub t5,t1,t4 xor t6,t5,a xor z,t6,b In each case consider scheduling the add t1,a,b to appear as early as possible or as late as possible. Determine the number of registers required to colour the program in all four resulting cases. (Assume that only z, allocated to r1, is live on exit and that a,b,c are allocated registers r1,r2,r3.) [10 marks] [Remark: you might note that doing add t1,a,b in the left-hand program decreases the number of live registers by one, while it increases the number by one on the right-hand program.