Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Feb 01, 2024

Consider the trigonometric series a0 2 + X r=1 (ar cos rx + br sin rx) where a0, a1, a2, . . . and b1,

Consider the trigonometric series a0 2 + X r=1 (ar cos rx + br sin rx) where a0, a1, a2, . . . and b1, b2, . . . are constants and suppose that f(x) is a periodic function of x with period 2. (a) State expressions for the constants a0, ar, br (r = 1, 2, . . .) so that the trigonometric series forms the Fourier series of f(x) over the interval < x 6 . Such expressions are then known as the Fourier coefficients of f(x). [4 marks] (b) State the Dirichlet conditions on the function f(x) for it to be represented by its Fourier series at all points in the interval < x 6 at which the function f(x) is continuous. [2 marks] (c) Determine simplified expressions for the Fourier coefficients when the function f(x) is an even function of x. [3 marks] (d) Consider the function f(x) which is periodic with period 2 and is defined by f(x) = x 2 in the interval < x 6 . Does the function f(x) satisfy the Dirichlet conditions? Briefly justify your answer. [2 marks] (e) Determine the Fourier series for this function f(x). [6 marks] (f ) By substituting a suitable value for x in the Fourier series show that 2 12 = X r=1 (1)r+1

Explain how the relation of observational congruence (=) between CCS agents is defined in terms of observation equivalence (). [2 marks] Say that an agent can deadlock if it can perform a sequence of actions to become an agent observationally congruent to 0. For any agent P, show that P = 0 if and only if P can do no action. Hence write down a process logic proposition such that P satisfies if and only if P can deadlock. [6 marks] Let C def = g0.g1.p0.p1.C D def = g1.g0.p1.p0.D S0 def = g0 .p0 .S0 S1 def = g1 .p1 .S1 For each of the following agents, determine whether or not it can deadlock: (a) (C|C|S0|S1) \ {g0, p0, g1, p1} (b) (C|D|S0|S1) \ marks] Prove that T 0, where T def = .T. Hence, or otherwise, show that it is possible for an agent that can deadlock to be observationally congruent to one that cannot deadlock.

For each of the following ML definitions write, explain and comment on the closest reasonable Java equivalent code-fragment that you can construct. (a) fun fact n r = if n = 0 then r else fact (n-ception Disaster of int; raise Disaster 99; [4 marks] (e) fun recursiveLength nil = 0 | recursiveLength (a :: b) = 1 + recursiveLength b; [4 marks]

(a) Briefly explain the concept of coroutines as used in BCPL and outline the effect of the library functions createco(f, size), deleteco(ctpr), callco(cptr, val) and cowait(val). [10 marks] (b) Outline how you would design a coroutine to merge, in increasing order, two infinite streams of increasing integers supplied by two other coroutines. [5 marks] (c) Briefly outline how you would implement an analogous merging mechanism in an object-oriented language, such as Java, that does not provide a coroutine mechanism.

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

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:

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

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

[4 marks]

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]

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]

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.

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]

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

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]

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]

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

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.