In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net continues to iterate in response to a given input? [3 marks] (ii) How many stable content-addressable memories would you expect a fully connected Hopfield network consisting of neurons to be capable of storing? [1 mark] (iii) What property of those memory patterns would make it most probable that you could successfully train the network to store the maximum number, and why? [3 marks] (b) Explain how five independent dimensions of visual processing are multiplexed together into the three available spatial dimensions of neural tissue, by the structure of the cubic millimetre hypercolumns in the brain's visual cortex. [5 marks] (c) The retina is often regarded as an image capture device; but it has about 100 million input sensors (photoreceptors) yet only 1 million output fibres (optic nerve axons). What are some implications of this 100-to-1 ratio of input channels to output channels? [4 marks] (d) Provide some quantitative evidence and arguments supporting the proposition that: "Connectivity is the basic computational principle in the brain". [4 m

The network is represented as a directed graph, with a vertex for each bus stop, and edges between adjacent stops along a route. For each edge j {1, . . . , p} let the travel time be dj . The following ticketing data is available: for each trip i {1, . . . , n}, we know its start time si , its end time fi , and also the list of edges it traverses. The total trip duration is the sum of travel times along its edges. We shall estimate the dj using linear least squares estimation, i.e. solve arg min ky Xk 2 for a suitable matrix X and vectors and y. (i) Give an example of ticket data for a trip traversing 5 edges, and write the corresponding equation of its residual. [1 mark] (ii) Give the dimensions and contents of X, , and y for this problem. State a condition on X that ensures we can solve for . [3 marks] (iii) Give an example with p = 2 and n = 3 for which it is not possible to estimate the dj . Compute XT X for your example. [2 marks] (c) Let A be an n n matrix with real entries. (i) We say that A is diagonalisable if there exists an invertible n n matrix P such that the matrix D = P 1AP is diagonal. Show that if A is diagonalisable and has only one eigenvalue then A is a constant multiple of the identity matrix. [3 marks] (ii) Let A be such that when acting on vectors x = [x1, x2, . . . , xn] T it gives Ax = [x1, x1 x2, x2 x3, . . . , xn1 Write out the contents of A and find its eigenvalues and eigenvectors. Scale the eigenvectors so they have unit length (i.e. so their magnitude is equal to 1). [6 marks]

A and B are finite sets with |A| = m, and |B| = n. How many partial functions are there from A to B? Why? 2 How many different ways are there to make up a basket of 15 fruit from apples, pears, oranges and bananas? 3 Explain, without writing a program, Euclid's algorithm for greatest common divisor. 4 Simplify (A B) (A B) (A B). 5 Given a distribution P(X = r) = r r! e , what is the expectation E(X)? 6 What is the probability that the scores on two dice sum to 8? 7 Following the ML definition fun tw f x = f(f(x)), what is the type of tw? 1 Can the following circuit exhibit a static hazard and if so when? A A C B 9 What is a tri-state buffer, how does it differ from more ordinary logic gates and how is it used? 10 Given a CARDINAL variable n, write Modula-3 code to declare and initialise a variable p to point to an array of n REALs. 11 Write a Modula-3 type definition for a linked list of INTEGERs. 12 Following the ML definition fun f g [y,z] = g(y+1, z) what is the type of f? 13 What three new offences were created under the Computer Misuse Act of 1990? 14 Systems engineers use the terms "availability" and "reliability". Explain the distinction they make between them. 15 List four essential differences between a software engineering project and a civil engineering project such as building a skyscraper. 16 Verify (A B) \ (A B) = (A B) (A B). 17 A, B, C are arbitrary events which occur with probability P(A), P(B), and P(C). Write an expression for the event that only one of them occurs. You do not need to express its probability. 18 If the probability of having a boy is 1 2 what is the probability that a family of 4 children has more boys than girls? (Ignore the possibility of multiple births.) 19 Give a finite deterministic automaton with alphabet of input symbols {a, b} that accepts the language denoted by the regular expression a . 20 If L is a regular language over an alphabet , explain why the complement {w |w / L} is also a regular language. B 21 Digital Electronics and Computer Design Explain the terms "minterm" and "prime implicant". A number of Boolean functions conform to the map shown below: A B C = 0 = 1 = unspecified Exhibit maps and minimum "sum of product" expressions for the following particular functions: (a) F1, being a function of two variables; (b) F2, having four minterms; (c) F3, having two prime implicants; (d) F4, having a prime implicant that can not appear in the minimum "sum of products" representation. [20 marks] 3 [TURN OVER CST.95.2.4 22 Digital Electronics and Computer Design A sequential circuit has been built, and it behaves slightly erratically. When switched on it produces on its three output wires one of the following patterns: 000 001 100 110 011 000 010 101 111 010 or The second pattern is not intended to arise. Deduce the circuit details and propose a modification that ensures that in due course the circuit will always settle into the cycle shown in the first pattern. [20 marks] SECTION C 23 Probability Two gamblers play a game which involves tossing a fair coin. After t2 tosses the first gambler has scored k wins. If there is no record of the sequence of tosses, what probability distribution describes the situation after t1 tosses (t1 < t2)? If the game is tied after eight tosses, show that the probability that it was tied after four is 18 35 . [20 marks] 4 CST.95.2.5 24 Probability Find the probability generating function of the discrete uniform random variable X distributed on {a, a + 1, a + 2, ...b 1, b} A tail generating function T(s) for a discrete random variable X is defined as T(s) = X n= P(X > n)s n Give the relation between a probability generating function and the tail generating function for X > n, and hence obtain the tail generating function in this case. [20 marks] SECTION D 25 Professional Practice and Ethics How is private ownership of software justified? What laws are used to protect software ownership? Are there any workable alternatives to private ownership of software? [20 marks] 26 Software Engineering Describe the process of specifying a major piece of software: the main documents produced, their immediate purpose and their ongoing role in the software life cycle. Describe the role that formal methods can play at each stage of the software life cycle. Explain any disadvantages of the uses of formal methods that you have discussed. [20 marks] 5 [TURN OVER CST.95.2.6 27 Regular Languages and Finite Automata Prove or disprove each of the following statements, stating clearly any well known results that you use. (a) The set of strings over the alphabet {0, 1} that contain exactly twice as many occurrences of 0 as of 1 is a regular language; (b) Let L be a regular language over an alphabet . Then the language consisting of those u such that there is some v with uv L, is also a regular language; (b) Any finite subset of {a, b} is a regular language; (d) For any regular expressions r and s, the regular expressions (r s ) and (r|s) always denote the same language. [20 marks] 28 Unix Case Study What is an i-node and what information is contained in it? Describe how named files are mapped to i-nodes. How is the information associating disc blocks with i-nodes represented? What restrictions are placed on name to i-node links to simplify file system recovery? [20 mar

Consider a database with one binary relation B. (a) Write programs in stratified Datalog for the following queries: (i) Give the set of elements x for which there are fewer than three elements y such that B(x, y). [3 marks] (ii) Give the set of elements x such that there is no path (in the graph formed by B) from x back to itself. [3 marks] (iii) Give the set of elements x such that B(x, y) for every y. [3 marks] (b) Which of the queries defined in part (a) is: (i) safe? [3 marks] (ii) domain independent? [4 marks] (iii) monotone? [4 marks] In each case, justify your answer fully

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]

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

(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

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

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

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

kindly answer all the questions