The most critical submission 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.The parameters for IEEE Double Precision are: β = 2, p = 53, emin = −1022, emax = 1023. Explain the terms significand, sign bit, exponent, normalised number, denormal number, hidden bit, precision as used in IEEE arithmetic. What values does the hidden bit have for normalised and denormal numbers? [8 marks] In which order are the significand, sign bit and exponent stored? How is the exponent stored? Deduce how many bits are required to store the Double Precision exponent. How many bits are required to store a Double Precision number?

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

 

(a) (i) Many classes of artificial neural networks learn from data by forming a
lower dimensional parametric representation, or mapping, that resembles
the process of curve-fitting. Explain this idea in reference to least-squares
error minimisation or statistical regression. [4 marks]
(ii) Explain why increasing the complexity of a model may cause a neural
network's error in the training phase to become smaller and smaller, but
its generalisation in the validation phase to become worse and worse. How
would you expect the optimal complexity of a neural network model to
depend on the amount of data? [6 marks]
(b) Answer each of the following short questions:
(i) What is the approximate capacitance of nerve cell membrane, in
microFarads per cm2
, and what functional parameters of neural activity
are determined by this? [2 marks]
(ii) Approximately what range of voltages does a nerve cell membrane move
through during the course of generating a neural impulse, and what
determines this range? [2 marks]
(iii) What is the rˆole of positive feedback in nerve impulse generation?
[2 marks]
(iv) From which organ does the retina develop embryologically, and to what
cells elsewhere in the body are the retinal photoreceptors most closely
related? [2 marks]
(v) What causes the refractory deadtime of about 1 msec after each nerve
impulse, and what is its consequence?

 

 

What is a priority queue? Explain the data structure known as a heap and
document how a heap is stored in a simple linear block of memory. [4 marks]
If a heap stores N items, describe how it can be viewed as an almost-balanced
binary tree. What difference can there be between the greatest and least lengths of
paths from the root of the tree to a leaf? What operations must be performed to
move from one node in the tree to (a) its parent and (b) its offspring? [5 marks]
Describe, and estimate the costs of, procedures to
(a) insert a new item into an existing heap;
(b) delete the topmost item from a non-empty heap;
(c) starting from an array holding N items in arbitrary order, rearrange those
items so that they form a heap, taking time less than that which would be
needed if the items were just inserted into the heap one after the other.
[6 marks]
A stable sorting method is one where items whose keys compare as equal will appear
in the output in the same order that they appeared in the input list. Would a heap
sort based on the algorithms you have documented be stable? Justify your answer.
[5 marks]
6 Topics in Artificial Intelligence
Give some reasons why some tasks are suited to being solved by using constraints.
Illustrate your answer with examples of such tasks and the methods by which
constraints are used to solve them. [20 marks]
7 Operating System Foundations
Consider the operation of a scheduler in a system where there are system level and
user level processes. User processes may be IO bound or CPU bound and may have
user controlled (negative) priority.
Describe the data structures that the scheduler might use, including parts of process
descriptors that the scheduler would operate on. [10 marks]
Describe in detail the circumstances under which the scheduler would be entered
and for each different circumstance outline a scheduling algorithm that might be
used. 

 

 

A resource is managed by a system that allocates it to at most one of four requesters
for one cycle at a time. The resource is allocated in a "round robin" fashion, so that
for example if requester 2 last had the resource, requester 3 has highest priority to
acquire it, followed by, in order, requesters 0, 1 and 2. If no one requests the resource
it is not allocated, but the system still remembers who last had the resource.
(a) Define input and output variables for the system. [3 marks]
(b) Describe state variables for the system. [3 marks]
(c) Provide equations for the state control and outputs. [10 marks]
(d) Find a minimal sum of products expression for one of the outputs. [4 marks]
3 Digital Electronics
Consider two numbers X and Y , each represented by n boolean variables
xn−1xn−2 . . . x0 and yn−1yn−2 . . . y0 in the usual way so that for example
X =
Pn−1
i=0 2
i
xi
.
(a) Design a full adder to find Z = X +Y in the case where n = 2. If each gate has
a delay τ , how quickly is the result of the addition available after the inputs
are presented? [5 marks]
(b) Estimate a rough upper bound on the number of gates required to build a full
adder in combinational logic when n = 4. [3 marks]
(c) Describe two techniques for building adders which reduce gate count.
[7 marks]
(d) Design a full multiplier to find W = X ×Y for the case where n = 2. [5 marks]
3 [TURN OVER
CST.2001.2.4
SECTION C
4 Probability
(a) Solve the following inhomogeneous difference equation:
un = 2(un−1 + 3) given that u1 = 0
It may be assumed that n > 1. [5 marks]
A hardware device generates streams of ternary digits. Within a stream, each digit
is equiprobably 0, 1 or 2. A stream ends as soon as each digit has been seen at least
once. A stream may be as short as three digits (for example 201) but is usually
rather longer (for example 1110102).
(b) Clearly there are three ways in which the first k digits of a stream may all be
the same. What is the probability that the first k digits are all the same?
[1 mark]
(c) By using the difference equation above, or otherwise, determine the number of
ways in which the first k digits of a stream could comprise exactly two of the
three available digits. [5 marks]
(d) What is the probability that the first k digits comprise exactly two of the three
available digits? [1 mark]
(e) For r > 2, what is the probability that a stream is r digits long? [3 marks]
(f ) What is the expected length of a stream? [5 marks]
Hint: It may be useful to note that
X∞
r=1
rxr−1 =
1
(1 − x)
2
if 0 6 x < 1
4
CST.2001.2.5
5 Probability
Candidates for a certain first-year University Examination offer four subjects. At
their first meeting the Examiners agree that, within each subject, they will sort the
candidates into descending order of marks and those ranked in the top third will
be awarded informal Firsts for that subject.
To save effort, the Examiners agree to mark each subject simply by throwing a
fair die once for each candidate and awarding the outcome, a mark in the range 1
to 6. They reason, correctly, that 5 should be the threshold mark for a First since
approximately one-third of the candidates are likely to score 5 or 6.
Noting that 5 is the threshold mark for a First in an individual subject and that
each candidate offers four subjects, the Examiners agree further that 20 marks
(4 × 5) should be the threshold mark for a First overall in the Examination. They
reason, incorrectly, that using 20 as the threshold about one-third of the candidates
will gain Firsts overall.
When they meet after the Examination, the Examiners are astonished to discover
that, using a threshold of 20 marks, considerably fewer than one-third of the
candidates gain Firsts.
(a) Assuming that dice throws are independent, what is the probability that a
candidate obtains 20 or more marks overall? [12 marks]
(b) To what value should the Examiners lower the threshold mark for a First
overall to ensure that approximately one-third of the candidates gain Firsts?
[5 marks]
(c) What is the probability that a candidate obtains or exceeds this lower
threshold? [1 mark]
(d) Suppose the candidates were assessed more conventionally (on perceived
ability) but still awarded integer marks in the range 1 to 6 for each subject.
Suppose further that the threshold mark of 5 for a First again results in about
one-third of the candidates in any individual subject being awarded a First.
Discuss whether it would be reasonable now for the Examiners to assume
that an overall threshold of 20 would lead to approximately one-third of the
candidates gaining Firsts overall. [2 marks]
5 [TURN OVER
CST.2001.2.6
SECTION D
6 Professional Practice and Ethics
(a) What kinds of law can be used in protecting intellectual property? [6 marks]
(b) What problems are faced with each of these kinds of law in protecting software
as a kind of intellectual property (i.e. creating proprietary software)?
[4 marks]
(c) What is the ethical justification for protection of software as a kind of
intellectual property? [3 marks]
(d) What arguments are used to oppose this justification? [3 marks]
(e) What alternative is there to proprietary software? [2 marks]
(f ) How could computer professionals support themselves without proprietary
software? [2 marks]
7 Regular Languages and Finite Automata
(a) Suppose that L is a language over a finite alphabet Σ with the property that
for each number ` > 1 there is some string w in L with length(w) > ` such that
no matter how w is split up into three pieces w = u1vu2 with length(u1v) 6 `
and length(v) > 1, there is some n > 0 for which u1v
n
u2 is not in L. Prove
that L cannot be a regular language.

 

Write  java program that takes both n (as input) and n integer inputs and add the given values to a defined array.
 a program that prompts the user to enter three integers and display the integers in non-decreasing order. You can assume that all numbers are valid.
 

An operating system for a smart card is required — that is a common run-time
system for the smart card, which hosts some set of applications loaded into the
card at the time the card is issued.
What operations should the memory management component of the operating
system support in such a system? [12 marks]
The hardware engineers are concerned about complex memory management
hardware consuming too much power, but the customer demands memory
protection between the applications. Describe some solutions that could meet these
demands. [8 marks]
9 Graphics
Explain the purpose and operation of the A-buffer in rendering a sequence of images
into a framestore. [12 marks]
Exhibit an example that shows an advantage over the use of a Z-buffer. [8 marks]
10 Computation Theory
Explain what is meant by a primitive recursive function and by a partial recursive
function. [6 marks]
Show that the function giving the next state of a register machine in terms of the
current state is primitive recursive. (You may assume the existence of primitive
recursive functions for coding any n-element list of numbers (x1, . . . , xn) as a
number [x1, . . . , xn] (for each n), and for extracting the head x1 and the (coded)
tail [x2, . . . , xn] from such a coded list.)

(a) (i) Construct an efficient, uniquely decodable binary code, having the prefix
property and having the shortest possible average code length per symbol,
for an alphabet whose five letters appear with these probabilities:
Letter Probability
A 1/2
B 1/4
C 1/8
D 1/16
E 1/16
[4 marks]
(ii) How do you know that your code has the shortest possible average code
length per symbol? [2 marks]
(b) (i) For a string of data of length N bits, what is the upper bound for its
Minimal Description Length, and why? [2 marks]
(ii) Comment on how, or whether, you can know that you have truly
determined the Minimal Description Length for a set of data. [2 marks]
(c) Suppose you have sampled a strictly bandlimited signal at regular intervals
more frequent than the Nyquist rate; or suppose you have identified all of
the zero-crossings of a bandpass signal whose total bandwidth is less than one
octave. In either of these situations, provide some intuition for why you now
also have knowledge about exactly what the signal must be doing at all points
between these observed points. [3 marks]
(d) (i) Explain how autocorrelation can remove noise from a signal that is buried
in noise, producing a clean version of the signal. For what kinds of signals,
and for what kinds of noise, will this work best, and why? What class
of signals will be completely unaffected by this operation except that the
added noise has been removed? Begin your answer by writing down the
autocorrelation integral that defines the autocorrelation of a signal f(x).
[5 marks]
(ii) Some sources of noise are additive (the noise is just superimposed onto
the signal), but other sources of noise are multiplicative in their effect on
the signal. For which type would the autocorrelation clean-up strategy
be more effective, and why?