In this question you will be asked to reflect on a project you have been involved in or observed, in which a design evolved, or could have evolved, through applying a theory of user behaviour. You may refer to a Part Ib group project, practical work from Part Ia/Ib Interaction Design, or a project outside the Computer Science Tripos. You are advised to read the whole question before choosing a project to describe. (a) Describe the project in one or two sentences. [2 marks] (b) Describe the intended users of this system, and the benefits that they would obtain through using the system. [2 marks] (c) Describe a theory of user behaviour that is relevant to the project, explaining why it is relevant. [3 marks] (d) Would application of this theory be formative or summative? Explain why. [2 marks] (e) How are the opportunities for design evolution different, when either summative or formative evaluation methods are applied? Your answer should refer to the roles of divergence and convergence in a design process. [4 marks] (f ) Explain what kind of evidence would be required when applying this theory in your project, and how you would obtain it, noting whether this evidence would involve qualitative or quantitative data. [3 marks] (g) Describe how your project team applied, or could have applied, a method that would improve the reliability of quantitative data. [2 marks] (h) Describe how your project team applied, or could have applied, a method that would improve the reliability of qualitative data. [2 marks]

(a) Prove that the information measure is additive: that the information gain from observing the combination of N independent events, whose probabilitie are pifor i = 1 . . . N, is the sum of the information gained from observing eachone of these events separately and in any order. [3 marks] (b) What is the shortest possible decodable code length, in bits per average symbol, that could be achieved for a six-letter alphabet whose symbols have probabilities

? [3 marks] (c) Consider Shannon's third theorem, the Noisy Channel Coding Theorem, for a continuous communication channel having bandwidth W Hertz, perturbed by additive white Gaussian noise of power spectral density N0, and average transmitted power P. (i) Is there any limit to the capacity of such a channel if you increase its signal-to-noise ratio P N0W without limit? If so, what is that limit? [4 marks] (ii) Is there any limit to the capacity of such a channel if you can increase its bandwidth W in Hertz without limit, but while not changing N0 or P? If so, what is that limit? [3 marks] (d) For each of the four classes of signals in the left table below, identify its characteristic spectrum from the right table. ("Continuous" here means supported on the reals, i.e. at least piecewise continuous but not necessarily everywhere differentiable. "Periodic" means that under multiples of some finite shift the function remains unchanged.) Give your answer just in the form 1-A, 2-B, etc. Note that you have 24 different possibilities. [4 marks] Class Signal Type 1. continuous, aperiodic 2. continuous, periodic 3. discrete, aperiodic 4. discrete, periodic Class Spectral Characteristic A. continuous, aperiodic B. continuous, periodic C. discrete, aperiodic D. discrete, periodic (e) Define the Kolmogorov algorithmic complexity K of a string of data. What relationship is to be expected between the Kolmogorov complexity K and the Shannon entropy H for a given set of data? Give a reasonable estimate of the Kolmogorov complexity K of a fractal, and explain why it is reasonable. [3 marks

For each of the following areas, write brief comments on the way in which Java and its libraries have been designed to try to prevent programmers from making undetected errors and to ensure that code runs on all possible brands and models of computer, yielding the same results in each case. (a) Programmers who get mildly confused about syntax or who make typing errors. [4 marks] (b) Groups of programmers working on libraries that will form part of some large project. [4 marks] (c) Numbers, characters, trig functions and so on. [4 marks] (d) Opening files, reading or writing and then closing them. [4 marks] (e) Other features of Java not falling centrally within any of the above categories. [4 marks]

Give a brief summary of the main syntactic constructs found in the programming language Smalltalk. Other languages often have the conditional constructs if-then-else and while. Show how these two constructs can be defined in Smalltalk. [8 marks] Illustrate the use of Smalltalk by showing how you would define a method to compute the factorial of an integer. [8 marks] Although Smalltalk was originally designed to be an interpretive language, modern implementations are dramatically more efficient. Briefly outline what techniques might have been used to make this improvement.

(a) Brieflfly explain the difffferences between combinational and sequential logic.

[2 marks]

(b) With the aid of appropriate diagrams, brieflfly explain the operation of Moore

and Mealy fifinite state machines and highlight their difffferences. [6 marks]

(c) The state sequence for a binary counter is as follows:

The counter is to be implemented using four synchronously clocked D-type

flflip-flflops.

(i) Draw a state table for the counter, showing the required D inputs.

[4 marks]

(ii) Find expressions for the D inputs, making use of unused states if

appropriate. [6 marks]

(iii) What problem could occur when the counter circuit is powered-up? Give

two possible general methods for overcoming the problem. [2 marks]

(ii) dynamic hazard. [3 marks]

(b) Simplify the following expressions using Boolean algebra:

(i) X = (A + B + A . B).(A + B). A . B

(ii) Y = (A + B + A . B). C

[4 marks]

(c) Given:

F = A . B . C . D + A . C + B . C . D + B . C + A . C . D + A . B . C . D

(i) Show using a Karnaugh map that F can be simplifified to

F1 = A . B + A . B + A . C + B . C . D

[2 marks]

(ii) Show that there are a total of four possible expressions for F. [3 marks]

(iii) Show how F1 can be implemented using NAND gates and draw the circuit

diagram. Assume that complemented input variables are available.

[2 marks]

(iv) Show how the static 1 hazard in F1 can be eliminated using a Karnaugh

map-based approach. [2 marks]

(v) Now implement F1 assuming that only 2-input NAND gates are available.

[4 marks]

3 (TURN OVER)CST.2008.2.4

SECTION B

3 Discrete Mathematics

Let X and Y be sets. You are reminded that a relation from X to Y is a subset of

the product X Y .

(a) Explain what it means for a relation f from X to Y to be a function, an

injection and a surjection from X to Y . [4 marks]

(b) A bijection from X to Y is defifined to be a function from X to Y which is

both an injection and a surjection. Prove that a function f from X to Y is a

bijection iffff it has an inverse function g, i.e. g is a function from Y to X such

that g f = idX and f g = idY .

[Remember to prove both the "if" and "only if" parts of the assertion.]

[12 marks]

(c) Describe, without proof, a bijection from P(X Y ) to (X P(Y )) and its

inverse. [4 marks]

4CST.2008.2.5

4 Discrete Mathematics

Let I be a non-empty subset of the natural numbers N = {1, 2, 3, }.

The set S is defifined to be least subset of N such that

I S, and

if m, n S and m < n, then (n m) S.

Defifine h to be the least member of S. This question guides you through to a proof

that h coincides with the highest common factor of I, written hcf (I), and defifined

to be the natural number with the properties that

hcf (I) divides n for every element n I, and

if k is a natural number which divides n for every n I, then k

divides hcf (I).

[Throughout this question you may assume elementary facts about division.]

(a) The set S may also be described as the least subset of N closed under certain

rules. Describe the rules. Write down a principle of rule induction appropriate

for the set S. [4 marks]

(b) Show by rule induction that hcf (I) divides n for every n S. [3 marks]

(c) Let n S. Establish that

if p.h < n then (n p.h) S

for all non-negative integers p. [5 marks]

(d) Show that h divides n for every n S. [Hint: suppose otherwise and derive a

contradiction.] [5 marks]

(e) Explain very brieflfly why the results of parts (b) and (d) imply that h = hcf (I).

[3 marks]

5 (TURN OVER)CST.2008.2.6

SECTION C

5 Probability

(a) Suppose that X is a random variable whose value r is distributed Geometric(p).

Write down the expression for the probability P(X = r). [3 marks]

(b) By using a suitable generating function or otherwise, show that the expectation

The University Computing Service defifine a serious power outage as a power cut that

lasts for longer than their Uninterruptable Power Supply equipment can maintain

power. During the course of an academical year the number of serious power outages

is a random variable whose value is distributed Geometric(2/5). Accordingly, the

probability of having no serious power outages during the course of a year is 2/5.

(c) The University is investigating a compensation scheme which would make no

payment over the year if the number of serious power outages were zero or

one but which would pay the Computing Service 1000 for every such outage

(including the fifirst) if the total number of serious power outages in a year were

two or more. Determine the expected annual sum that the Computing Service

would receive. [8 marks]

(d) To what value would the parameter of the Geometric Distribution have to be

changed (from 2/5) for the expected annual sum to be 750? [4 marks]

6 Probability

(a) Give a brief account of the Trinomial Distribution and include in your

explanation an expression that is equivalent to n

!

r!(n

r)! prqnr for the Binomial

Distribution. [5 marks]

(b) An indicator light can be in one of three states: OFF, FLASHING and ON, with

probabilities 1/2, 2/5 and 1/10 respectively. A test panel has fifive such lights

whose states are mutually independent.

(i) What is the probability that all fifive lights are OFF? [3 marks]

(ii) What is the probability that three lights are OFF, one light is FLASHING

and one light is ON? [3 marks]

(iii) What is the probability that three or more lights are OFF and at most one

is ON? [9 marks]

All results must be expressed as fractions.

6CST.2008.2.7

SECTION D

7 Software Design

Software systems often incorporate structural representations of the application

domain in which they operate. For example, a vehicle control system should be

aware of the fact that the car has precisely four wheels. This kind of information

must be captured, encoded and tested at each stage of the software design process.

Using the number of wheels in a car as a simple example, describe relevant design

activities and products at each of the following phases of a software project:

(a) inception; [4 marks]

(b) elaboration; [4 marks]

(c) construction; [4 marks]

(d) transition; [4 marks]

(e) system operation. [4 marks]

8 Regular Languages and Finite Automata

(a) Explain what is a context-free grammar and the language it generates.

[4 marks]

(b) What does it mean for a context-free grammar to be regular? Given any

deterministic fifinite automaton M, describe a regular context-free grammar

that generates the language of strings accepted by M. [4 marks]

(c) Construct a non-deterministic fifinite automaton with -transitions whose

language of accepted strings is equal to the language over the alphabet {a, b, c}

generated by the context-free grammar with non-terminals q0 and q1, whose

start symbol is q0 and whose productions are q0 abq1, q1 , q1 q0 and

q1 abc. [4 marks]

(d) Is every language generated by a context-free grammar equal to the

set of strings accepted by some non-deterministic fifinite automaton with

-transitions? Justify your answer. (Any standard results about regular

languages you use should be carefully stated, but need not be proved.)

[8 marks]

7 (TURN OVER)CST.2008.2.8

9 Professional Practice and Ethics

(a) The British Computer Society Code of Conduct has four sections. What kind

of professional conduct does each section cover, and how does each of these

kinds of conduct benefifit the profession and its members? [8 marks]

(b) True or False questions:

(i) A User can provide occasional use of the University computer system for

a friend who is a temporary visitor.

(ii) Circumstances that mitigate minor infractions of the rules promulgated

by the Information Technology Syndicate include, among other things,

inebriation.

(iii) Appropriate use of the Cambridge University Data Network (CUDN)

means bona fifide academic activity plus a low level for private purposes.

(iv) Small amounts of commercial activity are acceptable as long as the User

is acting in a private capacity.

[4 marks]

(c) The IT industry is increasingly aware of its own environmental impact.

Describe at least one environmental problem to which the industry contributes

and how, as an IT professional, you can help to solve this problem. [4 marks]

(d) "Social engineering is a greater threat to computer security than computer

cracking software." What is social engineering and what measures can be

taken to guard against it? [2 marks]

(e) What is copyleft and how is it used to protect free, open-source, software?

(a) Brieflfly explain the difffferences between combinational and sequential logic.

[2 marks]

(b) With the aid of appropriate diagrams, brieflfly explain the operation of Moore

and Mealy fifinite state machines and highlight their difffferences. [6 marks]

(c) The state sequence for a binary counter is as follows:

The counter is to be implemented using four synchronously clocked D-type

flflip-flflops.

(i) Draw a state table for the counter, showing the required D inputs.

[4 marks]

(ii) Find expressions for the D inputs, making use of unused states if

appropriate. [6 marks]

(iii) What problem could occur when the counter circuit is powered-up? Give

two possible general methods for overcoming the problem. [2 marks]

2CST.2008.2.3

2 Digital Electronics

(a) With the aid of relevant diagrams, show the effffect on the output of a

combinational logic circuit of a:

(i) static hazard;

(ii) dynamic hazard. [3 marks]

(b) Simplify the following expressions using Boolean algebra:

[2 marks]

(ii) Show that there are a total of four possible expressions for F. [3 marks]

(iii) Show how F1 can be implemented using NAND gates and draw the circuit

diagram. Assume that complemented input variables are available.

[2 marks]

(iv) Show how the static 1 hazard in F1 can be eliminated using a Karnaugh

map-based approach. [2 marks]

(v) Now implement F1 assuming that only 2-input NAND gates are available.

[4 marks]

3 (TURN OVER)CST.2008.2.4

SECTION B

3 Discrete Mathematics

Let X and Y be sets. You are reminded that a relation from X to Y is a subset of

the product X Y .

(a) Explain what it means for a relation f from X to Y to be a function, an

injection and a surjection from X to Y . [4 marks]

(b) A bijection from X to Y is defifined to be a function from X to Y which is

both an injection and a surjection. Prove that a function f from X to Y is a

bijection iffff it has an inverse function g, i.e. g is a function from Y to X such

that g f = idX and f g = idY .

[Remember to prove both the "if" and "only if" parts of the assertion.]

[12 marks]

(c) Describe, without proof, a bijection from P(X Y ) to (X P(Y )) and its

inverse. [4 marks]

4CST.2008.2.5

4 Discrete Mathematics

Let I be a non-empty subset of the natural numbers N = {1, 2, 3, }.

The set S is defifined to be least subset of N such that

I S, and

if m, n S and m < n, then (n m) S.

Defifine h to be the least member of S. This question guides you through to a proof

that h coincides with the highest common factor of I, written hcf (I), and defifined

to be the natural number with the properties that

hcf (I) divides n for every element n I, and

if k is a natural number which divides n for every n I, then k

divides hcf (I).

[Throughout this question you may assume elementary facts about division.]

(a) The set S may also be described as the least subset of N closed under certain

rules. Describe the rules. Write down a principle of rule induction appropriate

for the set S. [4 marks]

(b) Show by rule induction that hcf (I) divides n for every n S. [3 marks]

(c) Let n S. Establish that

if p.h < n then (n p.h) S

for all non-negative integers p. [5 marks]

(d) Show that h divides n for every n S. [Hint: suppose otherwise and derive a

contradiction.] [5 marks]

(e) Explain very brieflfly why the results of parts (b) and (d) imply that h = hcf (I).

[3 marks]

5 (TURN OVER)CST.2008.2.6

SECTION C

5 Probability

(a) Suppose that X is a random variable whose value r is distributed Geometric(p).

Write down the expression for the probability P(X = r). [3 marks]

(b) By using a suitable generating function or otherwise, show that the expectation

E(X) = (1 p)/p. [5 marks]

The University Computing Service defifine a serious power outage as a power cut that

lasts for longer than their Uninterruptable Power Supply equipment can maintain

power. During the course of an academical year the number of serious power outages

is a random variable whose value is distributed Geometric(2/5). Accordingly, the

probability of having no serious power outages during the course of a year is 2/5.

(c) The University is investigating a compensation scheme which would make no

payment over the year if the number of serious power outages were zero or

one but which would pay the Computing Service 1000 for every such outage

(including the fifirst) if the total number of serious power outages in a year were

two or more. Determine the expected annual sum that the Computing Service

would receive. [8 marks]

(d) To what value would the parameter of the Geometric Distribution have to be

changed (from 2/5) for the expected annual sum to be 750? [4 marks]

6 Probability

(a) Give a brief account of the Trinomial Distribution and include in your

explanation an expression that is equivalent to n

!

r!(n

r)! prqnr for the Binomial

Distribution. [5 marks]

(b) An indicator light can be in one of three states: OFF, FLASHING and ON, with

probabilities 1/2, 2/5 and 1/10 respectively. A test panel has fifive such lights

whose states are mutually independent.

(i) What is the probability that all fifive lights are OFF? [3 marks]

(ii) What is the probability that three lights are OFF, one light is FLASHING

and one light is ON? [3 marks]

(iii) What is the probability that three or more lights are OFF and at most one

is ON? [9 marks]

All results must be expressed as fractions.

6CST.2008.2.7

SECTION D

7 Software Design

Software systems often incorporate structural representations of the application

domain in which they operate. For example, a vehicle control system should be

aware of the fact that the car has precisely four wheels. This kind of information

must be captured, encoded and tested at each stage of the software design process.

Using the number of wheels in a car as a simple example, describe relevant design

activities and products at each of the following phases of a software project:

(a) inception; [4 marks]

(b) elaboration; [4 marks]

(c) construction; [4 marks]

(d) transition; [4 marks]

(e) system operation. [4 marks]

8 Regular Languages and Finite Automata

(a) Explain what is a context-free grammar and the language it generates.

[4 marks]

(b) What does it mean for a context-free grammar to be regular? Given any

deterministic fifinite automaton M, describe a regular context-free grammar

that generates the language of strings accepted by M. [4 marks]

(c) Construct a non-deterministic fifinite automaton with -transitions whose

language of accepted strings is equal to the language over the alphabet {a, b, c}

generated by the context-free grammar with non-terminals q0 and q1, whose

start symbol is q0 and whose productions are q0 abq1, q1 , q1 q0 and

q1 abc. [4 marks]

(d) Is every language generated by a context-free grammar equal to the

set of strings accepted by some non-deterministic fifinite automaton with

-transitions? Justify your answer. (Any standard results about regular

languages you use should be carefully stated, but need not be proved.)

[8 marks]

7 (TURN OVER)CST.2008.2.8

9 Professional Practice and Ethics

(a) The British Computer Society Code of Conduct has four sections. What kind

of professional conduct does each section cover, and how does each of these

kinds of conduct benefifit the profession and its members? [8 marks]

(b) True or False questions:

(i) A User can provide occasional use of the University computer system for

a friend who is a temporary visitor.

(ii) Circumstances that mitigate minor infractions of the rules promulgated

by the Information Technology Syndicate include, among other things,

inebriation.

(iii) Appropriate use of the Cambridge University Data Network (CUDN)

means bona fifide academic activity plus a low level for private purposes.

(iv) Small amounts of commercial activity are acceptable as long as the User

is acting in a private capacity.

[4 marks]

(c) The IT industry is increasingly aware of its own environmental impact.

Describe at least one environmental problem to which the industry contributes

and how, as an IT professional, you can help to solve this problem. [4 marks]

(d) "Social engineering is a greater threat to computer security than computer

cracking software." What is social engineering and what measures can be

taken to guard against it? [2 marks]

(e) What is copyleft and how is it used to protect free, open-source, software?

(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 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 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:

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.

public static void main0 { //Create PetProgram object //create Scanner object I/Declare a String for the name, a String for the type, and an int for the age of the pet. (these values can also be global variables, but they make more sense aslocal vars) // Initialize the Pet variable I/Print a statement to the screen asking the user to input the name, type, and age of pet /Use Scanner object to read in the name String and store it in the name var. I/Use Scanner object to read in the type String and store it in the type var. //Use Scanner object to read in the age int and store it in the age var. //Use setName) mutator to give the pet the name that the user has entered //Use setType0 //Use setAge0 //Use a print statement and getName0, getIype), and getAge) to display the pet's info to the user. return Class Pet //Declare a String for the name, a String for the type, and an int for the age of the pet. public void Pet{String newName, String newlype, int newAge) {/t's good programming practice to give these variables different names than the global values I/name = newName type = newType /age = newAge retun public void setName(String newName /name = newName public void setType(String newType Itype = newType public void setAgeint newAge /age = newAge

kindly answer all the questions