Consider an object's surface reflectance map ?(i, e, g) specifying the amount of incident light reflected towards a camera from each point on the surface, where the angle of the illuminant (a point source) relative to the local surface normal N is i, the angle relative to N of a ray of light re-emitted from the surface is e, and the angle between the emitted ray and the illuminant is g. (i) For what kind of surface is the reflectance map simply ?(i, e, g) = cos(i)? Name this type of surface and describe its key properties. [3 marks] (ii) For what kind of surface does the reflectance map simplify to ?(i, e, g) = 1 if i = e and both i and e are co-planar with the surface normal N, and ?(i, e, g) = 0 otherwise? Name this type of surface and describe its key properties. [3 marks] (iii) For what kind of surface does the reflectance map depend only on the ratio of the cosines of the angles of incidence and emission, cos(i)/ cos(e), but not upon their relative angle g nor upon the surface normal N? Give an example of such an object, and explain the consequence of this special reflectance map for the object's appearance. [3 marks] (iv) For the more general class of object surfaces described by the following reflectance map, with 0 ? s ? 1, ?(i, e, g) = s(n + 1)(2 cos(i) cos(e) ? cos(g))n 2 + (1 ? s) cos(i) which term is the specular component, and which term is the matte component? What fraction of light is emitted specularly, and what does the parameter n represent? Describe the behaviour of parameters s and n around regions of a person's face where the skin might be oily or sweaty and places where it is not, and how this impacts recognition. [4 marks] (b) Using the second finite difference operator -1 2 -1 for edge detection in an image, show how the pixel values in the top row are changed by discrete convolution with this operator: insert the output values in the bottom row. . . . 0 0 0 0 5 5 5 5 5 0 0 0 0 . . . [3 marks] (c) Show how Bayesian inference enhances face recognition when a face contains highly distinctive features, as exploited by caricature. Suppose some facial feature x is unusual so its probability P(x) is small, and that for each k th face described as class Ck we know the class-conditional likelihood P(x|Ck) of observing this unusual feature, but a priori all the classes are equiprobable. Use Bayes' Rule to show how the correct classification of face Ck given its unusual feature x acquires higher probability P(Ck|x).

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

denotational semantics semantic domain environment call-by-value call-by-need (lazy evaluation) call-by-reference gives meaning to a langu: a mapping from names tc [Choose ] [Choose ] [Choose ] [Choose ] > < >