Describe five physical properties of a communications channel. [5 marks] (b) Consider the figure below. Entities N and N0 use an ARQ system. Channel - 1 Channel Channel + 1 Entity - 1 Entity Entity + 1 Entity - 1 Entity Entity + 1 n n n N N N N' N' N' (i) Explain how the latency of channel n  1 can have a direct effect on the capacity of channel n. [6 marks] (ii) Define windowing as it relates to an ARQ system and describe how the capacity of the ARQ system may be improved through its use. [4 marks] (iii) If an ARQ system is used for an interactive session, the ARQ system can lead to many small packets, each under-full and perhaps sent with significant overhead. Design and describe an algorithm that overcomes the limitation of sending many mostly-empty packets for an interactive session

(a) State the fundamental theorem of Linear Programming. [3 marks] (b) Consider the following linear program: minimise 4 x1 x2 x1 + 5x2 4 x1 0.5x2 1 x1, x2 0 (i) Convert this linear program into slack form. [3 marks] (ii) What is the number of different slack forms of the linear program in Part (b)(i)? [2 marks] (iii) Give at least one non-feasible and one feasible basic solution of the linear program in (b)(i). [4 marks] (c) Consider the following separation problem. We are given m points x 1 = (x 1 1 , x1 2 ), x2 = (x 2 1 , x2 2 ), . . . , xm = (x m 1 , xm 2 ) R 2 and n points y 1 = (y 1 1 , y1 2 ), y2 = (y 2 1 , y2 2 ), . . . , yn = (y n 1 , yn 2 ) R 2 . The goal is to find a "separating" vector w = (w1, w2) R 2 (if it exists) such that: hx i , wi = X 2 j=1 x i jwj > 0 for i = 1, 2, ..., m, and hy i , wi = X 2 j=1 y i jwj < 0 for i = 1, 2, ..., n. (i) Create a new, equivalent system of inequalities by replacing each strict inequality by a suitable non-strict inequality. Justify why this new system has a solution if and only if the original system has one. [4 marks] (ii) Based on your answer in Part (c)(i), how can you solve the above problem using linear programming? [4 marks]

(a) Summarise the idea of a basic block and explain why it is useful in intermediate representations for optimising compilers. [3 marks] (b) Construct the flowgraph (in which every node is a basic block consisting of one or more 3-address instructions) for the C function: int f(int x, int y) { int r = x + 1; if (y == 0) { r = r * r; } else { y = y - 1; r = r * y; } return r + 1; } [4 marks] (c) Define static single assignment (SSA) form, and explain the changes you would have to make to your flowgraph from part (b) in order for it to be in SSA form. [3 marks] (d) Consider a. Each node whose instruction assigns some value to a variable is considered a "definition" of that variable; we are interested in discovering, for each node n in the flowgraph, which definitions reach n. A definition m is considered to reach n if the variable to which m assigns a value may still have that value at entry to n. (i) Define the notion of a definition reaching a node in the flowgraph in terms of possible execution flows of control. [2 marks] (ii) By analogy with live variable or available expression analysis, or otherwise, design dataflow equations for computing RD(n), the set of definitions which can reach a node n. [4 marks] (iii) Sketch an algorithm to compute RD(n), briefly commenting on any initialisation required.

(a) Explain the method of Active Contours. What are they used for, and how do they work? What underlying trade-off governs the solutions they generate? How is that trade-off controlled? What mathematical methods are deployed in the computational implementation of Active Contours? [10 marks] (b) When trying to detect and estimate visual motion in a scene, why is it useful to relate spatial derivatives to temporal derivatives of the image data? Briefly describe how one motion model works by these principles. [5 marks] (c) Provide a 3 3 discrete filter kernel array that approximates the Laplacian operator. Explain what the Laplacian might be used for, and what is the significance of the sum of all of the taps in the filter. [3 marks] (d) When visual sequences are encoded into an .mpeg video stream, typically about what percentage of the compression achieved is intra-frame (compression within individual still frames), and what percentage is inter-frame? Name a key feature that is extracted and estimated for purposes of prediction and, therefore, compression.

The Needham-Schroeder protocol is defined as 1. A S : A, B, NA 2. S A : {NA, B, KAB, {KAB, A}KBS }KAS 3. A B : {KAB, A}KBS 4. B A : {NB}KAB 5. A B : {NB 1}KAB (a) Explain the symbolism, and the purpose of the messages. [5 marks] (b) Explain the "bug" in the protocol. [5 marks] (c) Is the bug actually a vulnerability if one can assume (as the Needham- Schroeder paper does) that all principals execute the protocol faithfully? If not, why is it important? [5 marks] (d) Describe how one modern protocol derived from Needham-Schroeder deals with the issue.

Define the M/M/1 queueing model and derive the steady-state distribution for the number of customers present when the traffic intensity is less than one. [5 marks] (b) For the M/M/1 model in steady-state, derive the mean number of customers present and the mean time spent by a customer in the system. What is the utilisation of the server? [5 marks] (c) Now consider the M/M/1/K queueing model with K finite and again derive the steady-state distribution for the number of customers present. For what values of the traffic intensity does your steady-state distribution exist? What is the utilisation of the server and explain how this compares to the M/M/1 queueing model. [5 marks] (d) Give an example of the use of the M/M/m/m loss model. Derive Erlang's formula for the (a) Consider a software routine that converts and records the audio samples received in a digital telephone network call (8 kHz sampling frequency, 8 bit/sample) into a WAV file (8 kHz sampling frequency, 16 bit/sample, uniform quantisation). Your colleague attempted to write a very simple conversion routine for this task, but the resulting audio is very distorted. (i) Name two variants of the method used for quantising the amplitude of audio samples in digital telephone networks and explain one of them. [4 marks] (ii) Your colleague's routine right-pads each 8-bit data word from the telephone network with eight additional least-significant zero bits to obtain 16-bit values. Explain how this distorts the signal by discussing which frequencies could appear at the output when the incoming telephone signal consists of a pure 1 kHz sine tone. [4 marks] (b) A real-valued discrete random sequence {xi} is fed into a linear time-invariant filter with impulse response h0 = 1, h3 = 1, and hi = 0 for all other i. We observe for the resulting output sequence {yi} the expected value E(yi+k xi) = 1 for k = 1 2 for k = 0 1 for k = 1 1 for k = 2 2 for k = 3 1 for k = 4 0 otherwise What is the value of the autocorrelation sequence {xx(k)}? [4 marks] (c) The Y CrCb colour encoding is used in many image compression methods. (i) How is it defined and why is it used? [4 marks] (ii) Is the conversion from 3 8-bit RGB to 3 8-bit Y CrCb coordinates fully reversible? Why?steady-state probability that an arriving customer finds all m servers occupied.

(a) Given two signed distance field functions f and g, give the formula for their . . . (i) Union (fg) (ii) Intersection (fg) (iii) Difference (fg) [3 marks] (b) Give clear definitions for the Virtual Reality industry's principles of immersion and presence. Compare the two concepts and explain the difference between them with examples demonstrating each. [5 marks] (c) The Doo-Sabin subdivision scheme has kernel (1/4)[. . . , 0, 0, 1, 3, 3, 1, 0, 0, . . .], defining a scheme in which each face is replaced by four new vertices. (i) Give an expression for computing the position of a new vertex given the positions of the four old vertices of a face. [2 marks] (ii) If the face does not have 4 vertices then you must weight each parent vertex differently to find the position of the child. Suggest possible weights for the vertices of faces with 3, 5, and n vertices, and justify your answer. [3 marks] (d) There are several ray-tracing-friendly acceleration structures. (i) Explain the BSP tree data structure. Explain how it is constructed and traversed. [3 marks] (ii) Explain the kd-tree data structure. Explain how it is constructed and traversed. [3 marks] (iii) Which of the two data structures is best-suited to ray-tracing a game of chess in real time? [1 m