software projects failed. In the run-up to Y2K, most of the world's large companies claimed that fixing

No answer yet for this question. Ask a Tutor

Question:

software projects failed. In the run-up to Y2K, most of the world's large companies
claimed that fixing the Millennium Bug was a large project whose success was
critical to their survival. One would therefore expect many large companies to
have failed, but none did. Who was mistaken? Justify your answer.s?One means of improving system reliability is to have three or more replicated
systems and act on their majority output. Give two examples of failure that can
be stopped by the mechanism, and two which cannot. At least one of each type
should be illustrated by an actual case history or application. [12 marks]
An engineer attempts to improve the reliability of such a system further by
multiversion programming - by having three separate systems coded by different
teams and possibly in different languages. Discuss what might still go wrong.

What are the tools traditionally used to manage each type of complexity?
[6 marks]
For each type, describe briefly one case history in which a serious failure was caused.
[10 marks]

What is the maximum throughput of the system measured in transactions per second? [6 marks] Describe two balanced systems which bound the throughput of the system. What is the maximum throughput of these systems? [7 marks] Recall that the throughput of a balanced system with K devices, N customers and service demand D per device is X(N) = N (N + K − 1) × 1 D How many transactions do you expect to be in the system with a throughput of 7 transactions per second? [7 marks] 4 CST.2000.9.5 8 Neural Computing Give evidence supporting the view that the main computational load that has shaped the evolution of the human brain is "social computation", with sexual success being the ultimate measure of the value of an algorithm or neural design feature. Say what implications this has for: • The cognitive skills and perceptual faculties that have been selected for in brain evolution, as contrasted with the goals which are the traditional focus of AI. • The design of face recognition algorithms, which aim to interpret facial expression, gesture, and intent, as well as gender and identity. • The construction of the theory that other persons have minds, too. • Models of action, planning, and interaction between self and others. [8 marks] Comment on whether this "social computation" view of human brain evolution implies that brain science is less relevant to the goals of computer science than is usually thought. [2 marks] Answer any five of the following seven short questions: (a) Roughly what is the total number of neurones in the human brain? (b) Roughly what is the total number of synapses in the human brain? How does this compare with the total number of stars in our galaxy, and with the total number of galaxies in the known universe? (c) Why is nerve impulse propagation described as "saltatory", and what purposes are achieved by this method of signalling? (d) What is the approximate speed of nerve impulse propagation in warm-blooded animals, in metres/sec? (e) Why is "white matter" white, what cells are responsible for this, and what purpose do they serve? (f ) Name the three principal ions involved in nerve membrane current flows, and identify which two of them transit through voltage-dependent conductances. (g) What causes the refractory deadtime of about 1 msec after each nerve impulse? [2 marks each] 5 [TURN OVER CST.2000.9.6 9 Artificial Intelligence Consider the following story of the play Macbeth, by William Shakespeare: The characters are Macbeth, Lady-Macbeth, Duncan and Macduff. Macbeth is an evil noble. Lady-Macbeth is a greedy ambitious woman. Duncan is a king. Macduff is a loyal noble. Macbeth is weak because Macbeth married Lady-Macbeth and because Lady-Macbeth is greedy. Lady-Macbeth persuades Macbeth to want to be king. Macbeth murders Duncan using a knife because Macbeth wants to be king and because Macbeth is evil. Lady-Macbeth kills Lady-Macbeth. Macduff is angry because Macbeth murdered Duncan and because Macduff is loyal to Duncan. Macduff kills Macbeth. Construct a semantic network representing the above story. [8 marks] Show the chain of reasoning leading to Macduff killing Macbeth. [5 marks] It is possible to change the story so that Lady-Macbeth is unable to persuade Macbeth to want to be king. Augment the story to provide a reason for Lady-Macbeth's inability to persuade Macbeth to want to be king. Update the semantic network to reflect the new situation. [7 marks] 10 Numerical Analysis II Explain the terms (a) positive definite, (b) positive semi-definite for a symmetric matrix A. If a square matrix B is non-singular, which of the properties (a) or (b) most accurately describes BT B? What if B is singular? [4 marks] State Schwarz's inequality for the product AB. In what way is this modified for the product Ax, where x is a vector? What are the singular values of A, and how are they related to the l2 norm of A? In the singular value decomposition A = UWVT , what is W? [5 marks] Let ˆx be an approximate solution of Ax = b, and write r = b − Aˆx, e = x − ˆx. Find an expression which is an upper bound for the relative error ||e||/||x|| in terms of computable quantities. Explain how this result may be interpreted if the l2 norm is used. [8 marks] Suppose A is a 5 × 5 matrix and Ax = b is to be solved by singular value decomposition. If machine epsilon ' 10−15 and the singular values of A are 1, 10−6 , 10−10 , 10−17 , 0 write down the generalised inverse W+ that you would use. [3 marks] 6 CST.2000.9.7 11 Information Theory and Coding (a) Prove that the information measure is additive: that the information gained from observing the combination of N independent events, whose probabilities are pi for i = 1 . . . N, is the sum of the information gained from observing each one of these events separately and in any order. [4 marks] (b) What is the shortest possible code length, in bits per average symbol, that could be achieved for a six-letter alphabet whose symbols have the following probability distribution? { 1 2 , 1 4 , 1 8 , 1 16 , 1 32 , 1 32 } [3 marks] (c) Suppose that ravens are black with probability 0.6, that they are male with probability 0.5 and female with probability 0.5, but that male ravens are 3 times more likely to be black than are female ravens. If you see a non-black raven, what is the probability that it is male? [4 marks] How many bits worth of information are contained in a report that a non-black raven is male? [1 mark] Rank-order for this problem, from greatest to least, the following uncertainties: (i) uncertainty about colour (ii) uncertainty about gender (iii) uncertainty about colour, given only that a raven is male (iv) uncertainty about gender, given only that a raven is non-black [3 marks] (d) If a continuous signal f(t) is modulated by multiplying it with a complex exponential wave exp(iωt) whose frequency is ω, what happens to the Fourier spectrum of the signal? Name a very important practical application of this principle, and explain why modulation is a useful operation. How can the original Fourier spectrum later be recovered? [3 marks] (e) Which part of the 2D Fourier Transform of an image, the amplitude spectrum or the phase spectrum, is indispensable in order for the image to be intelligible? Describe a demonstration that proves this. [2 marks] 7 [TURN OVER CST.2000.9.8 12 Computer Vision Define the Correspondence Problem, detailing the different forms that it takes in stereo vision and in motion vision. (a) In each case, explain why the computation is necessary. [5 marks] (b) What are the roles of space and time in the two cases, and what symmetries exist between the stereo vision and the motion vision versions of the Correspondence Problem? [5 marks] (c) How does the complexity of the computation depend on the number of underlying features that constitute the data? [5 marks] (d) Briefly describe at least one general approach to an e[4 marks] (b) (i) State the incrementing rule for the Euler method of numerical integration, in terms of: • f(xn), the estimate of the solution f(x) at the current point xn • f(xn+1), the new estimate of f(x) for the next point xn+1 • for the derivative of the desired solution f(x) at the current point xn [4 marks] (ii) What might happen to your solution if the stepsize h is too large? [2 marks] (iii) What might happen to your solution if you make the stepsize h too small? [2 marks] (iv) What is the primary advantage of the Runge-Kutta method over the Euler method for numerical integration of ODEs? [2 marks] (v) Under what conditions might you wish to make the stepsize h adaptive rather than fixed? How should you adapt it? [2 marks] 5 [TURN OVER CST.2000.3.6 9 Computation Theory One of the most important contributions of the theory of computation has been to establish that the halting problem is not decidable. Give a clear statement of this result (you are not asked to prove it). [5 marks] Define a configuration of a 2-register machine at a particular point during the execution of some program. [3 marks] By considering the total number of configurations or otherwise, show that it is not possible to compute an upper bound for the contents of the two registers during halting computations as a function of the program code and the initial contents of the two registers.

1 Concurrent Systems (a) A software module controls a car park of known capacity. Calls to the module's procedures enter () and exit() are triggered when cars enter and leave via the barriers. Give pseudocode for the enter and exit procedures (i) if the module is a monitor [8 marks] (ii) if the programming language in which the module is written provides only semaphores [4 marks] (b) Outline the implementation of (i) semaphores [4 marks] (ii) monitors [4 marks] 1 [TURN OVER CST.2000.3.2 2 Further Java Write brief notes on the facilities for lightweight concurrency in Java. You should cover the following topics, using code fragments to illustrate your answer: (a) creating a thread (b) mutual exclusion (c) signalling (d) asynchronous interruption (e) managing priority [4 marks each] 3 Compiler Construction With reference to a strictly-typed block-structured programming language, write brief notes on the following topics: (a) the allocation and recovery of records stored in a heap (b) the implementation of variables of union type (c) the allocation of arrays with non-manifest bounds (d) the implementation of labels and GOTO commands [5 marks each] 2 CST.2000.3.3 4 Introduction to Security Consider the following two separation-of-duty policies: (a) A transaction needs approval from two people, one in group A and one in group B. (b) A transaction needs approval from two distinct users of the system. Which of these is harder to implement using the standard Unix access control mechanisms, and why? [10 marks] Sketch an implementation of the easier policy using Unix mechanisms. [5 marks] Describe at least two alternative mechanisms that might be used to implement the other policy. [5 marks] 5 Data Structures and Algorithms Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted. [6 marks] Describe another algorithm that will find the same element, but with a guaranteed worst case time of O(n). [7 marks] Give a rough estimate of the number of comparisons each of your methods would perform when k = 50, operating on a set of 100 random 32-bit integers. [7 marks] 6 Computer Design Gordon Moore's law originally applied to memory size (in bits), but also applies to processor speed (in MIPS). However, main memory access latency does not follow Moore's law. (a) What is Moore's law? [4 marks] (b) Why doesn't main memory latency decrease in proportion to processor cycle time? [6 marks] (c) What mechanisms are used to hide poor main memory access times and why do these mechanisms work? [10 marks] 3 [TURN OVER CST.2000.3.4 7 Operating System Functions Why are the scheduling algorithms used in general-purpose operating systems such as Unix and Windows NT not suitable for real-time systems? [4 marks] Rate monotonic (RM) and earliest deadline first (EDF) are two popular scheduling algorithms for real-time systems. Describe these algorithms, illustrating your answer by showing how each of them would schedule the following task set. Task Requires Exactly Every A 2ms 10ms B 1ms 4ms C 1ms 5ms You may assume that context switches are instantaneous. [8 marks] Exhibit a task set which is schedulable under EDF but not under RM. You should demonstrate that this is the case, and explain why. [Hint: consider the relationship between task periods.] [8 marks] 4 CST.2000.3.5 8 Continuous Mathematics (a) When numerically computing the solution to an ordinary differential equation (ODE) that involves higher-than first-order derivatives: (i) What is to be done about the higher-than first-order terms, and how can this be accomplished? [4 marks] (ii) Illustrate this step for the following ODE, in which functions r(x) and q(x) are known and we seek to compute the solution y(x): d 2 y dx2 + q(x) dy dx = r(x) [4 marks] (b) (i) State the incrementing rule for the Euler method of numerical integration, in terms of: • f(xn), the estimate of the solution f(x) at the current point xn • f(xn+1), the new estimate of f(x) for the next point xn+1 • the integration stepsize h, which is the interval (xn+1 − xn) • f 0 (xn), the expression given by the ODE for the derivative of the desired solution f(x) at the current point xn [4 marks] (ii) What might happen to your solution if the stepsize h is too large? [2 marks] (iii) What might happen to your solution if you make the stepsize h too small? [2 marks] (iv) What is the primary advantage of the Runge-Kutta method over the Euler method for numerical integration of ODEs? [2 marks] (v) Under what conditions might you wish to make the stepsize h adaptive rather than fixed? How should you adapt it? [2 marks] 5 [TURN OVER CST.2000.3.6 9 Computation Theory One of the most important contributions of the theory of computation has been to establish that the halting problem is not decidable. Give a clear statement of this result (you are not asked to prove it). [5 marks] Define a configuration of a 2-register machine at a particular point during the execution of some program. [3 marks] By considering the total number of configurations or otherwise, show that it is not possible to compute an upper bound for the contents of the two registers during halting computations as a function of the program code and the initial contents of the two registers.

1 Distributed Systems
In a distributed electronic conference application each participant has a replica of
a shared whiteboard. Only one user at a time may write to the whiteboard, after
which the user's update is propagated to all conference members. A dedicated
process manages each whiteboard replica. Define and discuss a protocol that the
replica managers could use to achieve this mutual exclusion. [10 marks]
A service database is replicated within a widely distributed system to achieve high
availability and low access latency. Within a hierarchy of replicas a set of top-level
primary servers maintain strong consistency of their replicas. Describe how this
strong consistency could be achieved. [10 marks]
2 VLSI Design
Sketch a transistor-level design and give a brief description of the method of
operation for each of the following memory cells:
(a) a dual-ported, static memory cell [5 marks]
(b) a dynamic memory cell using standard MOS logic [5 marks]
(c) a dynamic memory cell for dense memory [5 marks]
Explain the comparative merits of the three designs and explain where they might
be used. [5 marks]
1 [TURN OVER
CST.2000.9.2
3 Digital Communication II
Consider the IntServ (RSVP based) and DiffServ QoS Architectures.
(a) Compare the nature of "guarantee" that is made in each and the time scale
on which these are altered. [6 marks]
(b) Compare where state resides in each case, and how much state there is.
[3 marks]
(c) Compare the number of control interactions that a core router in each
architecture would engage in. [3 marks]
(d) Compare the resource efficiency of each scheme in terms of link bandwidth.
[Hint: consider single-ended Service-Level Agreements (SLAs).] [3 marks]
(e) Describe the architecture of a core router in a DiffServ environment, recalling
that each packet will have a Type of Service field describing its designated
Per Hop Behaviour. [5 marks]
4 Advanced Graphics and HCI
(a) Show how you would calculate the first intersection point between an arbitrary
ray and a finite length open cylinder of unit radius aligned along the x-axis.
[Note: an open cylinder is one which has no end caps.]
Having calculated the intersection point, how would you calculate the normal
vector? [7 marks]
(b) A non-rational B-spline has knot vector [1, 2, 4, 7, 8, 10, 12]. Derive the first of
the third order (second degree) basis functions, N1,3(t), and graph it.
If this knot vector were used to draw a third order B-spline, how many control
points would be required? [7 marks]
(c) Describe how an object built using constructive solid geometry (CSG) can be
represented using a binary tree. Given the intersection points of a ray with
each primitive in the tree, show how to calculate the first intersection point of
the ray with the entire CSG object. [6 marks]
2
CST.2000.9.3
5 Business Studies
What is meant by a critical path? [5 marks]
The village bakery has asked you to advise them about setting up a web site,
including a trading function.
Draw up a project plan, illustrated by a GANTT chart, and indicate the critical
path. [5 marks]
Make an estimate of the costs involved, and estimate how much working capital
you would need. [5 marks]
What other advice would you give them? [5 marks]
6 Security
The owner of a banking system which previously used manually distributed shared
keys to compute MACs on transactions decides to use public key cryptography to
distribute MAC keys in future. The proposed protocol is
A → B : { {TA, KAB}K−1
A KB
}
Explain the symbolism used in this description. [2 marks]
What is wrong with this protocol? [6 marks]
The protocol is changed to
A → B : { {A, TA, KAB}K−1
A KB
}
What attacks might there be on the system now? [12 marks]
3 [TURN OVER
CST.2000.9.4
7 Computer System Modelling
A database system has a central processor and three (different) discs.
Measurements are taken for 1000 transactions on a lightly loaded system and the
following observations are made.
• The CPU scheduler initiated or resumed transaction processing 10,000 times.
The total CPU usage was 25 seconds.
• Disc 1 made 5000 transfers with an average transfer time of 10 ms.
• Disc 2 made 2000 transfers with an average transfer time of 50 ms.
• Disc 3 made 2000 transfers with an average transfer time of 20 ms.
Derive the visit counts, service times and transaction service demands. What is
the bottleneck device? What is the maximum throughput of the system measured
in transactions per second? [6 marks]
Describe two balanced systems which bound the throughput of the system. What
is the maximum throughput of these systems? [7 marks]
Recall that the throughput of a balanced system with K devices, N customers and
service demand D per device is
X(N) = N
(N + K − 1) ×
1
D
How many transactions do you expect to be in the system with a throughput of 7
transactions per second? [7 marks]
4
CST.2000.9.5
8 Neural Computing
Give evidence supporting the view that the main computational load that has
shaped the evolution of the human brain is "social computation", with sexual
success being the ultimate measure of the value of an algorithm or neural design
feature. Say what implications this has for:
• The cognitive skills and perceptual faculties that have been selected for in
brain evolution, as contrasted with the goals which are the traditional focus
of AI.
• The design of face recognition algorithms, which aim to interpret facial
expression, gesture, and intent, as well as gender and identity.
• The construction of the theory that other persons have minds, too.
• Models of action, planning, and interaction between self and others.
[8 marks]
Comment on whether this "social computation" view of human brain evolution
implies that brain science is less relevant to the goals of computer science than is
usually thought. [2 marks]
Answer any five of the following seven short questions:
(a) Roughly what is the total number of neurones in the human brain?
(b) Roughly what is the total number of synapses in the human brain? How does
this compare with the total number of stars in our galaxy, and with the total
number of galaxies in the known universe?
(c) Why is nerve impulse propagation described as "saltatory", and what purposes
are achieved by this method of signalling?
(d) What is the approximate speed of nerve impulse propagation in warm-blooded
animals, in metres/sec?
(e) Why is "white matter" white, what cells are responsible for this, and what
purpose do they serve?
(f ) Name the three principal ions involved in nerve membrane current flows, and
identify which two of them transit through voltage-dependent conductances.
(g) What causes the refractory deadtime of about 1 msec after each nerve impulse?
[2 marks each]
5 [TURN OVER
CST.2000.9.6
9 Artificial Intelligence
Consider the following story of the play Macbeth, by William Shakespeare:
The characters are Macbeth, Lady-Macbeth, Duncan and Macduff.
Macbeth is an evil noble. Lady-Macbeth is a greedy ambitious woman.
Duncan is a king. Macduff is a loyal noble. Macbeth is weak because
Macbeth married Lady-Macbeth and because Lady-Macbeth is greedy.
Lady-Macbeth persuades Macbeth to want to be king. Macbeth murders
Duncan using a knife because Macbeth wants to be king and because
Macbeth is evil. Lady-Macbeth kills Lady-Macbeth. Macduff is angry
because Macbeth murdered Duncan and because Macduff is loyal to
Duncan. Macduff kills Macbeth.
Construct a semantic network representing the above story. [8 marks]
Show the chain of reasoning leading to Macduff killing Macbeth. [5 marks]
It is possible to change the story so that Lady-Macbeth is unable to persuade
Macbeth to want to be king. Augment the story to provide a reason for
Lady-Macbeth's inability to persuade Macbeth to want to be king. Update the
semantic network to reflect the new situation. [7 marks]
10 Numerical Analysis II
Explain the terms (a) positive definite, (b) positive semi-definite for a symmetric
matrix A. If a square matrix B is non-singular, which of the properties (a) or (b)
most accurately describes BT B? What if B is singular? [4 marks]
State Schwarz's inequality for the product AB. In what way is this modified for
the product Ax, where x is a vector? What are the singular values of A, and
how are they related to the l2 norm of A? In the singular value decomposition
A = UWVT
, what is W? [5 marks]
Let ˆx be an approximate solution of Ax = b, and write r = b − Aˆx, e = x − ˆx.
Find an expression which is an upper bound for the relative error ||e||/||x|| in terms
of computable quantities. Explain how this result may be interpreted if the l2 norm
is used. [8 marks]
Suppose A is a 5 × 5 matrix and Ax = b is to be solved by singular value
decomposition. If machine epsilon ' 10−15 and the singular values of A are
1, 10−6
, 10−10
, 10−17
, 0 write down the generalised inverse W+ that you would use.
[3 marks]
6
CST.2000.9.7
11 Information Theory and Coding
(a) Prove that the information measure is additive: that the information gained
from observing the combination of N independent events, whose probabilities
are pi
for i = 1 . . . N, is the sum of the information gained from observing each
one of these events separately and in any order. [4 marks]
(b) What is the shortest possible code length, in bits per average symbol, that
could be achieved for a six-letter alphabet whose symbols have the following
probability distribution?
{
1
2
,
1
4
,
1
8
,
1
16 ,
1
32 ,
1
32 }
[3 marks]
(c) Suppose that ravens are black with probability 0.6, that they are male with
probability 0.5 and female with probability 0.5, but that male ravens are 3
times more likely to be black than are female ravens.
If you see a non-black raven, what is the probability that it is male? [4 marks]
How many bits worth of information are contained in a report that a non-black
raven is male? [1 mark]
Rank-order for this problem, from greatest to least, the following uncertainties:
(i) uncertainty about colour
(ii) uncertainty about gender
(iii) uncertainty about colour, given only that a raven is male
(iv) uncertainty about gender, given only that a raven is non-black
[3 marks]
(d) If a continuous signal f(t) is modulated by multiplying it with a complex
exponential wave exp(iωt) whose frequency is ω, what happens to the Fourier
spectrum of the signal?
Name a very important practical application of this principle, and explain why
modulation is a useful operation.
How can the original Fourier spectrum later be recovered? [3 marks]
(e) Which part of the 2D Fourier Transform of an image, the amplitude spectrum
or the phase spectrum, is indispensable in order for the image to be intelligible?
Describe a demonstration that proves this. [2 marks]
7 [TURN OVER
CST.2000.9.8
12 Computer Vision
Define the Correspondence Problem, detailing the different forms that it takes in
stereo vision and in motion vision.
(a) In each case, explain why the computation is necessary. [5 marks]
(b) What are the roles of space and time in the two cases, and what symmetries
exist between the stereo vision and the motion vision versions of the
Correspondence Problem? [5 marks]
(c) How does the complexity of the computation depend on the number of
underlying features that constitute the data? [5 marks]
(d) Briefly describe at least one general approach to an e