Let i and j be positive integers. (i) Prove that there exist natural numbers a and b

No answer yet for this question. Ask a Tutor

Question:

Let i and j be positive integers. (i) Prove that there exist natural numbers a and b such that ai = bj+gcd(i, j). You may use standard results provided that you state them clearly. [4 marks] (ii) Let m be a positive integer. Prove that, for all integers n, ( n i 1 (mod m) n j 1 (mod m) ) = n gcd(i,j) 1 (mod m) [3 marks] (b) (i) For sets A and B, let be the binary relation on (A B) defined, for all f, g (A B), by f g Bij(A, A). Bij(B, B). f = g Prove that is an equivalence relation on (A B). [9 marks] (ii) Recalling that, for n N, we let [n] = { i N | 0 i < n }, define Sn = [n] [2] / that is, the set Sn is the quotient of [n] [2] under the equivalence relation . (A) List the elements of Sn for each n [4]. [2 marks] (B) What is the cardinality of Sn for each n N? [2 marks

(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() 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]

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

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

The complex form of the Fourier series is:

f(x) =

ckei2kx

where ck is a complex number and ck = ck.

(a) Prove that the complex coeffiffifficient, ck, encodes the amplitude and phase

coeffiffifficients, Ak and k, in the alternative form:

f(x) =

Ak cos(2kx k)

[10 marks]

(b) What is special about the case k = 0? [2 marks]

f(x):

f(x) = f(x + T), x

can be obtained from the Fourier transform, FL(), of the related function,

fL(x):

fL(x) = f(x

2 6 x < T

otherwise

[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 difffferent 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]

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]

[TURN OVERCST.2001.4.4

4 Compiler Construction

Consider the following grammar giving the concrete syntax of a language:

E id

C E = E;

C {B}

C C repeatwhile E

C if E then C

C if E then C else C

B B C

B C

S C eof

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]

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]

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]

[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]

(d) Deduce that Ackermann's function f(x, y) is a TR function. [3 marks]

(e) Is Ackermann's function PR? [1 mark]

[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]

Ax = b, where b = 1

1 . It is found that

L = 1

1 , D = 2

2 .

The next step in the method is to solve Ly = b to get y = 1

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

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]

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

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]

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

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]

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

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

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]

(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

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)

= u(t)

dv(t)

u(t) gm(t)

m(t)

dh(t)

= 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

. 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

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

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]

{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

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