Digital Communication I X A B C D Y Hosts X and Y are communicating through the data network provided by the switches A, B, C and D and the links interconnecting them as shown above. Initially all packets are travelling through switches A, C and D. (a) A packet is corrupted on the link between C and D. Describe the events that take place to recover from the error when (i) an end to end flow and error control protocol is in operation [5 marks] (ii) flow and error control are performed on a hop by hop basis [5 marks] (b) Switch C fails. Describe the events that follow to recover when (i) the network is a datagram network [d5 marks] (ii) the network is connection oriented [5 marks] 4 Graphics Consider the control of detail in a curve represented as a sequence of straight line segments. Describe Douglas and Peucker's algorithm for removing superfluous points. [10 marks] Describe how Overhauser interpolation can be used to introduce additional points. [10 marks] 2 CST.96.12.3 5 Business Studies In a project plan what is meant by a critical path, and why is the concept useful? [5 marks] A certain software project has two phases. Each phase has three tasks (analysis, coding and testing) which must be performed sequentially. Analysis for phase 2 cannot be started until analysis for phase 1 is complete. The effort in person-weeks, as estimated by the programmers, in each task is given in the table below. Task Phase 1 Phase 2 Analysis 4 8 Coding 4 4 Testing 4 8 Two staff are assigned to the project. Tasks may be performed by either member of staff. Analysis and coding tasks can have only one person usefully working at a time whereas, for testing, the time to completion is inversely proportional to the effort expended. Draw PERT and GANTT charts for the project, and indicate the critical path. [5 marks] Staff are each paid 24,000 per annum. The company allows for overheads of 100% of salary. Equipment worth 50,000 will be needed, depreciated over 5 years. Payment is proposed as 25% on start, 25% on delivery of the first phase, and 50% on completion. Draw up a rough budget and cash flow for the project. How much working capital (excluding equipment purchase, but including depreciation) is required? [5 marks] What price and delivery would you quote for this project? Explain the additional factors you have considered in formulating your quotation. [5 marks] 3 [TURN OVER CST.96.12.4 6 Programming in C and C++ For five of the following C or C++ features write a very short fragment of code (perhaps 2 or 3 lines will suffice in most cases) that illustrates the syntax involved. In each case explain very briefly what your example achieves. (a) preprocessor macros and conditional compilation (b) casts that convert from one pointer type to another (c) C and C++ style comments (d) the declaration of a simple C++ class (e) overloading the operator '+' (f ) the C setjmp function (g) the switch statement, including a default label [4 marks each] 7 Compiler Construction Outline the key features of the design of the part of a compiler that will translate the abstract syntax tree representation of a program into a stack-based intermediate code. Concentrate on those features used in the translation of the following fragment: ... LET i = k LET j = k WHILE (i>0) AND (j<100) DO { i := i-1; j := j+2 } ... In particular, concentrate on the mechanism you would choose to deal with (a) the scopes of identifiers [6 marks] (b) the compilation of boolean expressions involving the operators NOT, AND and OR [6 marks] (c) the translation of the WHILE command [4 marks] (d) the translation of the two assignments [4 marks] 4 CST.96.12.5 8 Prolog for Artificial Intelligence An ordered integer binary search tree (or OIBS tree) is either empty or a tuple (T, N, U), where T and U are also OIBS trees and N is an integer. Every node in T has a value less than N, which in turn is less than the value of every node in U. (a) Give two Prolog terms which are suitable for representing an empty OIBS tree and a node in the OIBS tree respectively. [2 marks] (b) Define a Prolog procedure insert(Item, T, NT), where Item is an integer being inserted into OIBS tree T, producing an OIBS tree NT. If Item is already present in T, then NT equals T. [9 marks] (c) Define a Prolog procedure lookup(Item, T), where Item is to be looked for in OIBS tree T. A lookup goal will succeed if Item is found, or fail otherwise. [9 marks] 9 Databases Describe the essentials of the ODMG-93 standard for Object Database Management. [7 marks] To what extent do these proposals conform to the ANSI/SPARC architecture for database management? [3 marks] Describe how binary relationships can be modelled directly within the ODMG-93 standard. [4 marks] In what way is it possible to create a representation for n-ary relationships that is similar to that of the relational model? [2 marks] Explain how these alternative approaches allow a navigational style of data manipulation as well as supporting an extension of SQL. [4 marks] 5 [TURN OVER CST.96.12.6 10 Designing Interactive Applications Some of today's photocopiers are connected by networks to repair centres so that technicians can monitor their performance and detect problems without visiting customer premises. Although this offers cost savings, it can have a negative impact on customer relations. Suggest an explanation for this, drawing on your knowledge of the service technician's job. [5 marks] You have been asked to design a modification to a networked photocopier, to enable users to send messages to the repair centre when they encounter problems. Again drawing on your understanding of the nature of photocopier repair work, produce a rough design for the message-system user interface. Include a one-sentence problem statement, a mental-model description and an outline of the design of the user interface itself. [15 marks] 11 Introduction to Functional Programming Describe how recursive definitions are modelled in the -calculus using Y. [6 marks] Consider the following attempt to define Y in ML: val Y = fn f => (fn x => f (x x)) (fn x => f (x x)) Explain why this doesn't work. [6 marks] Give a satisfactory definition of Y in ML and illustrate its use by defining the factorial function. [4 + 4 marks] 12 Computer Vision Discuss the problem of face recognition and face detection based on wavelet encodings of facial structure and facial features. How can one distinguish between those facial undulations that are generic (universal, or normally present in all faces), and those which are particular to a given face and which therefore distinguish it from others? How can statistical decision theory formalize these two pattern recognition problems - face detection and face recognition? What are the main advantages and disadvantages of using wavelets for the encoding of faces? [20 marks] 6 CST.96.12.7 13 Complexity Theory (a) Show that the problem 3-SAT is at least as hard to solve as n-SAT. [5 marks] (b) Show that the task of finding a minimum cost closed circuit in a weighted directed graph (a Travelling Salesman Problem of the minimization variety) is at least as hard as the Hamiltonian Circuit Problem. [5 marks] (c) Show that the class NP-complete is contained in the class P-space. [5 marks] (d) Show that the class P-space is contained in the class EXP-time. [5 marks] In each case ensure that your answer makes it clear what the problems and classes involved are. Standard results do not need to be proved provided they are clearly stated. 14 Numerical Analysis II In Peano's theorem, if a quadrature rule integrates polynomials of degree N exactly over an interval [a, b], then the error in integrating f C N+1[a, b] is conventionally expressed as E(f) = Z b a f (N+1)(t)K(t) dt where K(t) = 1 N! Ex[(x t) N + ]. Explain the notation (x t) N + and Ex. [3 marks] It follows directly from Taylor's theorem that E(f) = 1 N! Ex Z x a f (N+1)(t)(x t) N dt . Explain clearly, in simple stages, how to complete the proof of Peano's theorem. [8 marks] For the mid-point rule, what is N? [1 mark] If K(t) does not change sign in [a, b] then E(f) = f (N+1)() (N + 1)! E(x N+1) for some (a, b). Use this result to simplify E(f) = Z 1 1 f(x) dx 2f(0) [8 marks] 7We want to determine whether some basic-block orderings in "for every basic block" result in fewer overall iterations than others. Suppose the program has k basic blocks, but no cycle in the control flow graph; give an optimal ordering which only requires one dataflow iteration to calculate liveness (a second would only calculate the same value of the first). Also give such a program and an ordering which maximises the number of iterations required, giving the number of iterations in terms of k. [5 marks] (e) Consider the program with four labelled blocks (with B1 as entry node): B1: x = read(); y = read(); z = read(); goto B2; B2: z = z+1; x = x-1; if (x>0) goto B3; else goto B4; B3: z = z+1; y = y-1; if (y>0) goto B2; else goto B4; B4: print(z); Show (i) there is no basic block ordering for which a single iteration gives the correct liveness at each label, but (ii) there is an ordering for which two iterations suffice (in the sense that a third would agree with the second). Give your ordering both explicitly as a permutation of {B1, B2, B3, B4} and also as a general principle along the lines of your answer to part (d).

Imagine you have been commissioned to design the user interface for a head-up display (e.g. based on Google Pof appointment reminders and instructions should be as simple as possible. Describe three specific ways this can be achieved, using formal elements of visual design. [6 marks] (b) Consider the possibility that users might wish to modify their appointment schedules while riding. Choose three different Cognitive Dimensions of Notations, and discuss their implications. [6 marks] (c) Describe ways that features of the bicycle itself might form the basis for (i) a tangible user interface; and (ii) an augmented reality interface to this system. For each of these, explain what sensor processing would be involved. [4 marks] (d) How might these two alternative interfaces be compared experimentally? Describe the structure of the experimental design and procedure for analysis of the results.

) Modify the grammar so that the following sentence is now accepted in addition: the dog the cat the mouse sees hates sneezes Your modification should express the linguistic phenomenon as efficiently and elegantly as possible. Justify your choice. [6 marks] (c) The semantics of natural language expressions can be expressed in first order predicate logic (FOPL). For instance, "the dog sneezes" can be approximately expressed as x dog(x) sneeze(x) Following this pattern, express the semantics of the sentence in part (b) in FOPL. [4 marks] (d) Consider the following sentence: the mouse that sees the cat that hates the dog that sneezes Contrast this construction to the one in part (b) in terms of semantics and syntax. How would you modify the original grammar in part (a) to account for this construction?

Suppose that you read about the design of an end-to-end transport protocol for an early version of the Internet, which uses window-based flow control with a fixed size window, with Go-Back-N retransmission of all un-acknowledged packets when there is a time-out awaiting an acknowledgement for any given data packet. How would you convince the designer that they are going to have real problems with such a simplistic scheme?

(a) Formally state the two rules of the Bell-LaPadula (BLP) security policy model and then re-state them informally in terms of a single rule about the direction of information flow. [2 marks] (b) Consider a distributed system in which A is a TOP SECRET process running on machine Alice and B is a CONFIDENTIAL object residing on machine Bob. (i) Explain and justify whether A is allowed to read and/or write from B according to the BLP policy. [2 marks] (ii) Discuss the claim made by some researchers that this scenario highlights a fundamental problem with the BLP policy. [4 marks] (c) Consider the following description of Brewer and Nash's Chinese Wall security policy model. Simple rule: Read or write access to object o2 by subject s is granted if and only if, for all objects o1 to which s has had access, we have: (class(company(o1)) 6= class(company(o2)) or (company(o1) = company(o2)). *-rule: Write ccess to object o2 by subject s is granted if and only if access is granted by the simple rule and there does not exist any unsanitized object o1, readable by s, for which company(o1) 6= company(o2). (i) Explain the context and goal of the Chinese Wall security policy model. Then explain what each of the two rules is intended to enforce or prevent. [4 marks] (ii) Some researchers have claimed that the formal rules of Chinese Wall do not match the policy that Brewer and Nash intended to enforce, to the extent that the resulting policy is unusable in practice. Explain precisely why the policy would be unusable and give a clear proof of this claim.

Consider an inertial measurement unit that reports its change in distance and heading each second, but is subject to typical sensor errors such as bias and noise. A particle filter is to be used to fuse its output with a building map to estimate the current location of a user within that building. (a) Describe the evolution of the spatial distribution of the particles as a user moves through the building to their office. Assume that the initial position is unknown, but that the filter has correctly estimated the user's position before they reach their office. Additionally, the filter continues to run thereafter (during which time they are seated and not travelling). What factors influence the speed of transition between the regimes identified? [9 marks] (b) The particle filter is to run on a low power embedded platform that transmits its position results over WiFi. However, it is found to process particles too slowly for real-time tracking. (i) Describe the three stages of a particle filter cycle in the context described above. Assuming a multi-core GPU is available, discuss how easily they can be parallelised to increase performance. [5 marks] (ii) Describe two further ways to increase performance in such a system. [4 marks] (c) The internal structures of many office buildings change over time, as offices merge or split. Assuming the building map is not kept synchronised with these changes, discuss the effects on the positioning system described.

(a) Give some ML text to replace in the following: fun f g g = g; f x y; to make it into a valid ML program. (b) Given the following ML function definition: fun h x y z = x (y z); what is the type of h? (c) Let A be the set {1, 2, 3, 4}. Exhibit (or state briefly why this is impossible) a relation R on A which is a function whose inverse relation R1 is a partial function, but not a (total) function. (d) Solve the recurrence f(0) = 0 f(1) = 3

(e) It is claimed that there is a bijection from (A+B) C to (A C)(B C). Demonstrate this by replacing both "..." below with valid ML code which might form such a bijection and its inverse. Just ML is required, not proof. datatype BplusS = left of bool | right of string; fun LtoR(f: BplusS -> real) : (bool->real) * (string->real) = ...; fun RtoL((g: bool->real), (h: string->real)) : (BplusS -> real) = ...; (f ) Give an equation involving a set named S, such that the smallest (with respect to ) solution for S is the set of values represented by the ML datatype s: datatype s = empty | leaf of int | branch of s*s; Your solution may reasonably involve the constructors empty, leaf and branch. (g) Given an integer value between 0 and 9, show an expression in Modula-3 for the equivalent character. (h) What output would the following Modula-3 fragment produce when P was called? PROCEDURE P () = PROCEDURE Q (VAR a: INTEGER) = BEGIN a := 2 * a + b END Q; VAR a := 1; b := 2; c := 3; BEGIN Q (c); IO.Put (Fmt.Int (a) & " "); IO.Put (Fmt.Int (b) & " "); IO.Put (Fmt.Int (c) & " "); END P; (i) What is meant by an address space?

Princess Precious is a very light sleeper, and insists that every night she must sleep on brand new silk sheets. Her younger brother, however, is in the habit of secretly scattering toast crumbs in her bed, to make sure she sleeps badly. In order to get the week started well, he does this every Sunday with probability 0.9. For the rest of the week, he tends to relent on any given night if he placed crumbs in her bed the previous night, and hence leaves them with a probability of 0.1. On the other hand, if he did not leave crumbs on a given night, his mischievous nature compels him to leave crumbs the next night with probability 0.6. Precious, being a true princess, tends to be grumpy in the morning if she has not slept well. Consequently, if she has slept with crumbs in her bed she is grumpy with probability 0.95. Being a light sleeper, even if there are no crumbs she is grumpy with probability 0.55. (a) Give a detailed definition of a Hidden Markov Model (HMM) and show how the scenario described can be modelled as an HMM. [4 marks] (b) Give a detailed description of the Viterbi algorithm for computing the most probable sequence of states, given that an HMM produces a given sequence of observations. [8 marks]

Given the two DNA sequences: GCACTT and CCCAAT (a) Compute the alignment (using the edit graph) and the final score with the following rules: match score = +1, mismatch = 1, gap penalty = 1. [4 marks] (b) Discuss how the alignment score and the quality of the result depend on the match score, mismatch, and gap penalty. [6 marks] (c) Generate four, short DNA sequences (a,b,c,d) such that their relations as a tree are approximately the following: ((a,b),(c,d)). [5 marks] (d) How is the score matrix used in phylogenetic tree building techniques?

This question is about Intellectual Property and Copyright. (a) List 5 types of Intellectual Property. Comment on their use to protect a software program. [5 marks] (b) Explain what Intellectual Property Rights (IPR) an employee has on their inventions. Does this differ if the invention is made in their own time? [5 marks] (c) Professor Elbowpatch, a professor of ancient languages and keen amateur gardener, invents a new sort of lawnmower. What are his IPR options? [5 marks] (d) Discuss what actions Professor Elbowpatch should take to exploit his invention.

(a) Why might a heterogeneous or asymmetric chip-multiprocessor be preferable to a homogeneous or symmetric one? [5 marks] (b) You are a computer architect working on the design of a new processor for the mobile phone market. An initial analysis of applications suggests that there would be worthwhile gains in producing a processor that could offer two different power-performance tradeoffs. The first configuration would maximise the exploitation of ILP and consume the most power. The second would on average perform less well, but would consume less power. (i) Describe how the microarchitecture of a single processor could be modified in order to offer the ability to switch between the two configurations described at run-time. [9 marks] (ii) How might one determine when to switch from one configuration to the other in order to reduce overall power consumption while minimising the impact on the user experience?

. Find the area and volume of sphere/cube?

write program to convert celsius to fahrenheit / celsius to kelvin ?

: Write program that reads a person's first and last names, separated by a space. Then the program outputs last name, comma, first name.

(a) Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that whenever D is a domain and f is a continuous function, fix (f) exists. [5 marks] (b) A poset (P, v) has binary meets if for every pair of elements x, y P there is a necessarily unique element (x u y) P such that (x u y) v x and (x u y) v y, and for all z P, z v x and z v y imply z v (x u y). (i) Let (P, v) be a poset with binary meets. Show that the function meet : P P P given by meet(x, y) = x u y is monotone. [5 marks] (ii) Exhibit a domain with binary meets for which the function meet is not continuous. Justify your answer

A gate in a communications network is always in one of two states, open or closed. At each clock pulse it may change state according to the following rules: If it is open it remains open with probability 1 and changes to closed with probability . If it is closed it remains closed with probability 1 and changes to open with probability . It may be assumed that 0 < < 1 and that 0 < < 1. Let un be the probability that the gate is closed just after the nth clock pulse. Derive a difference equation for un and justify your derivation. [4 marks] Let u0 be the probability that the gate is closed initially. Solve your difference equation so as to give un in terms of , , u0 and n. [7 marks] Determine an expression for un in the limit as n and explain informally why this does not depend on u0. [3 marks] Find un in each of the four extreme cases: = 0, = 0; = 0, = 1; = 1, = 0; and = 1, = 1. Explain the operation of the system in each case. Suppose f(x) is a probability density function associated with a continuous random variable X and y(x) is a transformation function whose inverse is the function x(y). The derived random variable Y = y(X)

Suppose that X is distributed Uniform(0,1) and, accordingly, has an associated probability density function f(x) given by: f(x) = 1, if 0 6 x < 1 0, otherwise Suppose, further, that Y is required to be distributed as a triangular distribution such that the probability density function g(y) is: g(y) = ( 1 + y, if 1 6 y < 0 1 y, if 0 6 y < 1 0, otherwise Determine the transformation function y(x) that satisfies this requirement.