Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Oct 16, 2024

(a) In SystemVerilog, what is the difference between: (i) The ternary operator ? and if...then...else statements? [2 marks] (ii) always_ff and always_comb? [2 marks] (iii)

(a) In SystemVerilog, what is the difference between: (i) The ternary operator ? and if...then...else statements? [2 marks] (ii) always_ff and always_comb? [2 marks] (iii) Blocking, non-blocking and continuous assignment? [3 marks] (iv) Logic values 0, 1, x and z and how these values propagate through Boolean logic gates? [3 marks] (v) The way that synchronous and asynchronous reset are declared in an always_ff statement? [2 marks] (b) The following module attempts to implement a reset control circuit that should have the following behaviour: when the user-controlled reset button (which needs to be debounced) is pressed the asyncButton signal is high and should result in the rst going high and remaining high for a minimum of 106 clock cycles. rst should be generated immediately after the rising clock edge to allow time for it to propagate. module timeResetBad(input logic clk, input logic asyncButton, output logic rst); logic ctr [18:0]; logic ctrAtMax; always_comb begin ctrAtMax = &ctr; rst = !ctrAtMax; end always_ff @(posedge clk) ctr <= asyncButton ? 0 : !ctrAtMax ? ctr+1 : ctr; endmodule (i) What is wrong with the timeResetBad module? [4 marks] (ii) Write a corrected version timeResetBad that makes minimal changes and adds no new modules.

The standard linear regression model uses a hypothesis

h(x, w, b) = wT x + b

to fifit m examples ((x1, y1), . . . ,(xm, ym)) by minimizing the error

E(w, b) =

i=1

(yi h(xi, w, b))2 .

(a) Derive a gradient descent algorithm for training the linear regression model

described. [5 marks]

(b) In the application of interest, you believe that it is desirable to train such that

the learned parameters have ||w|| ' 1. Suggest a modifification to E(w, b) that

facilitates this, and derive the corresponding gradient descent training algorithm.

[5 marks]

(d) You are faced with a heuristic search problem, but the heuristics you have so far

developed are less effffective than desired. Suggest two ways in which supervised

machine learning might be used to develop a better heuristic, mentioning if

necessary any corresponding disadvantages of using the approach. You may

assume that a collection of problems to be solved by the heuristic search is

available. [6 marks]

2CST1.2021.6.3

Artifificial Intelligence

A Boolean satisfifiability problem has four variables, x1, x2, x3 and x4. A literal l

can be a variable or its negation, denoted l. The formula of interest, in conjunctive

normal form (CNF), is

f = (x2 x3) (x2 x3) (x1 x2 x4).

(1)

The aim is to fifind assignments to the variables such that f is true under the usual rules

for Boolean operations. This question addresses the use of more general constraint

satisfaction to solve this problem.

(a) Give a general description of a constraint satisfaction problem (CSP).

[3 marks]

(b) Explain how a Boolean satisfifiability problem in CNF form and with n variables

can be converted to a CSP, also having n variables and having a suitable

constraint for each clause. Illustrate your answer using the 4-variable formula f

in (1). [3 marks]

constraints can be converted to binary constraints. Provide a graph illustrating

the problem from (1) after it has been converted to a CSP with only binary

constraints. [4 marks]

(d) Explain, how forward checking works in the context of a general CSP. How does

this benefifit a CSP solver? [3 marks]

(e) Using the CSP equivalent you developed for (1), with only binary constraints,

demonstrate how forward checking works using the sequence of assignments

x1 = F, x2 = F, x4 = T. [5 marks]

(f ) How would you expect the solution obtained when applying forward checking to

be affffected if constraints were allowed to propagate more widely? [2 marks]

3CST1.2021.6.4

Complexity Theory

(a) Defifine the set of Boolean expressions 2CNF and the language 2SAT over them.

[2 marks]

(b) For a Boolean expression in 2CNF, let G() be the directed graph with vertices

the variables of and their negation, and with edges (a, b) if, and only if, there

is a clause (a b) or (b a) in . Note that an edge (a, b) is in G() if, and

only if, so is the edge (b, a).

Prove that a Boolean expression in 2CNF is unsatisfifiable if, and only if, there

is a variable x in such that there are paths from x to x and from x to x in

G(). [Hint: Recall that the proposition (P Q) is equivalently the implication

(P Q).] [12 marks]

use the fact that NL is closed under complementation. [6 marks]

4CST1.2021.6.5

Complexity Theory

(a) For a complexity class C, let co-C = { L | L C } and say that C is closed under

complementation whenever C = co-C.

Argue as to whether the following statements are true, false, or unknown.

(i) All deterministic time complexity classes are closed under complementation.

[3 marks]

(ii) All non-deterministic time complexity classes are closed under

complementation. [3 marks]

(b) For a mapping f : on an alphabet and a language L , defifine

f[L] = { f\ (w) | w L } where f\ (a1 an) = f(a1) f(an).

Prove that L NP implies f[L] NP. [4 marks]

Q: Given natural numbers m and n in N, and bits a

(k)

i,j

and bk in

{0, 1} for 1 k m and 1 i, j n, determine whether the system

of equations P 1i,jn a

(k)

i,j

xi xj = bk (1 k m) with unknowns

x1, . . . , xn has a solution in arithmetic modulo 2.

(i) Prove that Q is in NP. [3 marks]

(ii) By means of a polynomial-time reduction from the problem 3CNF, or

otherwise, prove that Q is NP-hard. [Hint: Note, for instance, that x = y

in the Boolean algebra {0, 1} if, and only if, xx + yy = 1 in arithmetic

modulo 2.] [7 marks]

You may use standard results provided that you state them clearly.

5CST1.2021.6.6

Computation Theory

(a) For each n, e N, let

(n)

denote the partial function Nn* N computed by the

and register R0 to store the result, if any.

Explain why for each m, n N there is a totally defifined register machine

computable function Sm,n : N 1+m N with the property that for all (e, ~x)

(m+n)

(~x, ~y) (1)

where denotes Kleene equivalence: for all z N, the left-hand side is defifined

and equal to z if and only if the right-hand side is defifined and equal to z.

Your explanation should make clear what assumptions you are making about

the relationship between numbers and register machine programs. [10 marks]

(b) Let f : N 1+m+n* N be a register machine computable partial function of 1+m+n

arguments for some m, n N.

(i) Why is the partial function f : N 1+m+n* N satisfying for all (z, ~x, ~y)

N 1+m+n

f(z, ~x, ~y) f(S1+m,n(z, z, ~x), ~x, ~y) (2)

(ii) By considering S1+m,n(e, e, ~x) where e is an index for the partial function

f in part (b)(i), prove that there is a totally-defifined register machine

computable function fifix f : Nm N with the property that for all ~x Nm

and ~y Nn

(n)

fifix

f(~x)(~y) f(fifix f(~x), ~x, ~y) (3)

[7 marks]

6CST1.2021.6.7

Computation Theory

A set A equipped with a binary operation @ : A A A is a combinatory algebra

if there are elements K, S A satisfying for all a, b, c A

@(@(K, a), b) = a

(1)

@(@(@(S, a), b), c) = @(@(a, c), @(b, c)) (2)

(a) Show that there is a binary operation on the set of equivalence classes of closed

-terms for the equivalence relation of -conversion that makes it a combinatory

algebra. [5 marks]

(b) Show that every combinatory algebra A contains an element I satisfying

@(I, a) = a

(3)

for all a A. [Hint: what does (2) tell us when a = b = K?] [2 marks]

given by the grammar

e ::= x | p aq | (ee)

where x is some fifixed symbol not in A and a ranges over the elements of A.

Given e A[x] and a A, let e[x := a] denote the element of A resulting from

interpreting occurrences of x in e by a, interpreting the expressions of the form

p a0 q by a0 and interpreting expressions of the form (ee0 ) using @.

(i) Give the clauses in a defifinition of e[x := a] by recursion on the structure of

e. [2 marks]

(ii) For each e A[x] show how to defifine an element xe A with the property

that

@(xe, a) = e[x := a] (7)

for all a A. [6 marks]

(d) Recall the usual encoding of Booleans in -calculus. Using Part (c)(ii), show

that in any combinatory algebra A there are elements True, False A and a

function If : A A A satisfying

@(If (a, b), True) = a

(11)

@(If (a, b), False) = b

(12)

for all a, b A

[5 marks]

7CST1.2021.6.8

Data Science

(a) Let xt be the number of new COVID infections on date t. We anticipate

approximately exponential growth or decay, xt+1 (1 + )xt , and we would

like to estimate from a dataset (x1, . . . , xT ).

(i) Find the maximum likelihood estimator for for the model

Xt+1 Poisson

One or more processors must be selected for inclusion in a portable device that

handles audio, image, video, telephone calls and simple word processing.

Possible design combinations include:

a single processor;

a pair of basically similar processors but with difffferent coprocessor

and bus structures;

a standard processor and a custom VLIW processor.

Explain whether one of these combinations is clearly the best. [2 marks]

(b) For each of the following processor technologies, justify whether it is applicable

in the device:

(i) Dynamically Scheduled Instruction Dispatch;

(ii) Simultaneous Multi-Threading (SMT);

(iii) SIMD extensions, similar to Intel's MMX;

(iv) Virtual Memory;

(v) Dynamic Clock Frequency/Power Control;

(vi) Snooping Cache.

[3 marks each]

2CST.2006.8.3

2 VLSI Design

A majority gate with three inputs signals logic one on its output if two or more of

its inputs are one, and zero otherwise. A minority gate is its complement.

(a) Give the boolean equation for a minority gate as a sum of products. [2 marks]

(b) Sketch the circuit diagram for a minority gate using NAND gates and inverters.

[3 marks]

as a single stage of CMOS logic. [3 marks]

(d) Calculate the number of transistors required for each implementation.

[2 marks]

(e) Assuming that a conducting p-channel has a resistance twice that of a similarly

sized n-channel, use logical effffort to compare the performance of the two

implementations. [10 marks]

3 Digital Communication II

(a) The Transmission Control Protocol (TCP) employs a transmit window

and cumulative acknowledgement and timeout system, as well as sequence

numbering of packets, to achieve reliable delivery of data.

(i) Outline the procedure for round-trip time estimation and the calculation

of the retransmission timer. [8 marks]

(ii) Explain the function of buffffering at the sender and receiver. [3 marks]

(iii) How do fast retransmit and fast recovery improve performance after

packet loss? [3 marks]

(b) In a wireless network, delay to access the channel due to scheduling of the

media access control protocol, and random packet loss due to interference,

may be non-negligible.

(i) Explain how this can interfere with the round-trip time estimation process

above. [3 marks]

(ii) Explain how this can interfere with the congestion control scheme that

TCP employs. [3 marks]

3 (TURN OVER)CST.2006.8.4

4 Distributed Systems

(a) Describe, with examples, the function of a naming service for a large

scale distributed system. Include defifinitions for "name space" and "naming

domain". [6 marks]

(b) Discuss consistency versus availability for naming data in large-scale systems.

[4 marks]

behalf of users can be resolved effiffifficiently in the presence of failures and heavy

load? [4 marks]

(d) Contrast the assumptions under which DNS was designed originally for the

Internet, with the properties of dynamically formed groups of mobile hosts

using wireless communication (MANETS). How might DNS-like services be

provided for MANETS? [6 marks]

5 Advanced Systems Topics

Modern peer-to-peer (P2P) systems are typically described as structured or

unstructured.

(a) Compare and contrast these two approaches. Include a discussion of the

general topology, membership management and query mechanisms. Use

examples to support your answer. [6 marks]

(b) Which approach is more resilient to churn? Justify your answer. [2 marks]

latencies. Describe how one can add proximity awareness to:

(i) unstructured P2P systems; [1 mark]

(ii) structured P2P systems. [3 marks]

(d) Swarming P2P systems like BitTorrent are designed for effiffifficient (and incentive

compatible) download of large fifiles. However, it is typically not possible to use

the fifile until it has downloaded in its entirety. Sketch the design of a swarming

P2P system which supports streaming video - that is, allows playback of video

to overlap the ongoing download of the remainder of the stream. Comment

on how effiffifficient (in terms of network resources) your system would be in

comparison with a system like BitTorrent. [8 marks]

4CST.2006.8.5

6 Computer Vision

(a) Explain the method of Active Contours. What are they used for, and how do

they work? What underlying trade-offff governs the solutions they generate?

How is that trade-offff controlled? What mathematical methods are deployed

in the computational implementation of Active Contours? [10 marks]

(b) When trying to detect and estimate visual motion in a scene, why is it useful

to relate spatial derivatives to temporal derivatives of the image data? Brieflfly

describe how one motion model works by these principles. [5 marks]

operator. Explain what the Laplacian might be used for, and what is the

signifificance of the sum of all of the taps in the fifilter. [3 marks]

(d) When visual sequences are encoded into an .mpeg video stream, typically

about what percentage of the compression achieved is intra-frame (compression

within individual still frames), and what percentage is inter-frame? Name a

key feature that is extracted and estimated for purposes of prediction and,

therefore, compression. [2 marks]

7 Security

The Needham-Schroeder protocol is defifined as

1. A S : A, B, NA

2. S A : {NA, B, KAB, {KAB, A}KBS }KAS

3. A B : {KAB, A}KBS

4. B A : {NB}KAB

5. A B : {NB 1}KAB

(a) Explain the symbolism, and the purpose of the messages. [5 marks]

(b) Explain the "bug" in the protocol. [5 marks]

Schroeder paper does) that all principals execute the protocol faithfully? If

not, why is it important? [5 marks]

(d) Describe how one modern protocol derived from Needham-Schroeder deals

with the issue. [5 marks]

5 (TURN OVER)CST.2006.8.6

8 Optimising Compilers

(a) Summarise the idea of a basic block and explain why it is useful in intermediate

representations for optimising compilers. [3 marks]

(b) Construct the flflowgraph (in which every node is a basic block consisting of

one or more 3-address instructions) for the C function:

int f(int x, int y)

{

int r = x + 1;

if (y == 0) {

r = r * r;

} else {

y = y - 1;

r = r * y;

}

return r + 1;

}

[4 marks]

have to make to your flflowgraph from part (b) in order for it to be in SSA form.

[3 marks]

(d) Consider a flflowgraph in which every node contains a single 3-address

instruction. Each node whose instruction assigns some value to a variable

is considered a "defifinition" of that variable; we are interested in discovering,

for each node n in the flflowgraph, which defifinitions reach n. A defifinition m is

considered to reach n if the variable to which m assigns a value may still have

that value at entry to n.

(i) Defifine the notion of a defifinition reaching a node in the flflowgraph in terms

of possible execution flflows of control. [2 marks]

(ii) By analogy with live variable or available expression analysis, or

otherwise, design dataflflow equations for computing RD(n), the set of

defifinitions which can reach a node n. [4 marks]

(iii) Sketch an algorithm to compute RD(n), brieflfly commenting on any

initialisation required. [4 marks]

6CST.2006.8.7

9 Artifificial Intelligence II

Consider the following Bayesian network:

The associated probability distributions for the binary random variables A, B, C

and D are Pr(a) = 0.1, Pr(a) = 0.9, Pr(b) = 0.8, Pr(b) = 0.2, and:

(a) Explain why the representation of the joint distribution of A, B, C and D

using the Bayesian network is preferable to a direct tabular representation.

[2 marks]

(b) Use the variable elimination algorithm to compute the probability distribution

of B conditional on the evidence that D = > . [16 marks]

algorithm. [2 marks]

7 (TURN OVER)CST.2006.8.8

10 Digital Signal Processing

(a) Consider a software routine that converts and records the audio samples

received in a digital telephone network call (8 kHz sampling frequency,

8 bit/sample) into a WAV fifile (8 kHz sampling frequency, 16 bit/sample,

uniform quantisation). Your colleague attempted to write a very simple

conversion routine for this task, but the resulting audio is very distorted.

(i) Name two variants of the method used for quantising the amplitude of

audio samples in digital telephone networks and explain one of them.

[4 marks]

(ii) Your colleague's routine right-pads each 8-bit data word from the

telephone network with eight additional least-signifificant zero bits to

obtain 16-bit values. Explain how this distorts the signal by discussing

which frequencies could appear at the output when the incoming

telephone signal consists of a pure 1 kHz sine tone. [4 marks]

(b) A real-valued discrete random sequence {xi} is fed into a linear time-invariant

fifilter with impulse response h0 = 1, h3 = 1, and hi = 0 for all other i. We

observe for the resulting output sequence {yi} the expected value

E(yi+k xi) =

0 otherwise

What is the value of the autocorrelation sequence {xx(k)}? [4 marks]

(i) How is it defifined and why is it used? [4 marks]

(ii) Is the conversion from 3 8-bit RGB to 3 8-bit Y CrCb coordinates

fully reversible? Why? [4 marks]

8CST.2006.8.9

11 Computer Systems Modelling

(a) Defifine the M/M/1 queueing model and derive the steady-state distribution

for the number of customers present when the traffiffiffic intensity is less than one.

[5 marks]

(b) For the M/M/1 model in steady-state, derive the mean number of customers

present and the mean time spent by a customer in the system. What is the

utilisation of the server? [5 marks]

the steady-state distribution for the number of customers present. For what

values of the traffiffiffic intensity does your steady-state distribution exist? What

is the utilisation of the server and explain how this compares to the M/M/1

queueing model. [5 marks]

(d) Give an example of the use of the M/M/m/m loss model. Derive Erlang's

formula for the steady-state probability that an arriving customer fifinds all m

servers occupied. [5 marks]

9 (TURN OVER)CST.2006.8.10

12 Numerical Analysis II

(a) In Peano's theorem, if a quadrature rule integrates polynomials of degree N

exactly over an interval [a, b], then the error in integrating f CN+1[a, b] is

expressed as

E(f) = Z ab

f(N+1)(t)K(t) dt

where

K(t) =

x[(x t)N

+ ].

Explain the notation E(f), Ex, (x t)N

+ . [4 marks]

(b) Assuming x [a, b], and writing Taylor's theorem in the form

f(x) = PN (x a) +

Z ax

f(N+1)(t)(x t)N dt

where PN is a polynomial of degree N, prove Peano's theorem, explaining each

step clearly. [8 marks]

(d) If K(t) does not change sign in [a, b] then

E(f) =

f(N+1)()

(N + 1)!

E(xN+1)

for some (a, b). Use this result to simplify

E(f) = Z 11

f(x) dx f(1) f(1).

[7 marks]

10CST.2006.8.11

13 Bioinformatics

(a) Why do we use dynamic programming algorithms for pairwise sequence

alignment problems but not for multiple pairwise alignment? [5 marks]

(b) Compare the use of the affiffiffine gap penalty with the constant gap penalty.

[3 marks]

2-parameter models of DNA evolution. [5 marks]

(d) Describe the UPGMA algorithm. [4 marks]

(e) What does the ultrametric property of a tree tell us about the evolutionary

process? [3 marks]

11 (TURN OVER)CST.2006.8.12

14 Denotational Semantics

Let D be a domain with bottom element . Let h, k : D D be continuous

functions with h strict (so h() = ). Let B = {true, false}. Defifine the conditional

function

if : B D D D

by if (b, d, d0 ) = d if b = true, d0 if b = false, and otherwise. Let p : D B be a

continuous function.

The function f is the least continuous function from D D to D such that

x D. f(x, y) = if (p(x), y, h(f(k(x), y))) .

(a) State the principle of fifixed-point induction. What does it mean for a property

to be chain closed? [4 marks]

(b) Assume that the property

Q(g) def x, y D. h(g(x, y)) = g(x, h(y)) ,

where g is a continuous function from D D to D, is chain closed. Prove Q(f)

by fifixed-point induction. [7 marks]

closed subset of E. Show that the inverse image g1Y is a chain-closed subset

of D. [4 marks]

(d) Exhibit cpos D, E, F and chain-closed subsets R D E and S E F

such that their relational composition S R D F is not chain closed. (No

proof is required.) [5 marks]

12CST.2006.8.13

15 Specifification and Verifification I

If C is a command that contains one or more occurrences of a command BREAK, then

LOOP (C) is a command that repeatedly executes C until a BREAK is executed.

Executing BREAK immediately terminates the execution of LOOP (C).

How might ideas from Floyd-Hoare Logic be used to verify programs that use the

LOOP/BREAK construct, such as the following program that sets the variable RES to

the factorial of the initial value of the variable X (if X > 0)?

RES := 1;

LOOP (IF X=1 THEN BREAK ELSE RES := RESX; X := X-1)

You may place restrictions that you consider reasonable on the form of C, but these

should be discussed and motivated.

[20 marks]

13 (TURN OVER)CST.2006.8.14

16 Information Theory and Coding

(a) Suppose we know the conditional entropy H(X|Y ) for two slightly correlated

discrete random variables X and Y . We wish to guess the value of X, from

knowledge of Y . There are N possible values of X. Give a lower bound

estimate for the probability of error, when guessing X from knowledge of Y .

What is the name of this relationship? [4 marks]

(b) In an error-correcting (7/4) Hamming code, under what circumstance is there

still a residual error rate? (In other words, what event causes this error

correction scheme to fail?) [2 marks]

power level of a white noise source is 2 and its excursions are zero-centred so

its mean value is = 0, give an expression describing the probability density

function p(x) for excursions x of this noise around its mean, in terms of .

What is the special relationship between the entropy of a white noise source,

and its power level 2 ? [4 marks]

(d) Explain the phenomenon of aliasing when a continuous signal whose total

bandwidth extends to W is sampled at a rate of fs < 2W. If it is not

possible to increase the sampling rate fs, what can be done to the signal

before sampling it that would prevent aliasing? [5 marks]

(e) Prove that the sinc function,

sinc(x) =

sin(x)

is invariant under convolution with itself: in other words that the convolution

of a sinc function with itself is just another sinc function. You might fifind it

useful to recall that the Fourier transform of a sinc function is the rectangular

pulse function:

(a) 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. [5 marks]

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

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]

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]

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

I = Iaka +X

Iikd(Li N) +X

Iiks(Ri V)n

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]

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

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]

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]

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

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]

[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

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

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]

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

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]

CSC 2310 Homework HW 6 and Lab program will ask the user to enter another amount. This continues until an amount greater than 50 is entered Dr. Xiaolin Hu Set the balance of the savings account object by calling the HW6 & Lab: setBalance() method Ask the user to deposit an amount. Deposit that amount and display the balance of the account. Objective Lab: To learn basic inheritance using simple super class and sub class HW: To learn inheritance using graphics Part l:( Lab Programming) Due bv: End of Lab Turn in the SavingsAcount.java and testAccount.java Below is an illustration of how the program works: Welcome. Which account do you want to create? . You are given the class Account with predefined methods for bank account. It already has methods to display the balance and methods to withdraw and deposit some amount 2. Savings 1. Normal Enter choice: 2 Enter initial balance: () $50) -20 Balance should be greater than 50 Enter initial balance: () $50) -70 Balance 70.0 Enter amount to deposit: 100 Balance - 180.0. You need to create subclass called SavingsAccount. Your SavingsAccount class should override the deposit method, so that when a user deposits an amount in the savings account, the bank will add additional 10% to the amount. You are given a testAccount class which asks the user what account it want to create. In the testAccount class, add java code to do the following things in a sequential order: create new savings account object (for choice 2) Part l!: HW6. ask the user to enter an initial balance which should be Deadlines as posted in d2l file Deadlines greater than 50. If the entered amount is less than 50, the

kindly answer all the questions