(iii) Now express your decision rule instead using only the quantities p(Ck), p(Cj ), p(x|Ck), p(x|Cj ), and relate it to the diagram above. [2
What forms of error do database normal forms seek to render less probable? [3 marks] Define Second Normal Form.Define Fourth Normal Form.Give an example of a database schema that is in 2NF form but not in 4NF, showing how it is possible for mutually contradictory data to be recorded. Explain your assumptions about the semantics underlying the database schema. [7 marks] Are there applications where normal forms are unnecessary or even unhelpful? [3 marks] 10 Topics in Artificial Intelligence Using appropriate mathematical expressions, define the following operations commonly used in computer vision and briefly explain their function and applications: (a) convolution (b) correlation (c) bandpass filtering (d) edge detection by derivative zero-crossings (e) invariant transform Modelling Given that in a balanced system with K devices and N customers, the utilisation of each device is given by U = N N + K 1 derive a formula for the response time in terms of throughput, the number of devices and the average service demand at each device. [6 marks] A system consists of three types of devices, A, B and C. Customers require service at each type of device but do not care at which particular device they are served. The numbers of each type of device and average service requirements per customer are number of devices average service demand A 48 48 ms B 24 24 ms C 18 18 ms so that, for example, a customer requires on average 48 ms of service at a type device. Give bounds for the system response time at a throughput of 500 customers per second when a scheduling policy ensures that (a) no device is more than 1.5 times as busy as the average for devices of the same type (b) no device is more than 1.8 times as busy as the average for devices of the same type [9 marks] What can you say about response time if no limit on utilisation skew across devices of the same type is guaranteed? Consider the ML definitions: fun I x = x fun curry f x y = f (x,y) fun uncurry f (x,y) = f x y What are the types of curry and uncurry? [2 marks] Recall that f o g is the function that maps x to f(g(x)). Describe the effect of the following functions: curry (fn(x,y) => x) uncurry o curry curry I uncurry I [4 marks] Infinite lists can be represented in ML by functions. A function f represents the infinite list f(0), f(1), f(2), . . . (a) Give a representation for the infinite list 0, 2, 4, . . . [2 marks] (b) Code in ML a map functional for this representation; given a function f and the infinite list x0, x1, x2, . . ., it should yield the representation of f(x0), f(x1), f(x2), . . . [2 marks] (c) Code in ML a drop function, which given an integer i > 0 and an infinite list x0, x1, x2, . . . returns the infinite list xi , xi+1, xi+2, . . . [2 marks] (d) Code in ML an interleave function, which combines the infinite lists x0, x1, x2, . . . and . . returns the infinite list obtained by deleting each xi for which p(xi) is false.
(a) Explain the terms amortized analysis, aggregate analysis and potential method.
[6 marks]
(b) Consider an arbitrary sequence of n stack operations PUSH(), POP() and
MULTIPOP(x) in which POP() or MULTIPOP(x) never attempt to remove more
elements than there are on the stack. Assuming that the stack begins with
s0 items and fifinishes with sn items, determine the worst-case total cost for
executing the n operations as a function of n, s0 and sn. You may assume
PUSH() and POP() cost 1 each and MULTIPOP(x) costs x. [5 marks]
(c) Suppose we want to store a number of items in an array, but we do not know in
advance how many items need to be stored. The INSERT(x) operation appends
an item x to the array. More precisely, if the size of the array is large enough, x
is inserted directly at the end of the array. Otherwise, a new array of larger size
is created that contains all previous items with x being appended at the end.
The total cost of INSERT(x) is 1 in the fifirst case, and the size of the new array
in the second case.
(i) Devise a strategy which, for any integer n, performs any sequence of n
INSERT(.) operations at a total cost of O(n). [5 marks]
(ii) For the strategy described in (c)(i), give a proof of the cost of the algorithm
using the potential method. [4 marks]
10CST.2014.1.11
10
Algorithms
(a) Given any directed graph G = (V, E) with non-negative edge weights, consider
the problem of all-pairs shortest path (APSP). Give the asymptotic runtimes of
the following four algorithms when applied (directly or iterated) to the APSP
problem as a function of |V | and |E|, and provide a brief justifification for your
answer: Bellman-Ford, Dijkstra, matrix multiplication and Johnson. [8 marks]
(b) Consider the problem of converting currencies modelled by a directed graph
G = (V, E) with |V | vertices representing currencies and |E| directed edges
(u, v) each of which has a strictly positive weight w(u, v) > 0 representing
the exchange rate. For instance, for any real number x, we have x USD =
w(dollars, pounds) x GBP. Our goal is, given a pair of currencies s, t V , to
fifind the least expensive way of exchanging from s to t, possibly by using more
than one exchange.
(i) How could you transform the graph by reweighting the edges so that the
problem could be solved with a shortest path algorithm? Indicate which
shortest path algorithm is used. [8 marks]
(ii) How would you deal with negative-weight cycles if they occurred in the
transformed graph? Give the perspective of the currency trader as well as
that of a computer scientist.
Continuous Mathematics
(b) What is special about the case k = 0? [2 marks]
(c) Explain how the coeffiffifficients, ck, of the Fourier series of the periodic function,
[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 different 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) {
count ++;
}
}
}
}
Show how to start two threads, each executing this run method. [2 marks]
(c) When this program is executed, only one of the count fifields is found to
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]
3
[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]
(c) Specify a suitable abstract syntax, for example by giving a type declaration
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]
(c) Roughly estimate how many character comparisons would be made when your
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
time
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 and comment a Verilog module which performs the function of a shaft
decoder. [15 marks]
5
[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]
(c) Hence or otherwise show that for all n N, gn(y) is a PR function. [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]
7
[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]
(c) The Choleski factorisation A = LDLT is to be applied to the solution of
Ax = b, where b = 1
1 . It is found that
L = 1
1
2
1 , D = 2
3
2 .
The next step in the method is to solve Ly = b to get y = 1
1
2
. 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]
(c) Under what circumstances would it be sensible to employ Douglas and Pucker's
algorithm?
(a) Write brief notes on polymorphism in ML, using lists and standard list functions
such as @ (append) and map. [4 marks]
(b) Explain the meaning of the following declaration and describe the corresponding
data structure, including the role of polymorphism.
datatype 'a se = Void | Unit of 'a | Join of 'a se * 'a se;
[4 marks]
(c) Show that ML lists can be represented using this datatype by writing the
functions encode_list of type 'a list -> 'a se and decode_list of type
'a se -> 'a list, such that decode_list (encode_list xs) = xs for every
list xs. [3 marks]
(d) Consider the following function declaration:
fun cute p Void = false
| cute p (Unit x) = p x
| cute p (Join(u,v)) = cute p u orelse cute p v;
What does this function do, and what is its type? [4 marks]
(e) Consider the following expression:
fn p => cute (cute p)
What does it mean, and what is its type? Justify your answer carefully.
[5 marks]
2CST.2014.1.3
2
Foundations of Computer Science
(a) Write brief notes on the queue data structure and how it can be implemented
effiffifficiently in ML. In a precise sense, what is the cost of the main queue
operations? (It is not required to present ML code.) [6 marks]
(b) Run-length encoding is a way of compressing a list in which certain elements
are repeated many times in a row. For example, a list of the form [a, a, a, b, a, a]
is encoded as [(3, a),(1, b),(2, a)]. Write a polymorphic function rl_encode to
perform this encoding. What is the type of rl_encode? [6 marks]
(c) The simple task of testing whether two lists are equal can be generalised to allow
a certain number of errors. We consider three forms of error:
element mismatch, as in [1,2,3] versus [1,9,3] or [1,2,3] versus [0,2,3]
left deletion, as in [1,3] versus [1,2,3] or [1,2] versus [1,2,3]
right deletion, as in [1,2,3] versus [1,3] or [1,2,3] versus [1,2]
Write a function genEquals n xs ys that returns true if the two lists xs and
ys are equal with no more than n errors, and otherwise false. You may assume
that n is a non-negative integer. [8 marks]
All ML code must be explained clearly and should be free of needless complexity.
3 (TURN OVER)CST.2014.1.4
SECTION B
3
Object-Oriented Programming
(a) (i) Explain the purpose of access modififiers in OOP languages. [2 marks]
(ii) Copy and complete the table below to show the access restrictions for the
four access modififiers in Java. [2 marks]
Access Modififier
Defifining class
Class in same package
Subclass in difffferent package
Non-subclass in difffferent package
(b) A Java game designer wishes to store all the game preferences (e.g., player name,
screen size, music volume, etc.) within a custom Preference class.
(i) Assuming each preference is stored as a unique String key mapping to
a String value, give a simple implementation of Preference that allows
for effiffifficiently setting or updating preferences and retrieving previously set
ones. Your implementation should defifine an exception that is thrown when
a preference key is requested but not present. [5 marks]
(ii) It is important that only one Preference object exists in a running game.
Show how to apply access modififiers and the Singleton design pattern to
ensure this. Your implementation should lazily instantiate the object. Is it
necessary to make your class final or Cloneable? Explain your answer.
[6 marks]
(c) The designer also implements other Singleton classes in the game and proposes
to create a SingletonBase base class from which all such classes would inherit
the singleton behaviour. By providing example Java code, explain why this is
not viable. [5 marks]
4CST.2014.1.5
4
Object-Oriented Programming
A Lecturer wishes to create a program that lists his students sorted by the number
of practical assignments they have completed. The listing should be greatest number
of assignments fifirst, sub-sorted by name in lexicographical order (A to Z).
A class StudentInfo stores the name and number of assignments completed for a
student. Amongst other methods, it contains a void setCompleted(int n) method
that allows changes to the number of completed assignments.
(a) Provide a defifinition of StudentInfo with an equals() method and a natural
ordering that matches the given requirement. [9 marks]
(b) A TreeSet is used to maintain the StudentInfo objects in appropriate order.
When setCompleted(...) is called on a StudentInfo object it is necessary
to remove the object from the set, change the value and then reinsert it to
ensure the correct ordering. This is to be automated by applying the Observer
design pattern via classes UpdatableTreeSet and SubscribableStudentInfo.
A partial defifinition of UpdatableTreeSet is provided below.
public class UpdatableTreeSet extends
TreeSet {
// To be called just before the StudentInfo object is updated
public void beforeUpdate(SubscribableStudentInfo s) {
remove(s);
}
// To be called just after the StudentInfo object is updated
public void afterUpdate(SubscribableStudentInfo s) {
add(s);
}
}
(i) Extend StudentInfo to create SubscribableStudentInfo such that: mul
tiple UpdatableTreeSet objects can subscribe and unsubscribe to receive
updates from it; and the beforeUpdate(...) and afterUpdate(...)
methods are called appropriately on the subscribed UpdatableTreeSet
objects whenever setCompleted(...) is called. [6 marks]
(ii) Give a complete defifinition of UpdatableTreeSet that overrides the in
herited methods boolean add(SubscribableStudentInfo) and boolean
remove(Object) to automatically subscribe and unsubscribe to their
arguments, as appropriate. You may ignore all other methods inherited
from TreeSet. [5 marks]
5 (TURN OVER)CST.2014.1.6
SECTION C
5
Numerical Methods
(a) Floating point representation:
(i) If a single-precision flfloating point number is added to a double-precision
flfloating point number, what can we say about the expected and worst-case
representation errors in the result? [2 marks]
(b) Floating point rounding:
(i) Would a round-to-odd rule introduce a difffferent amount of bias compared
with the normally used round-to-even rule? [2 marks]
(ii) What is it about counting in base 10 that causes bias in the standard
approach used when rounding to a given number of signifificant fifigures?
Explain whether a similar rule for numbers expressed in base 4 would
introduce a bias. [4 marks]
(c) Matrix multiplication conditioning:
(i) When a pair of matrices of dimension N N are multiplied, what is the
expected and worst case representation error in the result? [2 marks]
(ii) Before using Gaussian Elimination to achieve triangle form when solving
a system of simultaneous equations, what step or steps can be taken to
ensure numerical stability? [4 marks]
(iii) What is meant by backwards stability regarding a numerical method?
[2 marks]
(iv) What role can partial derivatives play in examining the stability of a
computation compared with using a condition number? [4 marks]
6CST.2014.1.7
6
Numerical Methods
(a) A lander for the planet Mars has initial mass M0 = m(0) kilograms which
includes F0 = f(0) kilograms of fuel. It is released from an orbiter at time zero
at height H0 = h(0) with an initial downwards velocity of zero. It must touch
down at less than 1 metre per second. Its downward force is Mg (where g is
constant) and this is countered by a rocket motor that is pre-programmed to
generate a time-varying upwards force of u(t). The motor burns fuel at a mass
rate proportional to the force it develops. This is summarised in these equations:
dm(t)
dt
= u(t)
dv(t)
dt
=
u(t) gm(t)
m(t)
dh(t)
dt
= v(t)
A discrete-time computer simulation of the landing uses time steps t. Using a
programming language of your choice or pseudo code:
(i) Give a suitable state vector for the system. Include setup code that suitably
initialises the state vector. [1 mark]
(ii) Give state update assignments for one time step based on simple linear
projections assuming a function u(t) has been provided. [2 marks]
(iii) Give code for the various stopping conditions. These include a safe landing,
a fatal crash or running out of fuel. [1 mark]
(iv) Why does a simple linear projection lead to a velocity modelling error
in every time step. What determines the error magnitude and does it
compound over successive steps? [3 marks]
(b) (i) Brieflfly describe the bisection method (binary chop) for fifinding a root of an
equation. Mention two possible stopping conditions. [3 marks]
(ii) Recall that the CORDIC algorithm uses successive approximation where
the ith division of the interval is by arctan(2i ). Give a stopping condition
for CORDIC. [2 marks]
(iii) The following approximation can be used for cosine: cos(x) 1 x
2
2
. Does
it accurately deliver three signifificant decimal digits where the argument
range is 0.0 to /4 ? [2 marks]
(iv) Approximately how many iterations of CORDIC are required to ensure three
signifificant decimal digits are accurate over the same range? [6 marks]
7 (TURN OVER)CST.2014.1.8
SECTION D
7
Algorithms
(a) Consider the radix sort algorithm.
(i) Explain how radix sort works, to what inputs it can be applied and what
its asymptotic complexity is. [5 marks]
(ii) Explain why running radix sort does not proceed from most to least
signifificant digit, as would at fifirst seem more intuitive. [4 marks]
(iii) Give a proof by induction of the correctness of radix sort. [4 marks]
(b) Clearly describe an algorithm, strictly better than O(n2 ), that takes a positive
integer s and a set A of n positive integers and returns a Boolean answer to the
question whether there exist two distinct elements of A whose sum is exactly s.
Evaluate its complexity. [7 marks]
8CST.2014.1.9
8
Algorithms
(a) Explain an effiffifficient method to fifind the k-th smallest number in a set of n
numbers (output: one number), without fifirst sorting the n numbers, and discuss
its complexity in terms of n and k. [4 marks]
(b) Explain an effiffifficient method to fifind the k smallest numbers in a set of n numbers
(output: k numbers), without fifirst sorting the n numbers, and discuss its
complexity in terms of n and k. How much extra work is needed compared
to (a)? [4 marks]
(c) Draw four distinct binary search trees (BSTs) for the following set of keys:
{1, 2, 3, 4}. [2 marks]
(d) Let a height-balanced BST (hBST) be a BST with the additional defifining
invariant that each node is the parent of subtrees whose heights diffffer by at
most 1. Give an effiffifficient procedure to insert into an hBST and prove that the
defifining invariant is preserved. [10 marks]
9 (TURN OVER)CST.2014.1.10
9
Algorithms
(a) Explain the terms amortized analysis, aggregate analysis and potential method.
[6 marks]
(b) Consider an arbitrary sequence of n stack operations PUSH(), POP() and
MULTIPOP(x) in which POP() or MULTIPOP(x) never attempt to remove more
elements than there are on the stack. Assuming that the stack begins with
s0 items and fifinishes with sn items, determine the worst-case total cost for
executing the n operations as a function of n, s0 and sn. You may assume
PUSH() and POP() cost 1 each and MULTIPOP(x) costs x. [5 marks]
(c) Suppose we want to store a number of items in an array, but we do not know in
advance how many items need to be stored. The INSERT(x) operation appends
an item x to the array. More precisely, if the size of the array is large enough, x
is inserted directly at the end of the array. Otherwise, a new array of larger size
is created that contains all previous items with x being appended at the end.
The total cost of INSERT(x) is 1 in the fifirst case, and the size of the new array
in the second case.
(i) Devise a strategy which, for any integer n, performs any sequence of n
INSERT(.) operations at a total cost of O(n). [5 marks]
(ii) For the strategy described in (c)(i), give a proof of the cost of the algorithm
using the potential method. [4 marks]
10CST.2014.1.11
10
Algorithms
(a) Given any directed graph G = (V, E) with non-negative edge weights, consider
the problem of all-pairs shortest path (APSP). Give the asymptotic runtimes of
the following four algorithms when applied (directly or iterated) to the APSP
problem as a function of |V | and |E|, and provide a brief justifification for your
answer: Bellman-Ford, Dijkstra, matrix multiplication and Johnson. [8 marks]
(b) Consider the problem of converting currencies modelled by a directed graph
G = (V, E) with |V | vertices representing currencies and |E| directed edges
(u, v) each of which has a strictly positive weight w(u, v) > 0 representing
the exchange rate. For instance, for any real number x, we have x USD =
w(dollars, pounds) x GBP. Our goal is, given a pair of currencies s, t V , to
fifind the least expensive way of exchanging from s to t, possibly by using more
than one exchange.
(i) How could you transform the graph by reweighting the edges so that the
problem could be solved with a shortest path algorithm? Indicate which
shortest path algorithm is used. [8 marks]
(ii) How would you deal with negative-weight cycles if they occurred in the
transformed graph? Give the perspective of the currency trader as well as
that of a computer scientist.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Authors: Thomas Nechyba
1st edition
538453257, 978-0538453257
