4 Comparative Programming Languages illustrating your answer by explaining the meaning of the following fragment of code: [self isAwake] whileTrue: [| item | item := self askForCookie. (self isCookie: item) ifTrue [self complainAbout:item]. (self isFull) ifTrue Suggest how you implement in Smalltalk (or Squeak) a binary tree in which each node contains an integer and pointers to two or fewer other nodes of the same kind. [4 marks] Outline the code you would use (a) to construct this kind of tree, and (b) to sum all the integers in a given tree.

 

ensure to answer all

(a) Describe the difference between blocking and nonblocking input/output operations. How can an operating system improve the performance (as seen by a
process) of blocking operations? [4 marks]
(b) A privileged process is given raw access to a slow disk device. It reads a page from
the disk (using a blocking operation), processes the information and repeats.
Suppose d processing takes 5 units of elapsed time. Assuming
the machine is otherwise idle, how can this elasped time be reduced? State any
assumptions about hardware features you are making. [5 marks]
(c) Describe how polled I/O works and state its disadvantages. Under what
conditions is polling a sensible approach? Describe an alternative approach.
(You may find it helpful to provide a few lines of psuedo code.) [4 marks]
(d) What advantages does direct memory access (DMA) provide? Describe its
operation as seen by a device driver in the operating system. (You may find
it helpful to write a few lines of psuedo code.) [5 marks]
(e) To what extent does heterogeneity in I/O systems add complexity to an
operating system?

 

 

Pedal cyclists are to be allowed once again to ride through Cambridge on a 24-hour
basis, using a traffic control system based on Air Traffic Control principles. By
dialling a special telephone number and using the telephone keypad for data entry,
cyclists will file a journey-plan before departure, and will be allocated a journey
schedule that is announced back to them over the telephone.
Your company is bidding for the contract to develop the journey-plan filing system,
which supports the filing of journey plans by the public and which will be linked to
a separate system (not part of the bid) that controls cycle traffic. You have been
put in charge of preparing your company's bid.
(a) Describe how you would conduct a user-needs analysis to support the design
of the system. What are the main needs that you think would emerge from
this? [6 marks]
(b) Design the user interface of the system in sufficient detail to explore the likely
form of the user's mental model, and describe the form you think this mental
model might take, presenting enough details of the user interface to justify
your answer. [10 marks]
(c) How would you go about analysing and/or evaluating the design? [4 marks]
7 Optimising Compilers
Summarise five of the following ideas
(a) control flow determination in the presence of function or label variables
(b) safety of dataflow information
 

In a concurrent system it is usual to distinguish between safety properties and
liveness properties.
(a) What is meant by mutual exclusion, and how does a programmer ensure it is
enforced in Java? Indicate whether it relates to safety or to liveness. [4 marks]
(b) What is deadlock and how can it occur? Again, indicate whether it relates to
safety or to liveness. [4 marks]
A group of ten feeding philosophers has gathered to eat at a long trough, as shown
below. They eat by leaning over the trough and so must be careful not to let their
heads collide in the middle. To ensure safety they decide that around each position
in the trough at most one philosopher is allowed to be eating at any one time. For
instance, only one of 1, 2 or 9 could be eating at once, but there is no problem with
9, 3, 6 and 10 all eating together.
9 10
1 3 5 7
2 4 6 8
In a Java system, each philosopher is modelled by a thread which loops
between eating and non-eating phases. There are four TroughPosition objects,
corresponding to the four positions along the trough. Each philosopher has a
reference to the position at which he or she is eating.
(c) Define a Java class TroughPosition which supports methods startEating()
and finishEating() to ensure safe execution for the philosophers at that
position. [6 marks]
(d) Can your solution suffer from deadlock? Either explain why it cannot occur,
or explain how it could be avoided. [3 marks]
(e) Can your solution suffer from starvation - that is, can one thread continuously
remain in the startEating() method? Either explain why this cannot occur,
or explain how it could be avoided. [3 marks]
4
CST.2003.5.5
SECTION B
5 Computer Graphics and Image Processing
(a) Describe the A-buffer polygon scan conversion algorithm using 4×4 sub-pixels
in each pixel. [10 marks]
(b) It is possible to represent continuous tone greyscale images using just black
ink on white paper because of limitations in the human visual system. Explain
how and why. [4 marks]
(c) Describe an algorithm which, given a greyscale image, will produce a black
and white (bi-level) image of four times the resolution in each dimension which
provides a good approximation to the greyscale image. [6 marks]
5 [TURN OVER
CST.2003.5.6
6 Compiler Construction
(a) A Java static method is defined in class C by
class C {
public static int f(int x, int y) { int z = x; ...; return x+y*z;
}
}
where '...' represents commands the details of which are not important to
this question. It is called in an expression e of the form
f(f(1,2), f(3,4))
Give JVM (or other stack machine) code corresponding to the expression e
and explain how this is derived from the syntax tree for e. [6 marks]
(b) Explain how the body of f above is mapped into JVM (or other stack machine)
code, explaining the rˆole of the registers FP and SP (precise details are not
important, but their rˆole should be well explained). You may write '...' for
the translation of the '...' in f. [6 marks]
(c) Consider the Java class definitions:
class A {
public int a1, a2;
public void m() { println("I am an A with " + a1 + " and " + a2);
}
}
class B extends A {
public int b1, b2;
public void m() { println("I am a B with " + a1 + " and " + a2 +
" also with " + b1 + " and " + b2);
}
}
Describe the run-time storage layout for objects of class A and for those of
class B, particularly noting the size and offsets of members and how a cast
of an object of type class B to one of class A can be achieved.
Explain how calls to m() work, particularly in code like:
public static void g(B x) { h(x); }
public static void h(A x) { x.m(); }
[8 marks]
6
CST.2003.5.7
7 Artificial Intelligence I
The following Prolog relation appends a list A to a list B to give a list C.
append([],Y,Y).
append([H|T],Y,[H|Z]) :- append(T,Y,Z).
(a) Using the append relation, write a Prolog predicate insert(X,Y,Z) that is
true if X can be inserted into a list Y to give a list Z. Your relation should be
capable of using backtracking to generate all lists obtained from Y by inserting
X at some point, using a query such as:
insert(c,[a,b],Z).
to obtain Z=[c,a,b], Z=[a,c,b], and Z=[a,b,c] and it should generate each
possibility exactly once. [5 marks]
(b) Using the insert relation, write a Prolog predicate perm(X,Y) that is true if
a list Y is a permutation of a list X. Your predicate should respond to a query
such as
perm([a,b,c],Y)
by using backtracking to generate all permutations of the given list. [6 marks]
(c) We have a list of events [e1,e2,...,en]. A partial order can be expressed in
Prolog by stating
before(e3,e4).
before(e1,e5).
and so on, where before(a,b) says that event a must happen before event
b (although not necessarily immediately before). No ordering constraints are
imposed other than those stated using before.
Given a list of events, a linearisation of the list is any ordering of its
events for which none of the before constraints are broken. Given the
example above and the list [e1,e2,e3,e4,e5], one valid linearisation would be
[e3,e1,e2,e5,e4]. However, [e4,e2,e1,e5,e3] is not a valid linearisation
because the first before constraint does not hold.
Using the perm predicate or otherwise, and assuming that your Prolog program
contains before constraints in the format suggested above, write a Prolog
predicate po(X,Y) that is true if Y is a valid linearisation of the events in the
list X. Your relation should be capable of using backtracking to generate all
valid linearisations as a result of a query of the form
po([e1,e2,e3,e4,e5],Y).

(a) (i) Define the operators in the core relational algebra. [5 marks]
(ii) Define the domain relational calculus. [4 marks]
(iii) Show how the relational algebra can be encoded in the domain relational
calculus. [3 marks]
(b) A constraint can be expressed using relational algebra. For example, R = ∅
specifies the constraint that relation R must be empty, and (R ∪ S) ⊆ T
specifies that every tuple in the union of R and S must be in T.
Consider the following schema.
RockStar(name, address, gender, birthday)
RockManager(managername, starname)
(i) Give a constraint to express that rock stars must be either male or female.
[1 mark]
(ii) Give a constraint to express the referential integrity constraint between
the RockStar and RockManager relations. (Note: starname is intended
to be a foreign key.) [3 marks]
(iii) Give a constraint to express the functional dependency name→address
for the RockStar relation. [4 marks]
8
CST.2003.5.9
SECTION C
9 Logic and Proof
(a) For k > 0, let φ(k) be the formula
[(P1 ↔ Q1) ∧ . . . ∧ (Pk ↔ Qk)] → R.
Prove that there exists an ordering of the propositional variables, namely P1,
P2, . . ., Q1, Q2, . . ., R, such that the size of the ordered binary decision diagram
(OBDD) for φ(k) increases linearly with k. [5 marks]
(b) Prove that there exists a variable ordering such that the size of the OBDD for
φ(k) increases exponentially with k. [6 marks]
(c) Give a set of clauses suitable for attempting to prove φ(k) using resolution.
[3 marks]
(d) Describe the computation that would result if the Davis-Putnam (DPLL)
procedure were applied to these clauses.

 

 

For each of the following situations identify one data structure or algorithm that it
would be sensible to use, and another that would in principle achieve the desired
result but which would have significant disadvantages. You may identify standard
methods by name and need not describe in detail how they work, but should make
it clear what properties the schemes that you identify have that make some of them
more appropriate than others.
(a) You need to represent some (directed) graphs where when a graph has N
vertices it will have around N log N edges. The number of vertices, N, may
become quite large. [4 marks]
(b) In the process of rendering a graphical image you have already sorted all the
objects that have to be drawn with an ordering based on their distance from
the viewpoint. Now the image has been changed slightly so that you can
start to display the next frame of the video sequence, so all the distances have
changed, and you need to sort the objects again. [4 marks]
(c) You need to build a table. It will be possible to insert objects into the table
or retrieve previously stored ones. The only operation you are permitted to
perform on objects is a pair-wise comparison that can tell if two objects are
equal and if not indicates an ordering between them. There will be both plenty
of insertion operations and plenty of lookups. [4 marks]
(d) You need to find the shortest distance (through a directed graph that has
lengths associated with each edge) from a nominated source point A to each
of a collection of destinations {Bi}. [4 marks]
(e) Blocks of material, each identified by a key, are to be stored on a large disc.
From time to time new blocks (and associated keys) will need to be added,
but mostly you need to service requests where a user submits a key and wants
the corresponding information recovered. There is so much data that the disc
is fairly full.

 

Write  complete java program that prompts the user for their name and two numbers.
a program that will ask the user to enter your name and your class section
 

A reasonable approximation for the average number of probes to insert a new entry
into an open hash table where a fraction β of the table is already in use is 1/(1−β).
Suppose that data is stored by initially creating a really tiny hash table (say a
vector of size just 8). Entries are added to the table from time to time. Whenever
the table becomes 3/4 full a new hash table, twice the size, is created: all existing
data is taken out of the old table, and inserted instead into the new one. Thus in
general the table that is in use will be between 3/8 and 3/4 full, and looking things
up in it will be efficient.
Although the above method has good predicted costs for retrieving information
stored in the table, there remains some worry that the repeated cost of copying
data from smaller to larger tables may be excessive. Suppose that at some stage
N items have been inserted and that the very last insertion provoked the copying
step. Estimate the ratio between the total number of hash probes performed while
building the table and N. How does it compare with the number that would have
been used if the table had been built full-sized to start with rather than having to
grow stage by stage on the way? [20 marks]
[If you really need their values, you may assume that ln(2) = 0.7, ln(3) = 1 and
ln(5) = 1.6, but note that you are not expected to perform any arithmetic tedious
enough to call for a calculator: a reasonable estimate (for example to within a factor
of 1.5) and a justification of how that value was arrived at is what is required.]
7 Operating System Functions
What properties of file access and of discs does a log-structured file system use
to optimise file system performance? Describe scenarios in which the relevant
assumptions are valid and invalid. [8 marks]
Describe the operation of such a file system, including the actions of the sweep, or
garbage collection, stage, and how the system recovers from crashes. [12 marks]
8 Unix Case Study
Describe the segments that compose a Unix process and how the exec functions
create these segments from the sections of an executable binary file. [8 marks]
Using as an example the command line ls | wc, describe the sequence of
operations and system calls that a shell must perform to execute the commands to
the point at which an exec function is invoked on each of ls and wc.

 

(a) Design a 2-bit multiplier for unsigned integers which takes input x1 x0 representing the unsigned integer X, y1 y0 representing the unsigned integer Y , and produces the output z3 z2 z1 z0 representing the unsigned integer Z. [4 marks] (b) How can multipliers designed in part (a) be cascaded (with adders) to provide a four-bit multiplier? [4 marks] (c) Design a sequential 8-bit multiplier. You can assume that a 16-bit adder has been provided. The finite state control can be described by a state diagram. [8 marks] (d) Outline the design of a sequential divider which can divide 16-bit unsigned integers by 8-bit unsigned integers. [4 marks] 4 CST.2003.2.5 SECTION C 4 Probability In order to test the integrity of a network of ducting, engineers have developed an inspection device which can be introduced at a node and which then finds its way along a length of ducting to an adjacent node. In a particular case, eight nodes are sited at the vertices (corners) of a cube and 12 lengths of ducting are arranged along the edges of the cube. The inspection device is introduced at one node and equiprobably chooses one of the three lengths of ducting leading from that node for its first move. On arrival at the adjacent node the device equiprobably chooses one of the three lengths of ducting leading from that node (including the length it has just inspected). It continues in this fashion until the engineers stop its operation. Let An be the probability of the inspection device returning to the starting node after n moves, and deem A0 = 1. Let Dn be the probability of the inspection device visiting the node diagonally opposite the starting node after n moves. Clearly, D0 = 0. (a) Demonstrate that An = 0 for all odd n and that Dn = 0 for all even n. [4 marks] (b) Determine A2, A4 and A6 expressing all values as fractions.(i) With reference to the 5-stage pipeline, what are data hazards and how

can they be resolved to ensure that the programmer's model of sequential

execution is always preserved whilst minimising performance impact?

[6 marks]

(ii) With reference to the 5-stage pipeline, what are control hazards and how

can they be resolved? [4 marks]

(b) If we wanted the above pipeline to mimic two processors running at half the

speed, then we could have two copies (A and B) of the register state and keep

the existing pipeline. The instruction-fetch stage would alternate between

fetching from threads A and B on alternate clock cycles. As a consequence, if

instruction fetch was from thread B, then an instruction from thread A would

be in decode, B in execute, A in memory access and B in write back.

(i) For this dual-threaded processor, if branches are performed in the decode

stage, does the pipeline exhibit a branch delay slot? [5 marks]

(ii) How can the resolution of data hazards be simplifified for this dual-threaded

processor? [5 marks]

3 (TURN OVER)CST.2008.5.4

3 Digital Communication I

(a) Describe fifive physical properties of a communications channel. [5 marks]

(b) Consider the fifigure below. Entities N and N0 use an ARQ system.

Channel - 1

Channel

Channel + 1

Entity - 1

Entity

Entity + 1

Entity - 1

Entity

Entity + 1

n

n

n

N

N

N

N'

N'

N'

(i) Explain how the latency of channel n − 1 can have a direct effffect on the

capacity of channel n. [6 marks]

(ii) Defifine windowing as it relates to an ARQ system and describe how the

capacity of the ARQ system may be improved through its use. [4 marks]

(iii) If an ARQ system is used for an interactive session, the ARQ system

can lead to many small packets, each under-full and perhaps sent with

signifificant overhead. Design and describe an algorithm that overcomes

the limitation of sending many mostly-empty packets for an interactive

session. [5 marks]

4CST.2008.5.5

4 Concurrent Systems and Applications

(a) A web server is an application that listens for incoming network connections

on TCP port 80. Once a connection is established, the task of processing

client requests and sending replies can be handled by an instance of a

Worker class which you may assume already exists. Worker implements the

java.lang.Runnable interface and has an accessible constructor that takes as

argument a java.net.Socket object representing the network connection to

a client.

Provide the Java code for a webserver which, upon start-up, attempts to listen

on TCP port 80 and starts a new Thread running a new Worker for every

connection. Your program should print helpful error messages indicating the

likely cause of problems when it is unable to proceed as expected. [10 marks]

(b) A busy web server might expect to handle concurrent requests to read and

update some shared data and could use Timestamp Ordering (TSO) to enforce

isolation between concurrent transactions.

(i) Explain how TSO enforces isolation. [5 marks]

(ii) Is TSO appropriate for a web server application? Explain your reasoning.

[5 marks]

5 (TURN OVER)CST.2008.5.6

SECTION B

5 Computer Graphics and Image Processing

(a) Describe in detail an algorithm that returns the minimum distance from a

point to a line segment in two dimensions. Ensure that you include all of your

assumptions and all necessary mathematical calculations. [7 marks]

(b) A quadratic Be´zier curve is defifined by three points, P1, P2, P3, and a

parameter, t:

P(t) = (1 − t)2P1 + 2t(1 − t)P2 + t2P3, 0 ≤ t ≤ 1

Describe an algorithm that draws the quadratic Be´zier curve, using straight

lines only, to within a tolerance τ . You may use the algorithm from part (a)

and you may assume that you already have an algorithm for drawing a straight

line. [8 marks]

(c) Consider the control of detail in a curve that is represented by a sequence of

many straight line segments. Describe how Douglas and P¨ucker's algorithm

can be used to remove superflfluous points. You may use the algorithm from

part (a). [5 marks]

6CST.2008.5.7

6 Compiler Construction

Consider the following grammar for expressions (where Id is a terminal symbol

representing an identififier resulting from lexical analysis):

Expr ::= 1 | 2 | Id | Expr + Expr | Expr / Expr |

Expr ^ Expr | (Expr)

(a) Explain in what principal respect this grammar is unsatisfactory. [1 mark]

(b) Assuming further that + is to be left-associative, ^ is to be right-associative and

/ is to be non-associative (i.e. 2/2/2 is forbidden but (2/2)/2 and 2/(2/2)

are allowed), re-write the grammar to reflflect this. [4 marks]

(c) List the terminal symbols and non-terminal symbols, and count the production

rules both in the original grammar and in the grammar in your answer to

part (b). Indicate the start symbol in both grammars. [2 marks]

(d) Defifine a type or types (in C, Java, or ML) suitable for holding an abstract

syntax tree resulting from your answer to part (b). [2 marks]

(e) Give a brief and elementary explanation of the principles of how the grammar

resulting from part (b) might be used to create a syntax analyser taking a

token stream as input (via calls to function lex()) and giving as output an

abstract syntax tree corresponding to part (d). Mention both hand-written

and automatically-generated syntax analysers. [8 marks]

(f ) Summarise any issues related to left- or right-associative operators in the

two techniques (in implementing the parser and in constructing the tool) you

outlined in part (e). [3 marks]

7 (TURN OVER)CST.2008.5.8

7 Concepts in Programming Languages

(a) Write a procedure and a call to it in block-structured pseudocode such

that the execution of the procedure under pass-by-reference and under

pass-by-value/result yields difffferent outcomes. Justify your answer.

[7 marks]

(b) Explain the meaning of static (i.e. compile-time) and dynamic (i.e. run-time)

type checking.

Compare the advantages and disadvantages of these two approaches to type

checking from the point of view of the language designer, the language

implementer, and the programmer.

[6 marks]

(c) Explain how objects can be simulated in SML, giving an example.

Does it follow that SML, together with its module system, is an object-oriented

programming language? Why?

[7 marks]

8 Databases

(a) What is the difffference between a key and a functional dependency? [3 marks]

(b) The schema R(A, B, C, D, E) has the following functional dependencies.

A, B

→

C

B, C

→

D

C, D

→

E

D, E

→