Question:

Check you are in charge of the design of both hardware and software for a new (but fairly conventional) workstation which will have its peripherals (for example a disc drive and a printer) directly connected to it. Your workstation will be required to support an operating system that allows its user(s) to run several independent programs at once. Explain and justify the method that you will provide for an application program to gain access to kernel services and physical input/output devices For both a printer and a disc drive, indicate additional functions (beyond those provided by the physical device itself) that an operating system typically provides in software.f a program is written cautiously and in a suitable high level language then it can be "portable", and one set of source files can be used with little or no change on a wide variety of computers and with many different operating systems. Explain the steps that are taken to turn the source version of such a program into a runnable version of the application that it represents. Indicate all the places where programs or pieces of code not derived from the portable sources are involved. [4 marks] Identify which parts of the software preparation path (if any) will need to be altered in each of the following cases, commenting on just where programs and code (not being directly part of the portable source) can be used unaltered and where different versions are called for: (a) The program is to be run on different hardware configurations of the various models of the same computer; [4 marks] (b) The program is to be run on computers which share the same hardware design and have the same processor, but under different operating systems (for example some PCs will run MSDOS, Unix and several other operating systems); [4 marks] (c) The program is to be run on two machines that share a common operating system (such as Unix) but which have different processor designs. [4 marks] Suppose the portable programming language involved is implemented using an interpreter rather than a compiler, and the language is already implemented on all the computer systems involved. How does this affect the amount of work and the number of changes needed when building an executable version of a program for use in many different environments?

Briefly explain the global illumination methods radiosity and photon mapping. Highlighting the strengths and weaknesses of each method, compare and contrast the two. You will be marked for correctness, clarity and brevity. [8 marks] Recall that the signed distance field (SDF) expression of a surface returns the signed nearest distance from a sample point to the surface. This is well-suited to ray-marching on a GPU. As an example, the SDF method describing a unit cube centred at the origin may be written in openGL shading language (GLSL) as: float cube(vec3 pt) { return max(abs(pt.x), max(abs(pt.y), abs(pt.z))) - 1; } (b) Give an SDF method cylY(pt, len, radius) for a finite cylinder of specified length and radius, centred at the origin, parallel to the Y axis. [4 marks] (c) Give an SDF method hollowedSphere(pt) which specifies the model shown in Figure 1: a unit sphere hollowed along each axis by a cylindrical hole of radius 0.5. [6 marks] (d) How would you repeat your hollowed sphere at two-unit intervals infinitely across the XZ plane as illustrated in Figure 2? [2 marks] Figure 1: A unit sphere hollowed along each axis by a hole of radius 0.5 Figure 2: The hollowed unit sphere infinitely repeated in XZ at intervals of 2 Ground plane is for illustration only

The runtime system of a concurrent programming language includes semaphore management and user-thread management modules. The design assumption was that the operating system on which the concurrent programs are to run supports only one process per address space. Outline the functionality and interaction of semaphore and user-thread management. [6 marks] The runtime system is to be ported to run on an operating system which supports multi-threaded processes and symmetric multiprocessing. (a) Describe how the two modules must be changed in order to support one kernel-thread per user-thread [5 marks] scheduler activations [5 marks] State any assumption you make about the functionality of the operating system. (b) Discuss the problem of concurrent execution of the semaphore management module and how this concurrency might be controlled. [4 marks] 1 [TURN OVER CST.99.3.2 2 Continuous Mathematics Many important problems in mathematical modelling and scientific computing require the use of complex variables. Unfortunately, popular programming languages like C do not have a complex variable type, and so we must construct them from floating-point types. Assuming that the quantities a, b, c, d are all real numbers and i = 1, resolve the following expressions, or explain the following operations, involving complex variables Z1 = a + ib and Z2 = c + id: (a) Let Z3 = Z1Z2. What is the real part of Z3, and what is its imaginary part? [2 marks] (b) What is kZ1k, the modulus of Z1, and what is kZ3k, the modulus of Z3 = Z1Z2? [2 marks] (c) What is Z2, the angle of complex variable Z2? [2 marks] (d) Express Z1 in complex polar form, not using the quantities a or b but rather the modulus kZ1k and angle Z1. [2 marks] (e) Suppose that Z1 and Z2 both have a modulus of 1. Explain, with the aid of a diagram, how their product Z3 = Z1Z2 amounts to a rotation in the complex plane. Why is the multiplication of these complex variables reduced now to addition? Without using the quantities a, b, c, d, what is the value of kZ3k? [4 marks] (f ) Suppose that in complex polar form, Z = exp(2i/5). What do you get if Z is multiplied by itself 5 times? Give the simplest possible answer that you can. [2 marks] (g) Consider the complex exponential function f(x) = exp(2ix). What function is its real part? What function is its imaginary part? [2 marks] (h) If the above function f(x) passes through a linear system, i.e. is operated upon by any conceivable linear differential or integral operator, what is the most dramatic way in which f(x) can possibly be affected? [4 marks] 3 Further Java Describe the facilities in Java for defining classes and for combining them through composition, inheritance and interfaces. Explain with a worked example how they support the principle of encapsulation in an object-oriented language. [15 marks] What is meant by reflection or introspection in Java? Give an example of its use. [5 marks] 2 CST.99.3.3 4 Compiler Construction A programming language has expressions e with the following syntax: e ::= x | n | e + e 0 | e(e 0 ) | (e) | let x = e in e 0 | letsta f(x) = e in e 0 | letdyn f(x) = e in e 0 where f and x range over identifiers and n ranges over numbers. The three let variants introduce simple variables (let) and (non-recursive) functions whose variables are statically (letsta) or dynamically (letdyn) bound. Using e itself (or any related language whose relationship to e is explained) as abstract syntax define an evaluator eval which, when given an expression e and an environment , yields the value of evaluating e in . The evaluator can be written in a language of your choice or in mathematical pseudo-code. [12 marks] Explain carefully in one sentence each: (a) the forms of value which eval may return; (b) the form(s) of value which constitute the environment; (c) the use(s) of environment(s) in letsta and in a call to a function defined by letsta; (d) the use(s) of environment(s) in letdyn and in a call to a function defined by letdyn. [8 marks] Hint: because both letsta and letdyn functions may be applied using the same function call syntax, you may find it helpful to use separate forms of value for the two forms of functions. 3 [TURN OVER CST.99.3.4 5 Introduction to Security Define access control lists and capabilities, and discuss their relative strengths and weaknesses. [5 marks] Describe how the access control list mechanisms work in Unix. [5 marks] You have been asked to build a funds transfer system in which a payment is authorised only once it has been approved by both a manager and an accountant at a bank branch. How would you implement this system using Unix security mechanisms as the foundation? [10 marks] 6 Data Structures and Algorithms Describe Larsen's method of dynamic hashing that enables a record to be located on a disk given its key using just one disk transfer and only a modest amount of information held in main memory. [10 marks] In Larsen's method each key has associated pseudo-random sequences of probe and signature values. Discuss what properties these sequences should have. Outline an algorithm that could be used to compute the n th probe-signature pair for a given key. You may assume that the key is a character string. [6 marks] Briefly discuss why Larsen's method is not used in most current filing systems. [4 marks] 7 Computer Design Why is MIPS (millions of instructions per second) a poor measure of a computer's performance? [4 marks] Explain why high-performance processors use pipelines to increase the MIPS rating and yet pipelines tend to increase the time to execute an instruction. [4 marks] instruction decode/ execute memory register fetch register fetch access write back With reference to the classic RISC pipeline above, explain what a data hazard is. [6 marks] How are feed-forward paths used to reduce pipeline stalls? [6 marks] 4 CST.99.3.5 8 Operating System Functions FIFO, LRU, and CLOCK are three page replacement algorithms. (a) Briefly describe the operation of each algorithm. [6 marks] (b) The CLOCK strategy assumes some hardware support. What could you do to allow the use of CLOCK if this hardware support were not present? [2 marks] (c) Assuming good temporal locality of reference, which of the above three algorithms would you choose to use within an operating system? Why would you not use the other schemes? [2 marks] What is a buffer cache? Explain why one is used, and how it works. [6 marks] Which buffer cache replacement strategy would you choose to use within an operating system? Justify your answer. [2 marks] Give two reasons why the buffering requirements for network data are different from those for file systems.

(a) For random variables (RVs) A1, A2 and B, define what it means for A1 to be conditionally independent of A2 given B, written A1 A2|B. [1 mark] (b) Given mutually disjoint sets X1, X2 and Y of random variables from some Bayesian network, define what it means to say that a path from x1 X1 to x2 X2 is blocked by Y . [5 marks] (c) Given mutually disjoint sets X1, X2 and Y of random variables from some Bayesian network, define what it means for X1 and X2 to be d-separated by Y . What does this tell you about the probability distribution represented by the Bayesian network? [3 marks] (d) Consider the following Bayesian network. A B C D E F G In each of the following cases, establish whether or not X1 X2|Y : (i) X1 = {A, E}, X2 = {G} and Y = {F}. [2 marks] (ii) X1 = {A}, X2 = {D} and Y = {G}. [3 marks] In each case explain your answer. (e) Define how Bayesian networks and Markov random fields are used to represent probability distributions, and briefly describe the trade-offs involved in choosing one versus the other. [6 marks] 4 CST2.2017.7.5 4 Bioinformatics (a) Discuss the time and space complexity of dynamic programming algorithms in the context of sequence alignment problems. [6 marks] (b) Describe the differences between Soft and Hard Clustering. [6 marks] (c) Construct the de Bruijn graph of TACCTTCAGCGCCTTC by splitting it into k-mers for a suitable value of k. Comment on how the choice of k affects the construction. Discuss the use of de Bruijn graphs in the context of genome sequencing. [8 marks] 5 Business Studies (a) Describe five types of Intellectual Property. [5 marks] (b) Describe five topics that might be in a Market Requirements Document. [5 marks] (c) Giles Murchiston, a PhD student, has invented a new algorithm to control a dog walking robot. He realises that his algorithm may have wider applications including driverless cars, factory and farm robots, drones, and uses such as domestic robot lawnmowers or robot vacuum cleaners. Advise Giles on the exploitation of his idea.

6 Comparative Architectures (a) What features of a processor's instruction set are desirable if a pipelined implementation is planned? [5 marks] (b) The performance of a processor typically improves when a modest number of pipeline stages are created. Why does it become difficult to maintain near linear performance gains with deeper pipelines? [5 marks] (c) Clustered superscalar processors partition functional units into clusters. Data forwarding within a cluster operates as normal allowing dependent instructions to execute on consecutive clock cycles. Communication between clusters normally incurs an additional delay of 1 or 2 clock cycles. The clustering idea may also be extended to include the issue buffer (also known as the issue window). (i) What problem does clustering attempt to solve? [5 marks] (ii) Assume a processor has two symmetric clusters that contain both functional units and an issue buffer. In this processor, instructions must be steered to a particular cluster before they are inserted in an issue buffer. What should the two basic goals of a good steering policy be? [5 marks] 6 CST2.2017.7.7 7 Denotational Semantics (a) (i) Define the notion of least pre-fixed point fix(f) of a continuous endofunction f on a domain and state Tarski's fixed point theorem for it. [2 marks] (ii) State Scott's fixed point induction principle. [2 marks] (b) Let f : D D, g : E E, and h : D E be continuous functions between domains such that h f = g h : D E. Show that if h is strict (that is, h(D) = E) then fix(g) = h

fix(f)

N. Wirth's textbook Algorithms + data structures = programs (1976) contains the following story. I married a widow (call her W) who has a grown-up daughter (D). My father (F), who visited us quite often, fell in love with my step-daughter and married her. Hence my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (S1), who became the brother-in-law of my father, as well as my uncle. The wife of my father - that is, my step-daughter - also had a son (S2). Using Prolog, cv of facts that represents the situation in the above story. [5 marks] Add rules defining the family relationships (such as father-in-law) described in the story. [5 marks] Show how a Prolog system would use your program to prove the goal "I am my own grandfather". [10 marks] 9 Databases Explain the ANSI/SPARC architecture for Data Base Management Systems, and show how it supports data independence. [5 marks] Describe the relational model of data introduced by E.F. Codd in 1970. [4 marks] What are its strengths and weaknesses? [7 marks] What factors have led to its dominant position in the market place today? [4 marks] 5 [TURN OVER CST.99.12.6 10 Introduction to Functional Programming Define a polymorphic datatype to represent binary trees. [1 mark] Define a function, post, to traverse such a binary tree in post-order. Your function should make use of @, the list append function. [2 marks] Comment on the efficiency of your function post, and wri a more efficient function, post2, which has no occurrences of @, the list append function. [2 marks] Prove using induction that your two functions are equal, i.e. t . post(t) = post2(t). [8 marks] Define a polymorphic datatype to represent trees where a node may have any number of subtrees. [1 mark] Define a function, post3, to traverse such a tree in post-order. (This function need not be efficient.) [6 marks] 11 Computer Vision It is often useful in computer vision to represent and analyse image content by means of complex variables, even though an image itself is defined as an array of real numbers. Give at least two distinct examples of useful operations in computer vision based on complex variables, identifying clearly the mathematical domain in which the complex variables exist. Explain in each case what is achieved by adopting such a representation.