Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly

Fantastic news! We've Found the answer you've been seeking!

Question:

Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly explain what a Reader is in the context of reading characters from data. [3 marks] A novice programmer has written the following copying program which is intended simply to read characters from data one at a time and to write them out. public class Copying { public static void main(String[] args) { int ch; while ( Unfortunately this program causes a compile-time error. Explain what the problem is and modify the code so that the program compiles. [3 marks] (d) The amended program correctly copies data in simple cases but is found to fail when exotic characters are encountered. Why is this? [3 marks] (e) By exploiting a Reader, rewrite the program so that exotic characters no longer cause any problems. [8 marks]

(a) Suppose that (D, v) is a poset which is chain-complete but does not have a least element, and that f : D D is a continuous function. (i) Give an example of such (D, v) and f for which f has no fixed point. [1 mark] (ii) If d D satisfies d v f(d), prove that there is a least element e D satisfying d v e = f(e). [Hint: consider the method used to prove Tarski's fixed point theorem.] [7 marks] (b) (i) Define the notion of contextual equivalence for the language PCF. (You need not describe the syntax and semantics of PCF.) [2 marks] (ii) State the compositionality, soundness and adequacy properties of the denotational semantics of PCF. Explain why they imply that any two closed PCF terms of the same type with equal denotations are contextually equivalent. [8 marks] (iii) Give, without proof, an example of two contextually equivalent PCF terms that have unequal denotation. [2 marks]

Explain why the Church-Rosser theorem implies that there are -terms that are not equal to each other. [2 marks] Suppose the following reduction rule is added to the -calculus: xy.x xy.y Show that in the resulting calculus, all terms are equal. [3 marks] Let A = xy.y(xxy) and = AA. Show that is a fixed-point combinator. [3 marks] Assume an encoding of lists where [a1, . . . , am] is represented Use the fixed-point combinator to obtain a -term rev such that: rev[a1, . . . , am] = [am, . . . , a1] You may assume a -term representation of the booleans and of ordered pairs, but you should define any other terms you require. [12 marks]

(a) (i) A variable-length, uniquely decodable code that has the prefix property and whose N binary code word lengths ar must satisfy what condition with these code word lengths? (Give an expression for the condition, and its name, but do not attempt to prove it.) [3 marks] (ii) Construct an efficient, uniquely decodable binary code, having the prefix property and having the shortest possible average code length per symbol, for an alphabet whose five letters appear with these probabilities: Letters the shortest possible code length per symbol? Demonstrate numerically that your code satisfies this optimality condition. [3 marks] (b) (i) Explain how autocorrelation can remove noise from a signal that is buried in noise, recovering a clean signal. For what kinds of signals, and for what kinds of noise, will this work best, and why? What class of signals can be recovered perfectly by autocorrelation? Begin your answer by writing down the integral that defines the autocorrelation of a signal f(x). [3 marks] (ii) Some sources of noise are additive (the noise is just superimposed onto the signal), but other sources of noise are multiplicative in their effect on the signal. For which type would the autocorrelation clean-up strategy be more effective, and why? In the case of additive noise where noise and signal occupy different frequency bands, what other strategy could allow recovery of a clean signal? [3 marks] (c) (i) If a continuous signal f(t) is modulated by multiplying it with a complex exponential wave exp(it) whose frequency is , what happens to the Fourier spectrum of the signal? Name a very important practical application of this principle, and explain why modulation is a useful operation. How can demodulation then recover the original signal? [3 marks] (ii) Which part of the 2D Fourier Transform of an image, the amplitude spectrum or the phase spectrum, is indispensable in order for the image to be intelligible? Describe a demonstration that proves this. [2 marks]

(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(yk|xj ): 1 1 (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 {n1, n2, n3, , nN } to satisfy the prefix property, what condition must be satisfied? (Express the condition, but do not try to prove it.) [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). Figure 17: Graphs representing memoryless source and two state Markov process In general then we may dene any nite state process 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 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:

f(x) =

ckei2kx

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:

Ak cos(2kx k)

[10 marks]

(b) What is special about the case k = 0? [2 marks]

f(x):

f(x) = f(x + T), x

can be obtained from the Fourier transform, FL(), of the related function,

otherwise

[8 marks]

2 Concurrent Systems

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]

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]

[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]

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]

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 d comment a Verilog module which performs the function of a shaft

decoder. [15 marks]

[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]

6CST.2001.4.7

8 Computation Theory

(a) Defifine precisely what is meant by the following:

(i) f(x1, x2, . . . xn) is a Primitive Recursive (PR) function of arity n.

[5 marks]

(ii) f(x1, x2, . . . xn) is a Total Recursive (TR) function of arity n. [3 marks]

(b) Ackermann's function is defifined by the following recursive scheme:

f(0, y) = S(y) = y + 1

f(x + 1, 0) = f(x, 1)

f(x + 1, y + 1) = f(x, f(x + 1, y))

For fifixed n defifine

gn(y) = f(n, y).

Show that for all n, y N,

gn+1(y) = gn(y+1)(1),

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

argument z. [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]

[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]

The next step in the method is to solve Ly = b to get y = 1

. Form the

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]

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]

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]

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]

[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

Iikd(Li N) +X

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]

[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]

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]

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]

[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.

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]

[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

(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]

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]

[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]

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]

[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]

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]

[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]

Explain how you might deal with the issue of keeping track of the values of bound

variables if you were to interpret lambda calculus directly. [8 marks]

[TURN OVERCST.2000.6.6

11 Logic and Proof

For each of the given pairs of terms, give a most general unififier or indicate why

none exists. (Here x, y, z are variables while a, b are constant symbols.)

h(x, y, x) and

h(y, z, u)

h(x, y, z) and

h(f(y), z, x)

h(x, y, b) and

h(a, x, y)

h(x, y, z) and

h(g(y, y), g(z, z), g(u, u))

[4 marks]

A standard unifification algorithm takes a pair of terms t1 and t2 and returns a

substitution such that t1 = t2. Show how this algorithm can be used to fifind

the unififier of several (n > 2) terms t1, t2, . . . , tn: a substitution such that

t1 = t2 = = tn. Indicate how the unififier is constructed from the unififiers

of n 1 pairs of terms. (Assume that all required unififiers exist and ignore the

question of whether the unififiers are most general.) [6 marks]

Prove using resolution the formula

(a) (i) A variable-length, uniquely decodable code that has the prefix property and whose N binary code word lengths are n1 n2 n3 nN must satisfy what condition with these code word lengths? (Give an expression for the condition, and its name, but do not attempt to prove it.) [3 marks] (ii) Construct an efficient, uniquely decodable binary code, having the prefix property and having the shortest possible average code length per symbol, for an alphabet whose five letters appear with these probabilities: Letter A B C D E Probability 1/2 1/4 1/8 1/16 1/16 [3 marks] (iii) How do you know that, on average, for samples drawn from this alphabet, your code uses the shortest possible code length per symbol? Demonstrate numerically that your code satisfies this optimality condition. [3 marks] (b) (i) Explain how autocorrelation can remove noise from a signal that is buried in noise, recovering a clean signal. For what kinds of signals, and for what kinds of noise, will this work best, and why? What class of signals can be recovered perfectly by autocorrelation? Begin your answer by writing down the integral that defines the autocorrelation of a signal f(x). [3 marks] (ii) Some sources of noise are additive (the noise is just superimposed onto the signal), but other sources of noise are multiplicative in their effect on the signal. For which type would the autocorrelation clean-up strategy be more effective, and why? In the case of additive noise where noise and signal occupy different frequency bands, what other strategy could allow recovery of a clean signal? [3 marks] (c) (i) If a continuous signal f(t) is modulated by multiplying it with a complex exponential wave exp(it) whose frequency is , what happens to the Fourier spectrum of the signal? Name a very important practical application of this principle, and explain why modulation is a useful operation. How can demodulation then recover the original signal? [3 marks] (ii) Which part of the 2D Fourier Transform of an image, the amplitude spectrum or the phase spectrum, is indispensable in order for the image to be intelligible? Describe a demonstration that proves this. [2 marks]

True or false 27. Java compiler does not ignore white spaces such as spaces, tabs, or blank lines in a Java program. 28. The same variable name(s) can be declared and used within different methods. 29. In Java, 3*b'+1 is a valid expression. 30. In Java x++ is equivalent to x=x+1. 31. In Java, int x-2.5; is a valid statement. 32. The data type of the Java expression (int) 2.5 is double. 33. A method in Java can return more than one value. 34. A method can take more than one parameter. 35. In Java, 3+ "abc"+2*3 is a valid statement. 36. Method A can call another method B which in turn calls the method A again in Java 37. More than two for loops can be nested within each other 38. In Java, if a=4, b6, then statements a=b; and b=a; will produce the result that a=6 and b=4. 39. Identifier_S is valid in Java. 40. Java biterode for the same nroaram is dififorent for difiorent nlatform

7.6 LAB: Warm up: Online shopping cart (Part 1) (1) Create three files to submit: Item ToPurchase.h - Struct definition and related function declarations Item ToPurchase.c- Related function definitions main.c-main function Build the ItemToPurchase struct with th following specifications: Data members (3 pts) char itemName int item Price int itemQuantity Related functions MakeltemBlanko (2 pts) Has a pointer to an item To Purchase parameter. Sets item's name = "hone, item's price = 0, item's quantity = 0 PrintltemCost Has an Item To Purchase parameter. Ex of PrintitemCost(output: Bottled water 10 $1= $10 (2) In main) prompt the user for two items and create two objects of the item ToPurchase struct. Before prompting for the second item, enter the following code to allow the user to input a new string. cis declared as a char. (2 pts) c = getchar0; while (c != n' && cl= EOF) C = getchar0; { Item 1 Enter the item name: Chocolate Chips Enter the item price: Enter the item quantity: Item 2 Enter the item name: Bottled Water Enter the item price: Enter the item quantity: (3) Add the costs of the two items together and output the total cost. (2 pts) Ex: TOTAL COST Chocolate Chips 1 $3 = 53 Bottled Water 10@ $1 = $10 Total: $13

(a) (i) Define the notion of admissible subset of a domain and state Scott's fixed point induction principle. [4 marks] (ii) Let (D, vD) and (E, vE) be domains and let f : D E and g : E D be continuous functions. Using Scott's fixed point induction principle prove (A) fix (f g) vE f

fix (g f) (B) f

fix (g f) vE fix (f g) [8 marks] (b) (i) Define the contextual-equivalence relation P1 =ctx P2 : for pairs of closed PCF expressions P1, P2 and a PCF type . [2 marks] (ii) Prove or disprove the following statement. For every pair of PCF types , and every pair of closed PCF expressions M of type and N of type , fix fn y : . M(N(y)) =ctx M

fix fn x : . N(M(x)) : [6

CIS 22B Lab 3 itty Bitty Airftreight (1BA) 200 Points Topics: Friend functions Copy constructor Lab 3.1 Create your objects in the stack (not on the heap). Add a friend function, kilotopound, which will convert kilograms to pounds. Change your weight mutator to ask whether weight is input in kilograms or pounds. If it is kilograms, call the friend function kilotopound to convert it to pounds and return pounds. There are 2.2 pounds in one kilogram. Create an object on the stack with the following information: uld- Container abbreviation - AYK uldid - AYK689431B aircraft - 737 weight 1654 Kilograms destination PDX Output the contents of your object. Lab 3.2 Utilizing Lab 3.1 code, add a copy constructor. Create object on the stack using the following data: uld - Container abbreviation - ABB uldid - ABB315451B aircraft - 737 weight - 1156 destination BUR Copy the first object using a copy constructor. Output the contents of both objects.

In this project, you will design and implement an algorithm to determine the next greater element of an element in an array in On) time, where 'n' is the number of elements in the array. You could use the Stack ADT for this purpose. The next greater element (NGE) for an element at index i in an array A is the element that Occurs at index j<) such that A] < A] and A] 2 AK for all k fi+ 1.. -1]. That is, indexj > i) is the first index for which AU] > A]. If no such indexj exists for an element at index i, then the NGE for the element A) is considered to be -1. For example: if an array is {1, 15, 26, 5, 20, 17, 36, 28, then the next greater element (NGE) of the elements in the array are as follows:

kindly answer all the questions