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.

(a)

ch 1i .((

ch 2i . 0) + (

ch 3i . 0)) and (

ch 1i . ch 2i . 0) + (

ch 1i . ch 3i . 0) [4 marks]

(b) P and c .((c(x). 0)|(

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]

5