State what is meant by a directed graph and a strongly connected component.

Illustrate your description by giving an example of such a graph with 8 vertices

 

and 12 edges that has three strongly connected components. ?

 

(b) Describe, in detail, an algorithm to perform a depth-fifirst search over such a

graph. Your algorithm should attach the discovery and fifinishing times to each

vertex and leave a representation of the depth-fifirst spanning tree embedded

within the graph. [5 marks]

(c) Describe an O(n) algorithm to discover all the strongly connected components

of a given directed graph and explain why it is correct. You may fifind it useful

to use the concept of the forefather (v) of a vertex v which is the vertex, u,

with highest fifinishing time for which there exists a (possibly zero length) path

from v to u. [10 marks]

2 Computer Design

(a) What is a data cache and what properties of data access does it exploit?

[5 marks]

(b) What is a direct mapped cache and under what conditions will it exhibit poor

performance? [5 marks]

(c) Under what circumstances might a word of data in main memory be

simultaneously held in two separate fifirst-level cache lines? [5 marks]

(d) A translation look aside buffffer is a specialised cache. What does it typically

store and why is it often a factor of 1000 smaller than a data cache? [5 marks]

2CST.2001.6.3

3 Digital Communication I

(a) Defifine the terms circuit and packet in the context of communication systems.

[5 marks]

(b) What sort of guarantee does circuit switching provide? [5 marks]

(c) What advantages does packet switching provide over circuit switching?

[5 marks]

(d) Which of frequency division multiplexing, time division multiplexing and code

division multiplexing lend themselves to circuit switching? Which to packet

switching? Explain why or why not in each case. [5 marks]

4 Computer Graphics and Image Processing

(a) Describe the z-buffffer polygon scan conversion algorithm. [10 marks]

(b) In ray tracing, once we have determined where a ray strikes an object, the

illumination at the intersection point can be calculated using the formula:

Explain what real effffect each of the three terms is trying to model and explain

what each of the following symbols means, within the context of this formula:

I, Ia, i, Ii , ka, kd, ks,Li, N, Ri, V, n

[10 marks]

3

[TURN OVERCST.2001.6.4

SECTION B

5 Comparative Programming Languages

(a) Brieflfly explain the concept of coroutines as used in BCPL and outline

the effffect 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

infifinite streams of increasing integers supplied by two other coroutines.

[5 marks]

(c) Brieflfly outline how you would implement an analogous merging mechanism in

an object-oriented language, such as Java, that does not provide a coroutine

mechanism. [5 marks]

6 Compiler Construction

(a) Describe one possible structure (e.g. ELF) of an object fifile. Illustrate your

answer by considering the form of object fifile which might result from the

following C program.

int a = 1, b = -1;

extern int g(int);

extern int c;

int f() { return g(a-b) + c; }

It is not necessary to consider the exact instruction sequence, just issues

concerning its interaction with the object fifile format. [10 marks]

(b) Describe how a linker takes a sequence of such programs and produces an

executable fifile. [4 marks]

(c) Compare and contrast static and dynamic linking in a system using your object

fifile format. [6 marks]

4CST.2001.6.5

7 Prolog for Artifificial Intelligence

A weighted binary tree can be defifined using compound terms in the following way.

A node of the tree is represented by the term n(V, L, R), where V stands for the

value of the node, and L and R stand for the left and right branches, respectively.

A terminal node has the R and L components instantiated to the null list.

Given an input tree T, write a Prolog program that constructs a tree of the same

shape as T, but in which the value of each node has been set to the value of the

maximum value node in T.

[Note: Maximum marks are available only for programs that perform this task in

one recursive descent of the input tree, and which use no more than four clauses.]

[20 marks]

5

[TURN OVERCST.2001.6.6

8 Databases

The environmental agency is setting up an SQL database to monitor long-term

trends in the climate. Data are collected from observatories of a number of difffferent

kinds.

Flood risk is of particular concern. Each water authority measures river levels and

rates of flflow hourly at major points, and records reservoir levels daily.

In addition, the agency maintains weather stations both inland and at sea. These

record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind.

Values of new precipitation, temperature, pressure, and wind speed and direction

are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur.

Maximum and minimum temperature and pressure, the total number of hours of

sunshine and the total precipitation are recorded daily. Inland stations can be

grouped by water authority.

By default these primary data will be relegated to archive after 2 years. Selected

information is retained permanently in a data warehouse. This serves two purposes.

First, it holds monthly summary data consisting of the maximum (and minimum

as appropriate) day value for each statistic, together with the monthly totals of

sunshine and precipitation. The warehouse also keeps detailed information relating

to periods of extreme weather from the relevant observatories, with one or more

keywords describing the nature of the incident (flflood, blizzard, hurricane etc.) and

an optional comment.

Write notes to assist in the design of the schema for the relational data warehouse,

including any diagrams that you fifind helpful. Explain how your design will enable

meteorologists to fifind relevant past records, noting any assumptions that you make

about the nature of the data.

[You should not go into unnecessary detail about the structure of the primary

database. You may assume that expert meteorologists will select the data for the

warehouse.]

[20 marks]

6CST.2001.6.7

SECTION C

9 Semantics of Programming Languages

Write short notes on four of the following fifive topics.

(a) The relationship between three forms of operational semantics of the Language

of Commands (LC) given by

an evaluation relation h P, si hV, s0 i

a transition relation h P, si hP0 , s0 i

a transition relation between the confifigurations

h c, r, si of the

SMC-machine

(b) The notion of semantic equivalence of LC phrases and its congruence property.

(c) Call-by-name and call-by-value rules for evaluating function applications in the

Language of Functions and Procedures (LFP) and the relationship between the

evaluation relations for LFP based upon each of them.

(d) The notion of bisimilarity of two confifigurations in a labelled transition system.

(e) The rules defifining the possible labelled transitions of parallel composition

(P1|P2) and restriction ( c . P) in the Language of Communicating Processes

(LCP).

[5 marks each]

7

[TURN OVERCST.2001.6.8

10 Foundations of Functional Programming

The following are some concepts that have flflourished in the context of functional

programming but which have (so far) been less heavily used in main-stream

languages even when they have been available:

(a) polymorphic types

(b) type reconstruction

(c) higher-order functions

(d) lazy evaluation

(e) continuations

For each case give a brief explanation of the facility referred to, suggest a

circumstance in which it might be useful and comment on how immediately relevant

to non-functional languages it seems.

[4 marks per part]

8CST.2001.6.9

11 Logic and Proof

(a) In the context of clause-based proof methods, defifine the notion of pure literal

and describe what should be done if the set of clauses contains pure literals.

[3 marks]

(b) Use the Davis-Putnam method to discover whether the following set of clauses

is satisfifiable. If they are satisfifiable, show a satisfying interpretation.

{P, R} {P, R} {P, Q} {Q, R} {P, Q, R}

[6 marks]

(c) The three-fifingered inhabitants of the planet Triterra build base-3 computers.

A Triterran named Randal Tryant has found a way of verifying base-3

combinational logic. His Ordered Ternary Decision Diagrams (OTDDs) are

the same as a technology used on planet Earth except that all variables and

expressions range over the values 0, 1 and 2 instead of just 0 and 1.

(i) Describe how a full ternary decision tree can be reduced to an OTDD

without regard for effiffifficiency. [2 marks]

(ii) Sketch an effiffifficient algorithm to convert a ternary expression directly to an

OTDD without constructing the full decision tree. For a typical ternary

connective use modulo-3 multiplication, written as . [6 marks]

(iii) Demonstrate your algorithm by applying it to the ternary expression

((i i) j) 2. [3 marks]

9

[TURN OVERCST.2001.6.10

12 Complexity Theory

(a) Show that any language that can be accepted by a nondeterministic machine

in time f(n) can also be decided by a deterministic machine in space O(f(n)).

[4 marks]

(b) Show that any language that can be accepted by a nondeterministic machine

in space f(n) can also be decided by a deterministic machine in time

O(c(f(n)+log n) ), for some constant c. [6 marks]

(c) Explain what the above results tell us about the inclusion relationships among

the complexity classes:

NL, co-NL, P, NP, PSPACE and NPSPACE

[4 marks]

(d) It has been proved that the graph reachability problem is in co-NL. What

further inclusions can you derive among the above complexity classes using

this fact? Explain your answer. [6 marks]

Continuous Mathematics

The complex form of the Fourier series is:

f(x) =

+

X

k=

ckei2kx

where ck is a complex number and ck = ck.

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

coeffiffifficients, Ak and k, in the alternative form:

f(x) =

+

X

k

=0

Ak cos(2kx k)

[10 marks]

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

(c) Explain how the coeffiffifficients, ck, of the Fourier series of the periodic function,

f(x):

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

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

otherwise

[8 marks]

2 Concurrent Systems

An interprocess communication environment is based on synchronous message

passing. A server is to be designed to support a moderate number of simultaneous

client requests.

Clients send a request message to the server, continue in parallel with server

operation, then wait for the server's reply message.

Discuss the design of the server's interaction with the clients. Include any problems

you foresee and discuss alternative solutions to them. [20 marks]

2CST.2001.4.3

3 Further Java

(a) Describe how mutual-exclusion locks provided by the synchronized keyword

can be used to control access to shared data structures. In particular you

should be clear about the behaviour of concurrent invocations of difffferent

synchronized methods on the same object, or of the same synchronized method

on difffferent objects. [6 marks]

(b) Consider the following class defifinition:

class Example implements Runnable {

public static Object o = new Object();

int count = 0;

public void run() {

while (true) {

synchronized (o) {

Show how to start two threads, each executing this run method. [2 marks]

(c) When this program is executed, only one of the count fifields is found to

increment, even though threads are scheduled preemptively. Why might this

be? [2 marks]

(d) Defifine a new class FairLock. Each instance should support two methods, lock

and unlock, which acquire and release a mutual exclusion lock such that calls

to unlock never block the caller, but will allow the longest-waiting blocked

thread to acquire the lock. The lock should be recursive, meaning that the

thread holding the lock may make multiple calls to lock without blocking.

The lock is released only when a matched number of unlock operations have

been made.

You may wish to make use of the fact the Thread.currentThread() returns

the instance of Thread that is currently executing. [10 marks]

3

[TURN OVERCST.2001.4.4

4 Compiler Construction

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

f

where C repeatwhile E has the same meaning as do C while E in C or Java.

(a) List the terminals and non-terminals of this grammar and explain the

signifificance of S. [3 marks]

(b) Identify any ambiguities in the above grammar and rewrite it to remove them,

ensuring that your new grammar generates exactly the same set of strings.

[4 marks]

(c) Specify a suitable abstract syntax, for example by giving a type declaration

in a programming language of your choice, which might be used to hold parse

trees for this language. [3 marks]

(d) Give either a recursive descent parser or a characteristic fifinite state machine

(e.g. for SLR(1)) with associated parser for your grammar. Your parser need

not return a parse treeit suffiffiffices for your parser either to accept or to reject

the input string. [10 marks]

4CST.2001.4.5

5 Data Structures and Algorithms

(a) Outline how you would determine whether the next line segment turns left or

right during the Graham scan phase of the standard method of computing the

convex hull of a set of points in a plane. [5 marks]

(b) Describe in detail an effiffifficient algorithm to determine how often the substring

ABRACADABRA occurs in a vector of 106 characters. Your algorithm should be

as effiffifficient as possible. [10 marks]

(c) Roughly estimate how many character comparisons would be made when your

algorithm for part (b) is applied to a vector containing 106 characters uniformly

distributed from the 26 letters A to Z. [5 marks]

6 ECAD

(a) When designing clocked circuits there are times when asynchronous inputs

have to be sampled which may result in metastable behaviour in state holding

elements. How might metastability be avoided when sampling asynchronous

inputs? [5 marks]

(b) An optical shaft encoder (e.g. used on the internal rollers of a mechanical

mouse) consists of a disk with an evenly spaced alternating transparent and

opaque grating around the circumference. Two optical sensors are positioned

such that when one sensor is at the middle of an opaque region, the other

is at the edge. Consequently, the following Gray code sequence is produced,

depending upon the direction of rotation:

positive rotation

negative rotation

time

A shaft decoder module is required to convert the Gray code into an 8-bit

position. The 8-bit position should be incremented every time the input

changes from one state to another in a positive direction (e.g. from 00 to

01, or from 10 to 00). Similarly, the 8-bit position should be decremented

every time the input changes from one state to another in a negative direction

(e.g. from 00 to 10, or from 01 to 00).

Write and comment a Verilog module which performs the function of a shaft

decoder. [15 marks]

5

[TURN OVERCST.2001.4.6

7 Operating System Functions

(a) In the context of virtual memory management:

(i) What is demand paging? How is it implemented? [4 marks]

(ii) What is meant by temporal locality of reference? [2 marks]

(iii) How does the assumption of temporal locality of reference inflfluence page

replacement decisions? Illustrate your answer by brieflfly describing an

appropriate page replacement algorithm or algorithms. [3 marks]

(iv) What is meant by spatial locality of reference? [2 marks]

(v) In what ways does the assumption of spatial locality of reference inflfluence

the design of the virtual memory system? [3 marks]

(b) A student suggests that the virtual memory system should really deal with

"objects" or "procedures" rather than with pages. Make arguments both for

and against this suggestion. [4 and 2 marks respectively]

.

6CST.2001.4.7

8 Computation Theory

(a) Defifine precisely what is meant by the following:

(i) f(x1, x2, . . . xn) is a Primitive Recursive (PR) function of arity n.

[5 marks]

(ii) f(x1, x2, . . . xn) is a Total Recursive (TR) function of arity n. [3 marks]

(b) Ackermann's function is defifined by the following recursive scheme:

f(0, y) = S(y) = y + 1

f(x + 1, 0) = f(x, 1)

f(x + 1, y + 1) = f(x, f(x + 1, y))

For fifixed n defifine

gn(y) = f(n, y).

Show that for all n, y N,

gn+1(y) = gn(y+1)(1),

where h(k)(z) is the result of k repeated applications of the function h to initial

argument z. [4 marks]

(c) Hence or otherwise show that for all n N, gn(y) is a PR function. [4 marks]

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

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

7

[TURN OVERCST.2001.4.8

9 Numerical Analysis I

(a) What is meant by a symmetric positive defifinite matrix ? [3 marks]

(b) Verify that A = 2 1

1 2 is positive defifinite. [4 marks]

(c) The Choleski factorisation A = LDLT is to be applied to the solution of

. Form the

upper triangular system of equations needed to complete the solution.

[4 marks]

(d) Solve these equations. [2 marks]

(e) What is meant by the order of convergence of an iterative process? [1 mark]

(f ) State the Newton-Raphson formula for solving f(x) = 0 for scalar x. What is

the order of convergence of this method? [2 marks]

(g) This method is used to solve f(x) = x2 4 = 0 using IEEE Double Precision

with a certain starting value x0. It is found that the third iterate x3 ' 2.0006,

and x4 ' 2.00000009. Very roughly, how many signifificant decimal digits of

accuracy would you expect in x5? Explain your answer. [4 marks]

8CST.2001.4.9

10 Computer Graphics and Image Processing

(a) Describe an algorithm to draw a straight line using only integer arithmetic.

You may assume that the line is in the fifirst octant, that the line starts and

ends at integer co-ordinates, and that the function setpixel(x, y) turns on the

pixel at location (x, y). [8 marks]

(b) Describe Douglas and Pucker's algorithm for removing superflfluous points from

a line chain. [10 marks]

(c) Under what circumstances would it be sensible to employ Douglas and Pucker's

algorithm?

(a) A combinational logic circuit takes a 4-bit unsigned binary integer number at its

inputs labelled D3 , D2 , D1 and D0 , where D3 is the most signifificant bit. For

decimal input 1, 2, 3, 5, 7, 11 and 13, the output S is to be at logic 1, and it is

to be at logic 0 otherwise.

(i) Write down the truth table for the required combinational logic function.

(ii) Using a Karnaugh map, determine the simplifified Boolean expression for the

output S in terms of the inputs D3 to D0 in a minimum sum-of-products

form.

(iii) Describe what is meant by an essential term in a Karnaugh map. Write

down the essential terms for the Karnaugh map in (ii).

(iv) Using a Karnaugh map, this time determine the required simplifified Boolean

expression for the output S in a minimum product-of-sums form.

[10 marks]

(b) Provide a circuit diagram which implements the following Boolean function using

only NAND gates

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

that has the don't care states: A.B.C.D, A.B.C.D, A.B.C.D and A.B.C.D

[4 marks]

(c) Show that

(X + Y ).(X + Z) = X + Y.Z

(X + Y ).(X + Z) = X.Z + X.Y

Using these results or otherwise, simplify the following expression

P = (A + B + C).(A + B + D).(A + B + E).(A + D + E).(A + C)

[6 marks]

2CST.2014.2.3

2

Digital Electronics

(a) Show how two NOR gates may be connected to form an RS latch. Describe

its operation and give a table relating its inputs to its outputs. How could you

use this circuit to eliminate the effffect of contact bounce in a single pole double

throw switch supplying an input to a digital logic circuit? [6 marks]

(b) The state sequence for a particular 4-bit binary up-counter is as follows:

Show how four negative edge triggered T-type flflip-flflops (FFs) with outputs

labelled QA , QB , QC and QD can be used to implement a ripple counter having

the specifified state sequence. Show any combinational logic necessary assuming

that the FFs have asynchronous reset inputs available. [4 marks]

(c) Using the principles of synchronous design, determine the next state combi

national logic expressions required to implement a counter having the state

sequence specifified in part (b ). Assume that D-type FFs are to be used and

that unused states do not occur. [4 marks]

(d) Explain carefully what happens if the counter in (c ) starts in state 1 1 1 0 . In

general, how can start-up problems be overcome in the design of synchronous

state machines? [4 marks]

(e) What are the advantages and disadvantages of the synchronous design in part

(c ) compared with the alternative design in part (b )? [2 marks]

3 (TURN OVER)CST.2014.2.4

SECTION B

3

Operating Systems

One goal of a multiuser operating system is to protect each user's information and

activity from damage caused by accidental or deliberate actions of other users of the

system.

(a) Describe a mechanism that operating systems use to reduce the opportunity for

a user process to prevent another user's process from making progress. In your

description include any particular hardware features that are relied upon.

[3 marks]

(b) Describe two alternative mechanisms that operating systems could use to reduce

the opportunity for a user process to access or corrupt the information being used

by another user's process. In your descriptions include any particular hardware

features that are relied upon. [6 marks]

(c) Describe how an operating system might attempt to ensure that long-term user

information (that is, information which exists beyond process execution) is not

interfered with or misused by other users. Your description should be clear

about when actions are performed and the resources they consume. [5 marks]

(d) To what extent are the mechanisms described above useful in single user

systems? [3 marks]

(e) How do operating systems ensure that they are not themselves overly-restricted

by these mechanisms? [3 marks]

4CST.2014.2.5

4

Operating Systems

(a) Describe the difffference between blocking and nonblocking input/output opera

tions. How can an operating system improve the performance (as seen by a

process) of blocking operations? [4 marks]

(b) A privileged process is given raw access to a slow disk device. It reads a page from

the disk (using a blocking operation), processes the information and repeats.

Suppose a read takes 3 units of time and the processing 2 units of time, so

that reading a block and processing takes 5 units of elapsed time. Assuming

the machine is otherwise idle, how can this elasped time be reduced? State any

assumptions about hardware features you are making. [5 marks]

(c) Describe how polled I/O works and state its disadvantages. Under what

conditions is polling a sensible approach? Describe an alternative approach.

(You may fifind it helpful to provide a few lines of psuedo code.) [4 marks]

(d) What advantages does direct memory access (DMA) provide? Describe its

operation as seen by a device driver in the operating system. (You may fifind

it helpful to write a few lines of psuedo code.) [5 marks]

(e) To what extent does heterogeneity in I/O systems add complexity to an

operating system? [2 marks]

5 (TURN OVER)CST.2014.2.6

SECTION C

5

Software and Interface Design

(a) Defifine brieflfly, for each of the following techniques, what its purpose is and how

it is conducted.

(i) Regression testing

(ii) A/B testing

(iii) Unit testing

(iv) Load testing

[12 marks]

(b) Although each of these techniques can provide new information of value to a

software project, costs can be reduced if information is available earlier in the

design cycle. For each of the four techniques in part (a), suggest a method by

which some of the resulting information could be obtained earlier in the project.

[8 marks]

6CST.2014.2.7

6

Software and Interface Design

The following is an extract from a design brief written by the client for one of the

2014 Cambridge group design projects.

What I'd like is some sort of database of recipes to which I can send queries such

as "Find me something that doesn't contain cabbage or tomatoes that takes less than

30 minutes to prepare", or "I've got kohlrabi in the veg box AGAIN, are there any

recipes I haven't tried that might make something edible out of it?", or "I've actually

got a couple of hours free to cook this weekend, what was that complicated Ottolenghi

recipe I flflagged two weeks ago to try later?". The database needs to cope with the fact

that ingredients can have difffferent names but mean the same thing: e.g. "flflour" and

"plain flflour", and that "1/4 lb" and "4oz" are the same thing and equal to "100g"

(and not 113g). It would be great if once I've chosen this week's menu, it could

produce a shopping list I can plug into www.myfavouritesupermarket.com, and it

needs to be usable by non-engineers.

(a) For each of the following software project phases, suggest a design model or

representation that would be a helpful aid in the design process. For each of

these, sketch an example to show what this model looks like, based on some part

of the above design brief.

(i) Inception phase

(ii) Elaboration phase

(iii) Construction phase

(iv) Transition phase