Prolog You are approached to compose a Prolog program to work with twofold trees. Your code shouldn't depend on any library predicates and you ought to expect that the mediator is running without happens checking. 3 2 7 4 2 5 (a) Describe an information portrayal plot for such trees in Prolog and exhibit it by encoding the tree displayed previously. [3 marks] (b) Implement a Prolog predicate bfs/2 which impacts an expansiveness first crossing of a tree passed as the principal contention and binds together the subsequent rundown with its subsequent contention. For instance, when given the tree displayed above as the main contention the predicate ought to bring together the second contention with the rundown [3,2,7,4,2,5]. [4 marks] (c) Explain why the bfs/2 predicate could profit from being switched over completely to utilize distinction records. [2 marks] (d) Implement another predicate diffbfs/2 which utilizes a distinction rundown to take advantage of the advantage you recognized to some extent (c). Your predicate ought to accept similar contentions as bfs/2. [6 marks] (e) A companion sees that a proviso in diffbfs/2 should contain a vacant contrast list and proposes two potential approaches to addressing it, either []-[] or A. Consider your execution of diffbfs/2. For each utilization of an unfilled contrast list, legitimize your decision and make sense of what can turn out badly utilizing the elective structure. [2 marks] (f ) Is your execution amiable to last call advancement (LCO)?Suppose that R(A, B, C) is a relational schema with functional dependencies F = {A, B C, C B}. (i) Is this schema in 3NF? Explain. [2 marks] (ii) Is this schema in BCNF? Explain. [2 marks] (b) Decomposition plays an important role in database design. (i) Define what is meant by a lossless-join decomposition. [2 marks] (ii) Define what is meant by a dependency preserving decomposition. [2 marks] (c) Let R(A, B, C, D, E) be a relational schema with the following functional dependencies i) What is the closure of {A, B}? [2 marks] (ii) What is the closure of {B, E}? [2 marks] (iii) Decompose the schema to BCNF in two different ways. In each case, are all dependencies preserved? Explain. [4 + 4 marks]

For a transaction model based on objects and object operation time-stamps: (a) (i) Define how conflict may be specified in terms of object operation semantics. (ii) Give an example of conflicting operations. (iii) Give an example of non-conflicting operations that would be defined as conflicting under read-write semantics. [3 marks] (b) Define the necessary and sufficient condition for two transactions to be serialisable. Give an example of a non-serialisable execution of a pair of transactions. [3 marks] (c) Define the necessary and sufficient condition for any number of transactions to be serialisable. [1 mark] (d) Discuss how the following methods of providing concurrency control in database systems enforce the properties defined above. (i) Strict two-phase locking. [4 marks] (ii) Strict timestamp ordering. [4 marks] (iii) Optimistic concurrency control. [5 marks]

) In the context of virtual memory management: implemented? [4 marks] (ii) What is meant by temporal locality of reference? [2 marks] (iii) How does the assumption of temporal locality of reference influence page replacement decisions? Illustrate your answer by briefly describing an appropriate page replacement algorithm or algorithms. [3 marks] (iv) What is meant by spatial locality of reference? [2 marks] (v) In what ways does the assumption of spatial locality of reference influence the design of the virtual memory system? [3 marks] (b) Buses are used to connect devices to the processor. (i) Describe with the aid of a diagram the operation of a synchronous bus. [4 marks] (ii) In what ways does an asynchronous bus differ? [2 marks

Consider an operating system that uses hardware support for paging to provide virtual memory to applications. (a) (i) Explain how the hardware and operating system support for paging combine to prevent one process from accessing another's memory. [3 marks] (ii) Explain how space and time overheads arise from use of paging, and how the Translation Lookaside Buffer (TLB) mitigates the time overheads. [3 marks] (b) Consider a system with a five level page table where each level in the page table is indexed by 9 bits and pages are 4 kB in size. A TLB is provided that is indexed by the first 57 bits of the address provided by the process, and achieves a 90% hit rate. A main memory access takes 40 ns while an access to the TLB takes 10 ns. The maximum memory read bandwidth is 100 GB/s. (i) What is the effective memory access latency? [4 marks] (ii) A colleague suggests replacing the system above with one that provides 80 GB/s memory read bandwidth and main memory access latency of 30 ns. Explain whether you should accept the replacement or not, and why. [4 marks] (c) A creative engineer suggests structuring the TLB so that not all the bits of the presented address need match to result in a hit. Suggest how this might be achieved, and what might be the costs and benefits of doing so. [6 marks]

(a) Describe two quantitative and two qualitative techniques for analysing the usability of a software product. [4 marks] (b) Compare the costs and benefits of the quantitative techniques. [6 marks] (c) Compare the costs and benefits of the qualitative techniques. [6 marks] (d) If restricted to a single one of these techniques when designing a new online banking system, which would you choose and why?

(a) Suppose that women who live beyond the age of 80 outnumber men in the same age group by three to one. How much information, in bits, is gained by learning that a person who lives beyond 80 is male? [2 marks] (b) Consider n discrete random variables, named X1, X2, . . . , Xn, of which Xi has entropy H(Xi), the largest being H(XL). What is the upper bound on the joint entropy H(X1, X2, . . . , Xn) of all these random variables, and under what condition will this upper bound be reached? What is the lower bound on the joint entropy H(X1, X2, . . . , Xn)? [3 marks] (c) If discrete symbols from an alphabet S having entropy H(S) are encoded into blocks of length n symbols, we derive a new alphabet of symbol blocks S n . If the occurrence of symbols is independent, then what is the entropy H(S n ) of this new alphabet of symbol blocks? [2 marks] (d) Consider an asymmetric communication channel whose input source is the binary alphabet X = {0, 1} with probabilities {0.5, 0.5} and whose outputs Y are also this binary alphabet {0, 1}, but with asymmetric error probabilities. Thus an input 0 is flipped with probability , but an input 1 is flipped with probability , giving this channel matrix p (i) Give the probabilities of both outputs, p(Y = 0) and p(Y = 1). [2 marks] (ii) Give all the values of (, ) that would maximise the capacity of this channel, and state what that capacity then would be. [3 marks] (iii) Give all the values of (, ) that would minimise the capacity of this channel, and state what that capacity then would be. [3 marks] (e) In order for a variable length code having N codewords with bit lengths 1 mark] (f ) The information in continuous signals which are strictly bandlimited (lowpass or bandpass) is quantised, in that such continuous signals can be completely represented by a finite set of discrete samples. Describe two theorems about how discrete samples suffice for exact reconstruction of continuous bandlimited signals, even at all the points between the sampled values. [4 mark

(a) A two state Markov process emits the letters {A, B, C, D, E} with the probabilities shown for each state. Changes of state can occur when some of the symbols are generated, as indicated by the arrows. 4.2 Information sources with memory We will wish to consider sources with memory, so we also consider Markov processes. Our four event process (a symbol is generated on each edge) is shown graphically together with a two state Markov process for the alphabet fA, B, C, D, Eg in gure 17. We can then solve for the state occupancy using ow equations (this example is trivial).

ess with states fS 1; S2; : : :Sng, with transition probabilities pi(j) being the probability of moving from state Si to state Sj (with the emission of some symbol). First we can dene the entropy of each state in the normal manner: Hi = X j pi(j) log2 pi(j) and then the entropy of the system to be the sum of these individual state entropy values weighted with the state occupancy (calculated from the ow equations):

Pipi(j) log pi(j) (45) Clearly for a single state, we have the entropy of the memoryless source. 4.3 The Source Coding theorem Often we wish to eciently represent the symbols generated by some source. We shall consider encoding the symbols as binary digits. 19 (i) What are the state occupancy probabilities? [1 mark] (ii) What is the probability of the letter string AD being emitted? [1 mark] (iii) What is the entropy of State 1, what is the entropy of State 2, and what is the overall entropy of this symbol generating process? [5 marks] (b) A fair coin is secretly flipped until the first head occurs. Let X denote the number of flips required. The flipper will truthfully answer any "yes-no" questions about his experiment, and we wish to discover thereby the value of X as efficiently as possible. (i) What is the most efficient possible sequence of such questions? Justify your answer. [2 marks] (ii) On average, how many questions should we need to ask? Justify your answer. [2 marks] (iii) Relate the sequence of questions to the bits in a uniquely decodable prefix code for X. [1 mark] (c) Define complex Gabor wavelets, restricting yourself to one-dimensional functions if you wish, and list four key properties that make such wavelets useful for encoding and compressing information, as well as for pattern recognition. Explain how their self-Fourier property and their closure under multiplication (i.e. the product of any two of them is yet again a Gabor wavelet) gives them also closure under convolution. Mention one disadvantage of such wavelets for reconstructing data from their projection coefficients. [8 mark

(a) Consider an alphabet of 5 symbols whose probabilities are as follows: A B C D E 1 16 1 4 1 8 1 16 1 2 One of these symbols has been selected at random and you need to discover which symbol it is by asking 'yes/no' questions that will be truthfully answered. (i) What would be the most efficient sequence of such questions that you could ask in order to discover the selected symbol? [2 marks] (ii) By what principle can you claim that each of your proposed questions in the sequence is maximally informative? [2 marks] (iii) On average, how many such questions will need to be asked before the symbol is discovered? What is the entropy of the symbol set? [2 marks] (iv) Construct a uniquely decodable prefix code for the symbols. Explain why it is uniquely decodable and why it has the prefix property. [2 marks] (v) Relate the bits in the code words forming your prefix code to the 'yes/no' questions that you proposed in (i). [2 marks] (b) Explain how the bits in an IrisCode are set by phase sequencing. Discuss how quantisation of the complex plane into phase quadrants sets each pair of bits; why it is beneficial for quadrant codes to form a Gray Code; how much entropy is thereby typically extracted from iris images; and why such bit sequences enable extremely efficient identity searches and matching. [5 marks] (c) Consider a noisy analog communication channel of bandwidth = 1 MHz, which is perturbed by additive white Gaussian noise whose total spectral power is N0 = 1. Continuous signals are transmitted across such a channel, with average transmitted power P = 1,000. Give a numerical estimate for the channel capacity, in bits per second, of this noisy channel. Then, for a channel having the same bandwidth but whose signal-to-noise ratio P N0 is four times better, repeat your numerical estimate of capacity in bits per second. [5 marks]

Continuous Mathematics

The complex form of the Fourier series is:

where ck is a complex number and ck = ck.

(a) Prove that the complex coeffiffifficient, ck, encodes the amplitude and phase

coeffiffifficients, Ak and k, in the alternative form:

An interprocess communication environment is based on synchronous message

passing. A server is to be designed to support a moderate number of simultaneous

client requests.

Clients send a request message to the server, continue in parallel with server

operation, then wait for the server's reply message.

Discuss the design of the server's interaction with the clients. Include any problems

you foresee and discuss alternative solutions to them. [20 marks]

2CST.2001.4.3

3 Further Java

(a) Describe how mutual-exclusion locks provided by the synchronized keyword

can be used to control access to shared data structures. In particular you

should be clear about the behaviour of concurrent invocations of difffferent

synchronized methods on the same object, or of the same synchronized method

on difffferent objects. [6 marks]

(b) Consider the following class defifinition:

class Example implements Runnable {

public static Object o = new Object();

int count = 0;

public void run() {

while (true) {

synchronized (o) {

Show how to start two threads, each executing this run method. [2 marks]

(c) When this program is executed, only one of the count fifields is found to

increment, even though threads are scheduled preemptively. Why might this

be? [2 marks]

(d) Defifine a new class FairLock. Each instance should support two methods, lock

and unlock, which acquire and release a mutual exclusion lock such that calls

to unlock never block the caller, but will allow the longest-waiting blocked

thread to acquire the lock. The lock should be recursive, meaning that the

thread holding the lock may make multiple calls to lock without blocking.

The lock is released only when a matched number of unlock operations have

been made.

You may wish to make use of the fact the Thread.currentThread() returns

the instance of Thread that is currently executing. [10 marks]

3

[TURN OVERCST.2001.4.4

4 Compiler Construction

Consider the following grammar giving the concrete syntax of a language:

where C repeatwhile E has the same meaning as do C while E in C or Java.

(a) List the terminals and non-terminals of this grammar and explain the

signifificance of S. [3 marks]

(b) Identify any ambiguities in the above grammar and rewrite it to remove them,

ensuring that your new grammar generates exactly the same set of strings.

[4 marks]

(c) Specify a suitable abstract syntax, for example by giving a type declaration

in a programming language of your choice, which might be used to hold parse

trees for this language. [3 marks]

(d) Give either a recursive descent parser or a characteristic fifinite state machine

(e.g. for SLR(1)) with associated parser for your grammar. Your parser need

not return a parse treeit suffiffiffices for your parser either to accept or to reject

the input string. [10 marks]

4CST.2001.4.5

5 Data Structures and Algorithms

(a) Outline how you would determine whether the next line segment turns left or

right during the Graham scan phase of the standard method of computing the

convex hull of a set of points in a plane. [5 marks]

(b) Describe in detail an effiffifficient algorithm to determine how often the substring

ABRACADABRA occurs in a vector of 106 characters. Your algorithm should be

as effiffifficient as possible. [10 marks]

(c) Roughly estimate how many character comparisons would be made when your

algorithm for part (b) is applied to a vector containing 106 characters uniformly

distributed from the 26 letters A to Z. [5 marks]

6 ECAD

(a) When designing clocked circuits there are times when asynchronous inputs

have to be sampled which may result in metastable behaviour in state holding

elements. How might metastability be avoided when sampling asynchronous

inputs? [5 marks]

(b) An optical shaft encoder (e.g. used on the internal rollers of a mechanical

mouse) consists of a disk with an evenly spaced alternating transparent and

opaque grating around the circumference. Two optical sensors are positioned

such that when one sensor is at the middle of an opaque region, the other

is at the edge. Consequently, the following Gray code sequence is produced,

depending upon the direction of rotation:

positive rotation

negative rotation

A shaft decoder module is required to convert the Gray code into an 8-bit

position. The 8-bit position should be incremented every time the input

changes from one state to another in a positive direction (e.g. from 00 to

01, or from 10 to 00). Similarly, the 8-bit position should be decremented

every time the input changes from one state to another in a negative direction

(e.g. from 00 to 10, or from 01 to 00).

Write and comment a Verilog module which performs the function of a shaft

decoder. [15 marks]

5

[TURN OVERCST.2001.4.6

7 Operating System Functions

(a) In the context of virtual memory management:

(i) What is demand paging? How is it implemented? [4 marks]

(ii) What is meant by temporal locality of reference? [2 marks]

(iii) How does the assumption of temporal locality of reference inflfluence page

replacement decisions? Illustrate your answer by brieflfly describing an

appropriate page replacement algorithm or algorithms. [3 marks]

(iv) What is meant by spatial locality of reference? [2 marks]

(v) In what ways does the assumption of spatial locality of reference inflfluence

the design of the virtual memory system? [3 marks]

(b) A student suggests that the virtual memory system should really deal with

"objects" or "procedures" rather than with pages. Make arguments both for

and against this suggestion. [4 and 2 marks respectively]

.

where h(k)(z) is the result of k repeated applications of the function h to initial

argument z. [4 marks]

(c) Hence or otherwise show that for all n N, gn(y) is a PR function. [4 marks]

(d) Deduce that Ackermann's function f(x, y) is a TR function. [3 marks]

(e) Is Ackermann's function PR? [1 mark]

7

[TURN OVERCST.2001.4.8

9 Numerical Analysis I

(a) What is meant by a symmetric positive defifinite matrix ? [3 marks]

(b) Verify that A = 2 1

1 2 is positive defifinite. [4 marks]

(c) The Choleski factorisation A = LDLT is to be applied to the solution of

upper triangular system of equations needed to complete the solution.

[4 marks]

(d) Solve these equations. [2 marks]

(e) What is meant by the order of convergence of an iterative process? [1 mark]

(f ) State the Newton-Raphson formula for solving f(x) = 0 for scalar x. What is

the order of convergence of this method? [2 marks]

(g) This method is used to solve f(x) = x2 4 = 0 using IEEE Double Precision

with a certain starting value x0. It is found that the third iterate x3 ' 2.0006,

and x4 ' 2.00000009. Very roughly, how many signifificant decimal digits of

accuracy would you expect in x5? Explain your answer. [4 marks]

8CST.2001.4.9

10 Computer Graphics and Image Processing

(a) Describe an algorithm to draw a straight line using only integer arithmetic.

You may assume that the line is in the fifirst octant, that the line starts and

ends at integer co-ordinates, and that the function setpixel(x, y) turns on the

pixel at location (x, y). [8 marks]

(b) Describe Douglas and Pucker's algorithm for removing superflfluous points from

a line chain. [10 marks]

(c) Under what circumstances would it be sensible to employ Douglas and Pucker's

algorithm? [2 marks]

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

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:

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. [6 marks]

Describe an O(n log(n)) algorithm based on a variation of merge sort to fifind the

closest pair of a given set of points lying in a plane. You may assume that the set

of points is given as a linked list of (x, y) coordinates. [8 marks]

Carefully prove that your algorithm can never take longer than O(n log(n)).

[6 marks]

Modify, with explanation, your algorithm to fifind the pair of points with minimum

Manhattan distance. The Manhattan distance between points (x1, y1) and (x2, y2)

is |x1 x2| + |y1 y2|. [6 marks]

1

[TURN OVERCST.2000.6.2

2 Computer Design

Why are the following statements fallacies?

(a) MIPS is an accurate measure for comparing performance among computers.

[5 marks]

(b) A benchmark is a typical program which accurately predicts the performance

of all other applications. [5 marks]

(c) Complex instruction set computers minimise the semantic gap between

machine code and high-level languages, thereby making applications run more

quickly. [5 marks]

(d) Data caches always improve processor throughput. [5 marks]

3 Digital Communication I

Compare circuit switching and packet switching, paying attention to channel

characteristics and resource effiffifficiency. [7 marks]

What is wave division multiplexing (WDM)? Is it more like circuit switching or

packet switching and why? [7 marks]

Wave length conversion is the process, either optical or optical-electronic-optical,

of receiving a signal on one wavelength and transmitting on another.

How does wave length conversion ease the problem of routing optical carriers in a

network? [3 marks]

"The huge capacity of WDM systems will mean that IP becomes redundant."

Discuss. [3 marks]

2CST.2000.6.3

4 Computer Graphics and Image Processing

Give an algorithm for drawing the part of a circle which lies in the fifirst octant.

Assume that the circle has integer radius and is centered at the origin. Assume

that you have a function setpixel(x, y) which turns on pixel (x, y). [10 marks]

Derive a matrix, or a product of matrices, to perform a clockwise 2D rotation of

arbitrary angle, , about an arbitrary point, (xc, yc). [4 marks]

Provide an algorithm to ascertain whether the Bezier curve defifined by P1P2P3P4

lies within some tolerance, , of the straight line segment, P1P4, which joins the

Bezier curve's end points. Your algorithm must return false if the Bezier curve is

outside the tolerance; it must return true if the curve is well inside the tolerance;

it may return either true or false if the curve is inside, but not well inside, the

tolerance. [6 marks]

SECTION B

5 Comparative Programming Languages

Give a brief summary of the main syntactic constructs found in the programming

language Smalltalk. Other languages often have the conditional constructs

if-then-else and while. Show how these two constructs can be defifined in Smalltalk.

[8 marks]

Illustrate the use of Smalltalk by showing how you would defifine a method to

compute the factorial of an integer. [8 marks]

Although Smalltalk was originally designed to be an interpretive language, modern

implementations are dramatically more effiffifficient. Brieflfly outline what techniques

might have been used to make this improvement. [4 marks]

3

[TURN OVERCST.2000.6.4

6 Compiler Construction

Describe how a parse tree can be translated into a sequence of assembly language

instructions based on a pattern matching graph derived from a set of tree rewriting

rules where each rule has a cost and a corresponding fragment of code. Illustrate

your answer using the following rules:

Ri = Kk LDI Ri,Kk Cost 2

Ri = add(Ri,Kk) ADDI Ri,Kk Cost 3

Ri = add(Ri,Rj) ADD Ri,Rj Cost 3

Ri = add(Ri,add(Rj,Kk)) ADD Ri,Rj,Kk Cost 4

applied to the following parse tree:

add(K1,add(add(K2,add(K3,K4)),add(K5,K6)))

[15 marks]

Discuss the advantages and disadvantages of this approach to code generation.

[5 marks]

7 Prolog for Artifificial Intelligence

One of the regulations of the International Rugby Board (IRB) states that for a

player to be eligible to play for a given country, the player's father or mother or

grandfather or grandmother must have been born in that country. Assume that

there is a complete genealogical database consisting of Prolog clauses of the form

person(P, B, F, M), where P is a person's name, B is the country of P's birth, F is

their father's name and M is their mother's name. For example, the clause

person(bruce, australia, rhodri, bronwyn).

might appear in such a database. Further assume that names in the database are

constructed so as to refer uniquely to individuals. Write Prolog clauses defifining

the predicate eligible such that goals of the form eligible(P,C) succeed if and only if

person P is eligible to play for country C according to the above regulation.

[10 marks]

Given a list of players on a given country's team, defifine a predicate checkteam

that will check each member of the team for eligibility according to the eligible

predicate, and furthermore check that each player appears on the list only once.

The checkteam goal will fail if any player is ineligible or if any player is listed more

than once. [10 marks]

4CST.2000.6.5

8 Databases

Describe the basic architecture of the ODMG standard for Object Data

Management. [10 marks]

What support is provided for transactions? What locking modes are available, and

how are they used by the database runtime systems? [4 marks]

The query language OQL is recognised as a standard by the Object Management

Group (OMG). To what extent is it similar to SQL, and in what ways does it

diffffer? [6 marks]

SECTION C

9 Semantics of Programming Languages

What does it mean to say that two confifigurations of a labelled transition system

are bisimilar? [3 marks]

Describe a labelled transition system for a language of communicating processes

with input prefifixing (c(x). P), output prefifixing (

ch Ei . P), an inactive process (0),

choice (P + P0 ), parallel composition (P|P0 ) and channel restriction ( c . P). You

may assume there is a relation E n which defifines when an integer expression E

evaluates to an integer n. [7 marks]

For each of the following pairs of processes, say whether or not they are bisimilar.

Justify your answer in each case.

ch 1i . P)), where c does not occur in P

[6 marks]

10 Foundations of Functional Programming

Give as simple a set of rules as you can for transforming lambda calculus to a form

where there are no bound variables mentioned, but where there are many instances

of the three standard combinator constants S, K and I. [6 marks]

Describe tree-rewrites suitable for reducing expressions written in terms of

combinators. [6 marks]

The server stores the ongoing status of every housemate as a line of text. For instance, housemate Eva could set her status to "Gone to the test corridor." Messages are passed among clients and the server as message strings sent over TCP. The new line character is utilized only as the last person in each message. On association with the server, a client can possibly (I) question the situation with a client by sending the client's name to the server as a string (and the server answers with the ongoing status message), or (ii) set the situation with a client by sending the client's name trailed by a colon and the new status message. For instance, "Eva:Gone to the test lobby." sets the status message for Eva. (a) Implement a status server in Java. The server ought to run endlessly, answering client demands. When a client demand has been satisfied, the server ought to close the association. You might expect current status messages are lost in the event that the server is restarted and you don't have to deal with exemptions. [8 marks] (b) One housemate recommends the server and client ought to convey by serializing Java protests as opposed to sending messages as message. (I) Describe in words the progressions you would make to your server execution to send messages as serialized Java objects. [3 marks] (ii) List two benefits and two drawbacks of an execution in light of serialized Java objects as opposed to sending messages as message. [4 marks] (c) Another housemate proposes that the server shouldn't close the client's association in the wake of noting the solicitation. Rather the association ought to stay open until the client sends another solicitation or shuts the association. Portray in words what transforms you would have to make to your execution to some degree (a) to accomplish this and remark on the benefits and detriments of this thought. [5 marks] 8 CST.2014.3.9 8