) Explain the collision detection mechanism applied in standard wired medium access control associated with CSMA and indicate why this might be unsuitable for wireless networks. [2 marks] (ii) Describe how CSMA/CA (Collision Avoidance) works and explain its limitations. [2 marks] (iii) Illustrate how MACAW works and indicate its limitations on the exposed terminal problem through an example. [3 marks] (iv) Would the deployment of MACAW be needed in an installation of a MAC protocol for a single base station that communicates with some mobile terminals? Why? [3 marks] (b) You are called upon, as expert, to design and deploy a wireless sensor network to monitor environmental factors in a 500 m2 area within a forest. (i) Describe the network architecture you would deploy to collect sensed data in the forest. [2 marks] (ii) Briefly illustrate two different MAC layer protocols for sensor networks and then indicate which one you would employ for your network and why. [4 marks] (iii) Explain the salient characteristics of Directed Diff Describe the process through which DD is able to reconfigure when sensor nodes fail in the network. [4 marks]

) Consider integer division of one two's-complement binary number by another. Programming languages may vary in the result when one argument is negative. What differing conventions might they be following? [2 marks] (b) Describe carefully, or give pseudocode for, the standard binary integer longdivision procedure. What common fault must it guard against? [6 marks] (c) Describe the iteration technique known as successive approximation by bisection. What does it have in common with standard long division? [3 marks] (d) Describe carefully, or give code changes to, the standard long division algorithm from part (b) so that it computes two bits of result per iteration. [3 marks] (e) Single-precision floating-point representation uses a sign bit, eight bits of exponent, a hidden bit and 23 bits of stored mantissa. Using a consistent encoding, similar or identical to the IEEE standard, give hexadecimal representations of the following four numbers: 1.0, 0.125, 4096.0 and 0.0. [4 marks] (f ) Consider different versions of an optimising compiler, each of which uses IEEE standard representation for all variables. Give two reasons why they might compile a floating-point program into code that, when run, produces differing

(a) State what is meant by a directed graph and a strongly

Illustrate your description by giving an example of such a graph with 8 vertices

and 12 edges that has three strongly connected components. [5 marks]

(b) Describe, in detail, an algorithm to perform a depth-fifirst search over such a

graph. Your algorithm should attach the discovery and fifinishing times to each

vertex and leave a representation of the depth-fifirst spanning tree embedded

within the graph. [5 marks]

(c) Describe an O(n) algorithm to discover all the strongly connected components

of a given directed graph and explain why it is correct. You may fifind it useful

to use the concept of the forefather (v) of a vertex v which is the vertex, u,

with highest fifinishing time for which there exists a (possibly zero length) path

from v to u. [10 marks]

2 Computer Design

(a) What is a data cache and what properties of data access does it exploit?

[5 marks]

(b) What is a direct mapped cache and under what conditions will it exhibit poor

performance? [5 marks]

(c) Under what circumstances might a word of data in main memory be

simultaneously held in two separate fifirst-level cache lines? [5 marks]

(d) A translation look aside buffffer is a specialised cache. What does it typically

store and why is it often a factor of 1000 smaller than a data cache? [5 marks]

2CST.2001.6.3

3 Digital Communication I

(a) Defifine the terms circuit and packet in the context of communication systems.

[5 marks]

(b) What sort of guarantee does circuit switching provide? [5 marks]

(c) What advantages does packet switching provide over circuit switching?

[5 marks]

(d) Which of frequency division multiplexing, time division multiplexing and code

division multiplexing lend themselves to circuit switching? Which to packet

switching? Explain why or why not in each case. [5 marks]

4 Computer Graphics and Image Processing

(a) Describe the z-buffffer polygon scan conversion algorithm. [10 marks]

(b) In ray tracing, once we have determined where a ray strikes an object, the

illumination at the intersection point can be calculated using the formula:

I = Iaka +X

i

Iikd(Li N) +X

i

Iiks(Ri V)n

Explain what real effffect each of the three terms is trying to model and explain

what each of the following symbols means, within the context of this formula:

I, Ia, i, Ii , ka, kd, ks,Li, N, Ri, V, n

[10 marks]

3

[TURN OVERCST.2001.6.4

SECTION B

5 Comparative Programming Languages

(a) Brieflfly explain the concept of coroutines as used in BCPL and outline

the effffect of the library functions createco(f, size), deleteco(ctpr),

callco(cptr, val) and cowait(val). [10 marks]

(b) Outline how you would design a coroutine to merge, in increasing order, two

infifinite streams of increasing integers supplied by two other coroutines.

[5 marks]

(c) Brieflfly outline how you would implement an analogous merging mechanism in

an object-oriented language, such as Java, that does not provide a coroutine

mechanism. [5 marks]

6 Compiler Construction

(a) Describe one possible structure (e.g. ELF) of an object fifile. Illustrate your

answer by considering the form of object fifile which might result from the

following C program.

int a = 1, b = -1;

extern int g(int);

extern int c;

int f() { return g(a-b) + c; }

It is not necessary to consider the exact instruction sequence, just issues

concerning its interaction with the object fifile format. [10 marks]

(b) Describe how a linker takes a sequence of such programs and produces an

executable fifile. [4 marks]

(c) Compare and contrast static and dynamic linking in a system using your object

fifile format. [6 marks]

4CST.2001.6.5

7 Prolog for Artifificial Intelligence

A weighted binary tree can be defifined using compound terms in the following way.

A node of the tree is represented by the term n(V, L, R), where V stands for the

value of the node, and L and R stand for the left and right branches, respectively.

A terminal node has the R and L components instantiated to the null list.

Given an input tree T, write a Prolog program that constructs a tree of the same

shape as T, but in which the value of each node has been set to the value of the

maximum value node in T.

[Note: Maximum marks are available only for programs that perform this task in

one recursive descent of the input tree, and which use no more than four clauses.]

[20 marks]

5

[TURN OVERCST.2001.6.6

8 Databases

The environmental agency is setting up an SQL database to monitor long-term

trends in the climate. Data are collected from observatories of a number of difffferent

kinds.

Flood risk is of particular concern. Each water authority measures river levels and

rates of flflow hourly at major points, and records reservoir levels daily.

In addition, the agency maintains weather stations both inland and at sea. These

record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind.

Values of new precipitation, temperature, pressure, and wind speed and direction

are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur.

Maximum and minimum temperature and pressure, the total number of hours of

sunshine and the total precipitation are recorded daily. Inland stations can be

grouped by water authority.

By default these primary data will be relegated to archive after 2 years. Selected

information is retained permanently in a data warehouse. This serves two purposes.

First, it holds monthly summary data consisting of the maximum (and minimum

as appropriate) day value for each statistic, together with the monthly totals of

sunshine and precipitation. The warehouse also keeps detailed information relating

to periods of extreme weather from the relevant observatories, with one or more

keywords describing the nature of the incident (flflood, blizzard, hurricane etc.) and

an optional comment.

Write notes to assist in the design of the schema for the relational data warehouse,

including any diagrams that you fifind helpful. Explain how your design will enable

meteorologists to fifind relevant past records, noting any assumptions that you make

about the nature of the data.

[You should not go into unnecessary detail about the structure of the primary

database. You may assume that expert meteorologists will select the data for the

warehouse.]

[20 marks]

6CST.2001.6.7

SECTION C

9 Semantics of Programming Languages

Write short notes on four of the following fifive topics.

(a) The relationship between three forms of operational semantics of the Language

of Commands (LC) given by

an evaluation relation h P, si hV, s0 i

a transition relation h P, si hP0 , s0 i

a transition relation between the confifigurations

h c, r, si of the

SMC-machine

(b) The notion of semantic equivalence of LC phrases and its congruence property.

(c) Call-by-name and call-by-value rules for evaluating function applications in the

Language of Functions and Procedures (LFP) and the relationship between the

evaluation relations for LFP based upon each of them.

(d) The notion of bisimilarity of two confifigurations in a labelled transition system.

(e) The rules defifining the possible labelled transitions of parallel composition

(P1|P2) and restriction ( c . P) in the Language of Communicating Processes

(LCP).

[5 marks each]

7

[TURN OVERCST.2001.6.8

10 Foundations of Functional Programming

The following are some concepts that have flflourished in the context of functional

programming but which have (so far) been less heavily used in main-stream

languages even when they have been available:

(a) polymorphic types

(b) type reconstruction

(c) higher-order functions

(d) lazy evaluation

(e) continuations

For each case give a brief explanation of the facility referred to, suggest a

circumstance in which it might be useful and comment on how immediately relevant

to non-functional languages it seems.

[4 marks per part]

8CST.2001.6.9

11 Logic and Proof

(a) In the context of clause-based proof methods, defifine the notion of pure literal

and describe what should be done if the set of clauses contains pure literals.

[3 marks]

(b) Use the Davis-Putnam method to discover whether the following set of clauses

is satisfifiable. If they are satisfifiable, show a satisfying interpretation.

{P, R} {P, R} {P, Q} {Q, R} {P, Q, R}

[6 marks]

(c) The three-fifingered inhabitants of the planet Triterra build base-3 computers.

A Triterran named Randal Tryant has found a way of verifying base-3

combinational logic. His Ordered Ternary Decision Diagrams (OTDDs) are

the same as a technology used on planet Earth except that all variables and

expressions range over the values 0, 1 and 2 instead of just 0 and 1.

(i) Describe how a full ternary decision tree can be reduced to an OTDD

without regard for effiffifficiency. [2 marks]

(ii) Sketch an effiffifficient algorithm to convert a ternary expression directly to an

OTDD without constructing the full decision tree. For a typical ternary

connective use modulo-3 multiplication, written as . [6 marks]

(iii) Demonstrate your algorithm by applying it to the ternary expression

((i i) j) 2. [3 marks]

9

[TURN OVERCST.2001.6.10

12 Complexity Theory

(a) Show that any language that can be accepted by a nondeterministic machine

in time f(n) can also be decided by a deterministic machine in space O(f(n)).

[4 marks]

(b) Show that any language that can be accepted by a nondeterministic machine

in space f(n) can also be decided by a deterministic machine in time

O(c(f(n)+log n) ), for some constant c. [6 marks]

(c) Explain what the above results tell us about the inclusion relationships among

the complexity classes:

NL, co-NL, P, NP, PSPACE and NPSPACE

[4 marks]

(d) It has been proved that the graph reachability problem is in co-NL. What

further inclusions can you derive among the above complexity classes using

this fact? Explain your answer.

A sequential circuit has been built, and it behaves slightly erratically. When switched on it produces on its three output wires one of the following patterns: 000 001 100 110 011 000 010 101 111 010 or The second pattern is not intended to arise. Deduce the circuit details and propose a modification that ensures that in due course the circuit will always settle into the cycle shown in the first pattern.Two gamblers play a game which involves tossing a fair coin. After t2 tosses the first gambler has scored k wins. If there is no record of the sequence of tosses, what probability distribution describes the situation after t1 tosses (t1 < t2)? If the game is tied after eight tosses, show that the probability that it was tied after four is 18 35 .

(a) In image compression we use three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values; (ii) quantising those values; (iii) symbol encoding the resulting values. Explain each mechanism, describe the way in which it helps us to compress the image, and describe how the mechanism is implemented in the baseline JPEG compression method. [10 marks] (b) Describe the limitations of human vision in terms of: (i) spatial resolution, (ii) luminance, (iii) colour, and explain the implications that each of these has on the design of display devices, including numerical estimates of the limits beyond which a human cannot discriminate.

(a) A continuous communication channel adds Gaussian white noise to signals transmitted through it. The ratio of signal power to noise power is 30 decibels, and the frequency bandwidth of this channel is 10 MHz. Roughly what is the information capacity C of this channel, in bits/second? [5 marks] (b) Explain the comb function, comb(t) = X(t), its role in the sampling theorem, its self-Fourier property, and the constraint on the spacing of the comb's tines that is required in both the signal domain and consequently in the Fourier domain in order to reconstruct exactly, from discrete samples, a signal having no frequency components higher than W.

(a) Explain the steps and the complexity of the Hirschberg algorithm and illustrate them with an example. [7 marks] (b) Give one example why the multiple alignment, as implemented in the software Clustal, needs a guide tree. [5 marks] (c) Explain what an amino acid exchange propensity matrix is and how you would construct it. [3 marks] (d) Explain with an example why a compression algorithm is often needed in genome assembly. [5 marks] 3 Computer Systems Modelling Consider a M/M/1 queueing system with an arrival rate > 0 and a service rate > 0 where = / < 1. (a) Derive the distribution for N, the total number of customers present in the queueing system in equilibrium. [6 marks] (b) Suppose that the queueing system is in equilibrium. For each of the following terms define the quantity and determine its value: (i) utilization (ii) throughput (iii) mean number of customers present in the system (iv) mean time spent by a customer in the system [8 marks] (c) Now suppose that the arrival rate and service rate are both scaled by a factor of s > 0. For each of the four quantities in part (b) determine their new values and explain your findings.

Describe the process of specifying a major piece of software: the main documents produced, their immediate purpose and their ongoing role in the software life cycle. Describe the role that formal methods can play at each stage of the software life cycle. Explain any disadvantages of the uses of formal methods that you have discussedProve or disprove each of the following statements, stating clearly any well known results that you use. (a) The set of strings over the alphabet {0, 1} that contain exactly twice as many occurrences of 0 as of 1 is a regular language; (b) Let L be a regular language over an alphabet . Then the language consisting of those u such that there is some v with uv L, is also a regular language; (b) Any finite subset of {a, b} is a regular language; (d) For any regular expressions r and s, the regular expressions (r s ) and (r|s) always denote the same language. [20 marks] 28 Unix Case Study What is an i-node and what information is contained in it? Describe how named files are mapped to i-nodes. How is the information associating disc blocks with i-nodes represented? What restrictions are placed on name to i-node links to simplify file system recovery

(a) In Mini-ML, define the relation of specialisation between (i) type schemes and types, A ( ) 0 [1 mark] (ii) type schemes and type schemes, A ( )A0 ( 0 ) [2 marks] (b) What is meant by the principal type scheme of a closed expression in Mini-ML? [2 marks] (c) State the Hindley-Damas-Milner Theorem for the Mini-ML typeability problem. [2 marks] (d) Define what is meant by a Mini-ML typing problem. Outline a type inference algorithm for Mini-ML that operates on typing problems. You should explain what is a solution and a principal solution for a typing problem, state the properties of the output of the algorithm and explain its overall structure. How does the algorithm make use of fresh type variables and of unification? Illustrate your answer by describing how the algorithm operates on function application expressions.

(a) Describe briefly six factors which might influence or constrain the design of a new processor. [6 marks] (b) The performance of a superscalar processor is often enhanced with hardware to support the following: branch prediction register renaming out-of-order execution the speculative reordering of load instructions strided prefetching (i) Sketch an assembly language program that would benefit from the use of all of these techniques when executed on a superscalar processor. Briefly describe how each of the techniques helps to improve the performance of your program. [10 marks] (ii) Briefly outline two example programs for which the adoption of the techniques listed would not provide a significant performance improvement.

. Write program that insert number from the keyboard, and find out the number is prime or not? Write complete C++ program to ask the user to enter 4 integers. The program must use a function to find the LARGEST integer among them and print it on the screen. Write c++ program to calculate the sum of all the elements in an array. : Write C program to print the Fibonacci series using for loop?

(a) (i) Suppose that FX(x) is a distribution function. Show the inverse transform result, namely that, if U is a random variable uniformly distributed in the interval (0, 1) then X = F 1 X (U) is a random variable with distribution function P(X x) = FX(x). [4 marks] (ii) Discuss the notion of a pseudo-random number generator for uniform random variables. Describe suitable algorithms for generating pseudorandom numbers. [6 marks] (iii) Using the inverse transform result in part (a)(i) derive a method to generate a stream of independent pseudo-random numbers from an exponential distribution with parameter > 0. What are the true mean and variance of these numbers in terms of ? [4 marks] (b) (i) Suppose that you conduct a simulation experiment to estimate the mean, , of a random quantity X from a sample of n values X1, X2, . . . , Xn. How would you estimate ? [2 marks] (ii) Now suppose that your simulation also yields a sample of n values Y1, Y2, . . . , Yn of the random quantity Y where E(Y ) = Y is a known number. How would you use the method of control variates to improve your estimator of ? Your answer should mention all quantities that may need to be estimated and in what way you will improve the estimation of

(a) Why does the formal security definition for collision-resistant hash functions require a key s and a security parameter n, even though most commonly used standard secure hash functions lack such input parameters? [4 marks] (b) If hs : {0, 1} {0, 1} `(n) is a collision-resistant hash function, do the following constructions Hs also provide collision-resistant hash functions? Explain your answers. [2 marks each] (i) Hs(x) = hs(x) k x (i.e. append x) (ii) Hs(x) = hs(x) k LSB(x) (i.e. append least significant bit of x) (iii) Hs(x) = hs(x | 1) (bitwise-or, i.e. set least significant bit of x to 1) (c) Use Euler's theorem to calculate 51 mod 8. [4 marks] (d) The standard Digital Signature Algorithm (DSA) uses a cyclic subgroup G Z p of the integers modulo a prime p, with prime order q, where q divides p 1. (i) Give two advantages of using a multiplicative subgroup of prime order, as opposed to just using Z p , in cryptographic schemes based on the Discrete Logarithm problem. [2 marks] (ii) Why is it possible to choose q substantially smaller than p, and what is an advantage of doing so?

(a) SoC design involves dividing work between hardware and software as well as deciding the number of general-purpose and custom processors and co-processors to be used. What main factors influence these design decisions and the associated manual partition of envisaged workload over these resources? [5 marks] (b) A lossless compression algorithm converts fixed-size, 1 kByte blocks of data to a variable-sized block that is normally shorter. Suggest a suitable signature (argument and return types) for a software function that implements the algorithm. Draw a diagram showing the external wiring to the neighbouring SoC components for an appropriate, high-performance, hardware implementation. State any assumptions that guide your design approach. [6 marks] (c) A synchronous hardware module has separate input and output ports that each convey 32-bit words. Handshaking is required on both ports since it is unpredictable whether the module or its environment are ready to exchange data in either direction at any time. Give a diagram or RTL module definition for such a component and precisely describe the handshaking protocol in words. State the maximum throughput of your protocol. [5 marks] (d) Why might it be useful to have a formal specification of your protocol from part (c) during design and testing? What, if anything, might we infer about the number of words stored inside the module from the protocol? [4 marks] 13 Topical Issues (a) Compare and contrast the Internet of Things (IoT) with the conventional internet. [4 marks] (b) Describe how Bluetooth Low Energy (BLE) was designed to address the following IoT-related issues. Your answers should consider both BLE advertising and data channels. (i) Reduce the overall power consumption of peripherals. [6 marks] (ii) Handle radio channel contention from other IoT devices

kindly answer all the questions