The simulator will be used to study how cyclists
ride at night in low light conditions and in particular how well they can spot
hazards. A typical, non-HDR LCD display will be used for the simulator.
(i) What perceptual effects would you need to simulate in the tone-mapping
operator?
(ii) Illustrate a high-level design of such an operator on a diagram showing
major processing blocks. Use a similar notation to that used in the lectures:
block stating the purpose and output of each processing block. Note
that the problem can be solved in many ways and there is no single correct
solution.

 

provide answers to every question

Total Store Order (TSO) is a widely implemented memory consistency model.
How does TSO differ from Sequential Consistency (SC)? [4 marks]
(b) Describe an execution of a simple program that is legal under TSO but not SC.
The simple program should consist of two threads, each thread consisting of a
small number of load and store instructions accessing memory locations X and
Y. [3 marks]
(c) Would the use of a coalescing write buffer violate TSO? Justify your answer.

(d) Consider a chip-multiprocessor where each core supports simultaneous multithreading (SMT). Furthermore, each processor core has a write-through L1 data
cache. Could multicopy atomicity be supported in such a design? [6 marks]
(e) Consider a chip-multiprocessor with two cores P1 and P2. Coherence is
maintained using a MESI protocol with support for Bus Upgrade (BusUpgr)
transactions to avoid unnecessary data transfers (i.e. when moving from state S
to M). Why might a processor that initially makes a BusUpgr request have to
change the request to a Read-Exclusive (BusRdX) before it even wins access to
the shared bus?

 

In this question you should ensure that your predicates behave appropriately with
backtracking. You may not make use of extra-logical built-in predicates such as
findAll. Use of the cut operator is permitted unless specified otherwise. You may
ignore the possibility of overflow or division by zero.
(a) A term can either be an atom, variable or a compound term. Define each of
these. [3 marks]
(b) Euclid's algorithm for computing the greatest common divisor of two integers
can be implemented in ML as:
fun gcd(a,0) = a
| gcd(a,b) = gcd(b, a mod b);
Provide an implementation in Prolog without using the cut operator.
[4 marks]
(c) We can represent fractions using the compound term div/2. For example
div(1,3) represents 1
3
.
Implement a predicate simplify which transforms a fraction into its smallest
exact representation. For example, simplify(div(8,4),B) should unify B with
2, and simplify(div(4,8),A) should unify A with div(1,2). Your predicate
should avoid unnecessary computation. [5 marks]
(d) We can also represent arithmetic expressions involving addition, subtraction,
multiplication and division. For example, the expression 3 5
2−1 + 4 is represented
as add(mul(3,div(5,sub(2,1))),4).
Implement a predicate reduce which reduces an arithmetic expression to its
smallest exact representation e.g. reduce(add(div(1,2),div(1,4)),A) should
unify A with div(3,4)

This question deals with stochastic processes {N(t), t ≥ 0} where N(t) represents
the number of events in the time interval [0, t].
(a) (i) Define a Poisson process {N(t), t ≥ 0} of rate λ > 0. [2 marks]
(ii) Show that N(t) ∼ Pois(λt) for each fixed t > 0. You may use the result
that limn→∞(1 − x/n)
n = e
−x without proof. [4 marks]
(iii) Let X1 be the time of the first event of the Poisson process N(t). Show
that X1 ∼ Exp(λ). [2 marks]
(iv) Now given that N(t) = 1 derive the distribution of the time of the single
event in [0, t]. [4 marks]
(b) Suppose that events of a Poisson process of rate λ are independently selected at
random with probability p > 0. Show that the process of selected events is also
a Poisson process and establish its rate. [2 marks]
(c) Describe how your result from part (b) can be used to simulate a nonhomogeneous Poisson process whose rate function λ(t) is such that λ(t) ≤ λ
∗
for all t ≥ 0.

 

Various languages provide a built-in 'eval' operator which evaluates an
expression passed as an argument. Discuss the extent to which this: (i) fits
with existing language features, naming languages or classes of languages for
which it is easy or hard to implement; (ii) easily deals with variable scoping;
(iii) is a security risk. [4 marks]
(b) (i) Explain and justify what goes wrong when the following code is given to a
Standard ML system:
fun id x = x;
val fnlist = ref [id];
fnlist := (fn x=>x+1) :: !fnlist;
fnlist := Math.sqrt :: !fnlist;
print (hd(!fnlist)(1))
(ii) Explain, giving an example, a related problem involving polymorphic
exceptions.
[5 marks]
(c) (i) Explain the concept of a "value type" in an object-oriented language,
including which, if any, primitive and non-primitive types in Java can be
seen as value types.
(ii) Discuss to what extent a programmer can use final to create value types in
Java, and whether this implementation gives the expected space and time
usage. [Hint: You may find it useful to discuss arrays of complex numbers.]
[5 marks]
(d) An implementation of finite sets of natural numbers in Standard ML uses int
list as its representation. However, certain client code has been found to be
buggy, because it misuses :: to add elements (creating duplicates) and length
to obtain the number of elements (miscounting duplicates).
(i) Explain how ML modules might be helpful for addressing such bugs.
(ii) Use the ML modules language to create a type natset which uses int list
internally but only exposes operations (a) to create an empty set, (b) to
(functionally) insert one (non-negative) element into a set, (c) to sum the
elements in a set, (d) to count the number of elements in a set. No other
operation may create or manipulate an natset value.
[6 marks]
3 (TURN OVER)
CST1.2018.7.4
2 Economics, Law and Ethics
(a) Describe the possible market failures affecting anti-virus software firms in the
late 1980s and early 1990s, when viruses were a new threat to computer systems
and dozens of firms started up to offer anti-virus software. [5 marks]
(b) Describe how the incentives facing anti-virus software firms had changed 10 years
later once the industry had consolidated into a handful of large firms. How might
this affect attacker behaviour? [5 marks]
(c) How will the incentives have changed in recent years with the spread of online
banking and crypto currencies? [5 marks]
(d) How do you expect the anti-virus industry to change as computing shifts from
PCs and laptops to phones and tablets? What about the impact of systems
embedded in durable consumer goods such as cars? [5 marks]
4
CST1.2018.7.5
3 Formal Models of Language
Consider the following grammar:
S → NP VP
NP → N S
NP → N
VP → V N
VP → V
N → {Alice, cats}
V → {saw, grinned}
(a) The grammar can be used to generate the following sentences:
(i) Alice saw cats
(ii) Cats Alice saw grinned
Draw derivation trees for both of these sentences. [2 marks]
(b) What is the longest sentence that can be generated by the grammar? Describe
this sentence. [2 marks]
(c) Is the language generated by the grammar a regular language? Provide a proof
for your answer. [8 marks]
(d) A psycho-linguistic experiment shows that, by the 2nd word in the sentence,
Part (a)(ii) is harder to process than the sentence Part (a)(i). Yngve
hypothesised that a speaker's short-term memory functions as a stack. Explain
how this hypothesis might account for the experimental results by drawing the
stack arising from a top-down parse of the two sentences. [4 marks]
(e) How might the sentence in Part (a)(ii) be altered so that it has the same meaning
but is easier to process? Explain your reasoning. [4 marks]
5 (TURN OVER)
CST1.2018.7.6
4 Further Graphics
(a) Here are two methods for implementing a cube using signed distance fields:
float methodOne(vec3 p) {
return max(max(abs(p.x), abs(p.y)), abs(p.z)) - 1;
}
float methodTwo(vec3 p) {
vec3 d = abs(p) - vec3(1);
return min(max(d.x, max(d.y, d.z)), 0.0)
+ length(max(d, 0.0));
}
One is preferable to the other for producing better images faster. Which one,
and why? [4 marks]
(b) Complete the code below to implement the signed distance field function for
a finite line segment with hemispherical end-caps (Figure 1) of arbitrary start
point, end point, and radius. [4 marks]
float lineSegment(vec3 p, vec3 start, vec3 end, float radius) {
// [YOUR CODE HERE]
}
float getSdf(vec3 p) {
return lineSegment(
p, vec3(-PI, 0, 0), vec3(PI, 0, 0), 0.5);
}
(c) Implement a version of getSdf() that doubles the height of your line segment
and translates it by −0.5 along the Z axis, to be centred at (0, 0, −0.5) (Figure
2). [4 marks]
(d) Implement a version of getSdf() that warps the original line segment into a
sine wave sin(X) (Figure 3). [4 marks]
(e) Modify getSdf() to render the sine wave model subtracted from the taller model
(Figure 4). [4 marks]
6
CST1.2018.7.7
Figure 1 Figure 2
Figure 3 Figure 4
Figure 1: A finite cylinder of radius 0.5 centred at (0, 0, 0) with hemispherical
end-caps, starting at (−π, 0, 0) and ending at (π, 0, 0).
Figure 2: The original finite cylinder has been enlarged to double its height on
the Y axis and has been translated in Z so that it is now centred at (0, 0, −0.5).
Figure 3: The original finite cylinder has been warped with a sine wave. Its
centre remains at (0, 0, 0) and its endpoints remain centred around (+/−π, 0, 0),
but in between its central axis falls to Y = −1 and rises to Y = 1.
Figure 4: The sine wave has been subtracted from the double-height cylinder.
(Note: Ground plane shown at Y = −1 for illustration purposes only)
 

Write C program with output:
1. Write  program to find Cartesian product of two sets.
Write recursive programs to find
a. Factorial
b. Power
c. Greatest common divisor

 

(a) Write a GLSL function dartboard() which takes as input a texture co-ordinate
texCoord which ranges from (0, 0) → (1, 1), and returns the colours of the
procedural texture for a black-and-white dartboard pattern of 16 squares around
and 8 squares in radius (see figure below). The background behind the dartboard
is gray.
vec3 dartboard(vec2 texCoord) {
// [YOUR CODE HERE]
}
[6 marks]
(b) What is . . .
(i) the formula for the face angle α(F, vi) of face F at vertex vi of a closed
manifold? [2 marks]
(ii) the formula for the angle deficit AD(v) of vertex v and its surrounding set
of faces {F}? [2 marks]
(iii) the formula for the Poincar´e Formula of a surface with genus g and Euler
characteristic χ? [2 marks]
(iv) the formula for Descartes' Theorem of Total Angle Deficit? [2 marks]
(c) Consider a closed manifold surface with total angle deficit −4π.
(i) If your hypothetical surface has 20 vertices and 20 faces then how many
edges must it have? [2 marks]
(ii) Sketch a picture of your surface. [4 marks]
8
CST1.2018.7.9
6 Further HCI
(a) Explain in general how the actions that a user takes are related to the user's
goals. Your answer should make reference to the function of perception, and to
the nature of the cognitive processing that must occur. [8 marks]
(b) Describe a class of problems for which it is not possible to formulate goals. Give
a specific example of a problem in this class, and with reference to that example,
explain how it illustrates two significant attributes of the class. [6 marks]
(c) If an interactive system has several alternative models to describe the user's
goal, how can Bayes' theorem be used to improve the system usability?
[6 marks]
9 (TURN OVER)
CST1.2018.7.10
7 Further HCI
Imagine that you have been asked to implement a radical new design of your college
website. The Senior Tutor has decided that, to make the college seem friendlier, the
home page and navigation should be implemented using a group photograph of all
members of the college that was taken last summer. Your task is to design graphical
content that will be overlaid onto the photograph to provide all necessary information
and navigation.
(a) Draw a sketch showing the main graphical features of your proposed design.
(A few stick figures will be adequate to represent the original photograph. No
additional marks will be given for realistic depictions of members of your college.)
[4 marks]
(b) Explain how the display plane of the photograph has been segmented in your
proposed design, including explanation of any visual marks that were used to
achieve this segmentation. [6 marks]
(c) Choose five specific visual aspects of your proposed design, and for each of these
five:
(i) Describe the graphical property used to implement this aspect (by reference
to your sketch); and
(ii) Explain the mode of correspondence between this graphical property and
the meaning that is intended in this aspect of your design

(a) Explain how each of the following equations or expressions can be used for
detecting and estimating visual motion in a spatio-temporal image sequence
I(x, y, t). Include in your answer the name used to describe each of these general

(b) Colour perception is not about measuring wavelengths, because they vary with
illumination. Explain why it is difficult to assign intrinsic spectral reflectance
properties of surfaces. Explain all steps in the Retinex Algorithm intended to
solve this, relating these steps where possible to neurobiology. [7 marks]
(c) Sketch out an algorithm for shape classification and the construction of shape
grammars, involving active contours, codon strings, and indexing. Explain how
codon constraints enable a shape grammar to define broad equivalence classes
such as "cashew shaped" objects, with invariance to irrelevant transformations
such as planar rotations or dilations.