answer the question clearly You are building a flight-control system for which a convincing safety case must

No answer yet for this question. Ask a Tutor

Question:

answer the question clearly

You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case development and assurance documentation to a separate team, or distribute them among your developers? Justify your answer briefly. [4 marks] (c) Describe two particular features of ML and two (different) features of Java that might be expected to help the process of designing, implementing, debugging or maintaining high quality programs in a cost effective manner. Explain whether the features you have noted are ones that come into play for all users or if they are capabilities that a user can choose to use or to ignore. [4 marks] (d) Draw a state diagram for a deterministic finite automaton that accepts w {a, b} if, and only if, w either begins with a and is of odd length or begins with b and is of even length. [4 marks] (e) A (ROM) Read Only Memory has 8 address inputs and 8 data outputs. Estimate how many two-input gates would be required, on average, to perform the function of the ROM.An inspector selects a newly-manufactured component at random and does not know which machine fabricated it. What is the probability that it is faulty? [5 marks] (b) A faulty component is drawn at random from a pile of rejects. Use Bayes's Theorem to determine the probabilities that the faulty component was fabricated by machines A, B and C respectively. Express your answers as fractions. [9 marks] (c) Six faulty components are drawn at random from a pile of rejects. What is the probability that two were fabricated by machine A, two by machine B, and two by machine C? Your answer should be written as an expression which may incorporate the values determined in part (b). [6 m(a) Prove that if L is a regular language, its complement is also regular. [6 marks] (b) For each of the following languages over the alphabet {a, b}, state whether or not it is regular and justify your answer. (i) {w | w is not a palindrome} (ii) {a k | k is a multiple of 3} (iii) {a k | k is prime} [14 mark(a) Prove that if L is a regular language, its complement is also regular. [6 marks] (b) For each of the following languages over the alphabet {a, b}, state whether or not it is regular and justify your answer. (i) {w | w is not a palindrome} (ii) {a k | k is a multiple of 3} (iii) {a k | k is prime} [14 markA new scanner for small objects consists of a transmitting array of 512512 elements and a receiving array of similar size. Each array is 4 cm on a side and the two arrays are placed 4 cm apart so that a total volume of 43 cubic centimetres can be scanned. Each transmitting element has two inputs that may be directly connected to digital logic and which are internally ANDed by the element. The scanner operates in still image mode by delivering a complex pattern of microsecond resolution pulses to the transmitting array over the course of one millisecond. The more pulses that can be delivered, the better quality the image. The complete pattern of pulses is determined in advance by software. The software will be aware of any constraints you may implement in the hardware that generates the pulses. Please execute the following steps in the design of the transmitter array: (a) Design and sketch out the inter-wiring between the control electronics and the transmit array elemen circuits) to use, taking into account a 100 pin limit for each chip. [8 marks] (b) Decide how much RAM is needed on each chip to store the pattern and explain the data representation in RAM you have selected. Justify your decision. [4 marks] (c) Show how the transmitting and receiving arrays may both be wired into the address space of a controlling microprocessor. [4 marks] (d) Sketch out the internal architecture of each transmitter chip, showing the major blocks

(a) The professional standards of the British Computer Society's Code of Conduct are organised into four groups of standards, each including at least three specific standards. State what is the general concern of three of the main groups and give an example of one of the standards of conduct included in each group you mention. [6 marks] (b) Suggest two arguments in favour of computer cracking and how one would reply to each argument. [4 marks] (c) How can institutional measures serve to control computer cracking? [2 marks] (d) (i) How can privacy exist when for virtually every fact about us there is at least one person who knows that fact? [1 mark] (ii) State two principles of the 1998 Data Protection Act and how each serves to protect privacy. [4 marks] (e) Name three types of law that protect intellectual property. [3 marksA manufacturing plant consists of three machines, A, B and C, which fabricate electronic components. Machine A is responsible for 20% of the components, machine B is responsible for 30%, and machine C is responsible for 50%. The manufactured components are supposed to be identical but it is known that 3 in every 1000 made by machine A are faulty, 1 in every 125 made by machine B is faulty, and 1 in every 250 made by machine C is faulty. (a) An inspector selects a newly-manufactured component at random and does not know which machine fabricated it. What is the probability that it is faulty? [5 marks] (b) A faulty component is drawn at random from a pile of rejects. Use Bayes's Theorem to determine the probabilities that the faulty component was fabricated by machines A, B and C respectively. Express your answers as fractions. [9 marks] (c) Six faulty components are drawn at random from a pile of rejects. What is the probability that two were fabricated by machine A, two by machine B, and two by machine C? Your answer should be written as an expression which may incorporate the values determined in part (b). [6 marks]A computer room is cooled by two groups of fans. Each group contains three fans. All six fans are identical and, when they fail, they fail equiprobably and independently. Two or more fans never fail simultaneously. There is deliberate over-provision of fans so that there is adequate cooling as long as at least one fan in each group is working. The local maintenance policy is to do nothing until all three fans in one or other of the groups have failed. When that happens, all six fans in the room are replaced including those that have not failed. (a) When replacement occurs, what is the minimum number of working fans that could be replaced and what is the maximum number that could be replaced? Justify your answers. [2 marks] (b) Let X be a random variable whose value r is the number of failed fans when replacement occurs. Clearly 0 6 r 6 6 and, for some values of r, the probability P(X = r) = 0. By constructing an event tree or otherwise, tabulate P(X = r) for r = 0, 1, 2 . . . 6. All non-zero probabilities should be expressed as fractions. [12 marks] (c) Determine the expectation and variance E(X) and V(X). [6 marks

Assume that jobs are no longer CPU-bound but also perform blocking and non-blocking IO. Discuss how this can affect the effectiveness and fairness of the SRTF scheduler. [4 marks]

Consider the access rights of user alice regarding the following files and directories on a Linux file system: $ id uid=1000(alice) gid=1000(alice) groups=505(safety) $ ls -ld foo foo/* foo// drwxrwxrwx 4 root root 4096 Apr 20 14:40 foo -rw-rw-r-- 1 root root 100 Apr 20 14:40 foo/bar -rw-rw-r-- 1 alice alice 100ir2 -rw-rw---- 1 root root 100 Apr 20 14:40 foo/dir2/flop -rw-rw-r-- 1 alice alice 100 Apr 20 14:40 foo/dir2/wibble -rw-rw---- 1 root safety 100 Apr 20 14:40 foo/dir2/wobble (i) For each of the eight files and directories under foo/, list which of the fo: read (R), delete (D), rename (N). Your answer should be foo/qux where the letters RDN indicate that the corresponding operation is allowed, and replacing any of these letters with - indicates that it is denied. [8 marks] (ii) Which sequence of shell commands can user alice use to take ownership of file foo/bar, without affecting its content, such that it appears afterwards in the above directory listing as in -rw-rw-r-- 1 alice alice 100 Apr 20 14:40 foo/bar [2 marks] (iii) Name two operations on the metadata of file foo/bar that user alice can execute only after taking ownership. [2 marks] (b) List four mechanisms that a web server can use to maintain authentication session state across a web browser's HTTP requests that form part of the same login session, along with one disadvantage associated with each.

Most modern computers include a translation lookaside buffer (TLB) to speed up address translation. (a) Describe with the aid of a diagram the basic operation of a TLB. [2 marks] (b) Some TLBs support process tags (sometimes called address space numbers). Explain how process tags could be used by an operating system, and what benefits might be expected. [2 marks] (c) Some TLBs support superpages of one or more sizes. (i) Explain how superpages could be used to reduce the TLB footprint for operating system kernels. [2 marks] (ii) Explain how superpages could be used to reduce the TLB footprint for processes. What additional considerations need to be taken into account in this case? How well do you think your scheme would work in practice? [4 marks] (d) Compare and contrast the way in which demand paging is performed in Unix and VMS. [10 marks]

(a) Write immutable Java class Complex that represents a complex number with integer real and imaginary components. [Note: Your class should contain only methods that are essential for its use. Do not incorporate any mathematical operations in the class.] [4 marks] (b) Without using Generics, adapt the class to support the use of arbitrary types to store the real and imaginary components. Give three disadvantages of this approach and comment on the immutability of the new class. [7 marks] (c) Rewrite your class from part (b) using Generics. Discuss the extent to which this new version addresses the problems identified in part (b). [7 marks] (d) Explain carefully why the following code cannot be used to print out an object of type LinkedList>. You may assume the existence of a working print method within each Complex object. void printAll(LinkedList> list) { for (Complex c : list) c.print();

Cons cumulative reward, a policy, and an optimal policy for a problem of this kind. [5 marks] (b) Give a detailed derivation of the Q-learning algorithm. [5 marks] (c) In the reinforcement learning problem shown in the diagram, states are positions on a grid and actions are down and right. The initial state is s1. The only way an agent can receive a (non-zero) reward is by moving into one of two special positions, one of which has reward 50 and the other 150. s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s11 s12 150 50 A possible sequence of actions (sequence 1) is shown by solid arrows, and another (sequence 2) by dashed arrows. Assume that all Q values are initialised at 0. Explain how the Q values are modified by the Q-learning algorithm if sequence 1 is used once, followed by two uses of sequence 2, and then one final use of sequence 1. [10 marks]

The following code has been written by a novice Java programmer. You are not required either to understand or to debug the details of how this code draws some particular pattern (a "Dragon"). The programmer finds that the Java compiler complains. Identify any errors and comment on any issues that (even if not strictly invalid Java) are liable to cause problems. You are not required to provide corrections.pper class Dragon extends JApplet throws Exception { import javax.swing.*; public paint(Graphics g) { this.g = g; drawDragtle: drawDragon Function to draw a dragon curve between too points (x1,y1) and (x2,y2) with depth 'depth'. */ void protected drawDargon(int depth, int x1,int y1,int x2,int y2) { if (x1 < 0 | x2 < 0) if (y1 < 0) raise new Exception("X & Y < 0"); else assert("Ok so far"); if (depth = 0) // bottom of recursion { (y2+y1-x2+x1)/2; ... and Y coord. */ printf("DEBUG: x= drawDragon(depth-1,mpx,mpy,x1,y1); drawDragon(depth+1,mpx,mpy,x2,y2); } static secret int DRAWDEPTH=15, Graphics g;

(a) Show how you would create Java array of 1000 integer values. [1 mark] (b) The values in an array could be used to represent digits in the decimal representation of a number. For example, the number 1 7 has decimal representation 0.142857 . . . and that could be stored in an array whose elements started {1, 4, 2, . . .}. For a number stored that way write code that multiplies the number by a given integer, returning the whole number part of the result and leaving the array updated to hold the fractional part of the product. [5 marks] (c) To convert a fraction to a representation base 16 (i.e. hexadecimal) you can multiply it by 16, and the resulting integer part is the first digit of the base-16 representation. Multiplying the fraction left over by 16 gets the second digit and so on. Write method that accepts an array of digits (base 10) and creates and returns a new array representing the same fraction but now base 16. Your code should work for any length input array, not just one of length 1000, and you may make the output array have the same length as your input array. [6 marks] (d) Suppose the input to your method in part (c) was of length 1000 and started off with the decimal digits of 1 7 in it. Although the initial digits in the output array are the correct hexadecimal representation of 1 7 the last few end up looking odd. Explain. [3 marks] (e) One way to ensure that numerical results are correct is to use interval arithmetic. A value is represented as a pair of arrays, one representing a number less than (or equal to) the true value and one a value greater than it. So if using 6 decimal places the number 1 7 would be held as a pair { If the two final digits differ by at most 1 then the smaller of them can be viewed as fully accurate. Using this idea, write code that accepts a fraction in decimal form and returns a vector denoting the same value in another base n (now no longer necessarily 16) such that all the digits in the result vector are correct. Clarity in your code is to be preferred to performance, but if you are aware of particular ways in which the code you present is particularly inefficient, you should note and explain them

For each of the following pairs of concepts that are used in Java explain similarities and differences and discuss when you would use one rather than the other. If there are important syntactic differences, method names, degrees of generalisation possible or the like, then any code fragments you give in illustration should be as short as possible to make the desired point. (a) JApplet and simple Java applications [4 marks] (b) Vector and arrays of strings (String []) [3 marks] (c) class, abstract class and interface

(a) In order to remove the overhead of a function call, a programmer decides to replace all calls to a function f with the macro F, where f and F are defined as follows: int f(int x) { return x+x;} #define F(X) (X)+(X) (i) Give two valid C expressions involving f which produce different results when F is substituted for f. Justify your answer. [4 marks] (ii) State the C language feature which can be used to correctly remove the overhead of a function call. [1 mark] (b) Consider the following: static struct link { int v; struct link *next; } *head=0; void convert(int a[], int len); Write function definition for convert which updates head to point to a linked-list containing the elements of a in the same order. You may assume len contains the number of elements in a. [5 marks] (c) Consider the following C++ declaration: template int SumSquares(); (i) Using function specialisation, provide an implementation of SumSquares so that, given an integer N, SumSquares() returns: X N i=1 i 2 [5 marks] (ii) Compare and contrast the functionality of the C preprocessor and the C++ template system. Explain why it is not possible to write a C preprocessor macro to implement SumSquares. [5 marks]

(a) An author writes: Most successful language design efforts share three important characteristics . . . 1. Motivating Application: The language was designed so that a specific kind of program could be written more easily. 2. Abstract Machine: There is a simple and unambiguous program execution model. 3. Theoretical Foundations: Theoretical understanding was the basis for including certain capabilities and omitting others. Briefly discuss the merits and/or shortcomings of one of the above three statements of your choice, giving examples and/or counterexamples from procedural, applicative, logical, and/or object-oriented programming languages. [6 marks] (b) For two programming languages of your choice amongst FORTRAN, Algol, Pascal and C, briefly discuss and evaluate their typing disciplines. Further compare the advantages and disadvantages that their designs impose on the programmer. [5 marks] (c) Consider the following two program fragments. ( defvar x 1 ) ( defun g(z) (+ x z) ) ( defun f(y) (+ (g 1) ( let ( ( x (+ y 3) ) ) ( g(+ y x) ) ) ) ) ( f 2 ) val x = 1 ; fun g(z) = x + z ; fun f(y) = g(1) + let val x = y + 3 in g(y+x) end ; f(2) ; What are their respective output values when run in their corresponding interpreters? Justify your answer, explaining it in a conceptual manner. [4 marks] (d) Outline the key features that a language must have to be called object-oriented. Further, briefly discuss to what extent one programming language of your choice amongst Simula, Smalltalk, C++, and Java has them. [5 marks

(a) Many computer scientists believe that languages with strong compile-time type checking are better than those that are typeless, dynamically typed, or are weakly type checked. Discuss the reasons for this view. [7 marks] (b) If strictly-checked data types are seen as good, discuss whether augmenting a language with many more primitive data types is better. Consider, in particular, the possibility of incorporating into a language such as Java many new numerical types such as packed decimal of various precisions, scaled arithmetic, and new types to hold values representing distance, mass and time. How would these additions affect the readability and reliability of programs? [7 marks] (c) Some languages allow different modes of calling of function arguments, such as call by value, call by reference and call by name. Discuss the advantages and disadvantages of incorporating the argument calling modes into the data types of functions. [6 marks]

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

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, hurrican

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.

(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