A continuous communication channel adds Gaussian white noise to signals
transmitted through it. The ratio of signal power to noise power is 30 decibels,
and the frequency bandwidth of this channel is 10 MHz. Roughly what is the
information capacity C of this channel, in bits/second?
(b) Explain the comb function, comb(t) = δX(t), its role in the sampling theorem, its
self-Fourier property, and the constraint on the spacing of the comb's tines that
is required in both the signal domain and consequently in the Fourier domain in
order to reconstruct exactly, from discrete samples, a signal having no frequency
components higher than W
(c) Explain what Logan's Theorem asserts about the richness of the zero-crossings
in signals strictly bandlimited to one octave (as illustrated in the figure below).
Consider an amplitude-modulated signal such as f(t) = [1+a(t)] c(t), where c(t)
is a pure sinusoidal carrier wave and its modulating function is [1 + a(t)] > 0.
What would Logan's Theorem say about the information contained in its
zero-crossings? Name one intended application, and at least one algorithmic
difficulty, of Logan's theorem

 

tackle all questions

(a) In the Chebyshev characterisation theorem, the best L∞ approximation to
f(x) over a closed finite interval by a polynomial pn−1(x) of degree n − 1 has
the property that the maximum error |e(x)| is attained at M distinct points
ξj such that e(ξj ) = −e(ξj−1). What is M? [2 marks]
(b) Let x = m × 2
k
represent a normalised number in a floating-point
implementation. When computing √
x show how the domain of the problem
can be reduced to x ∈ [1, 4). Find the coefficients a, b which minimise ||e(x)||∞
over [1, 4] where e(x) = ax + b −
√
x. [8 marks]
(c) Taking full account of symmetry, describe the form of the best polynomial
approximation p(x) to x
4
over [−1, 1] by a polynomial of lower degree. Sketch
x
4
and p(x), showing the extreme values of |e(x)| where e(x) = x
4 − p(x).
Hence compute the coefficients of p(x). [10 marks]
10 Introduction to Functional Programming
(a) Give a recursive definition of an ML datatype 'a tree of binary trees
consisting of nodes where data items are stored. Each such node is either
a leaf or a branch node with left and right trees as branches. [3 marks]
(b) Write a recursive function size of type 'a tree -> int that returns the
number of nodes of a given tree. [4 marks]
(c) Write an iterative function isize of type int * 'a tree -> int which
satisfies the following identity for all integers n and all trees t
isize(n, t) = size(t) + n (1)
[6 marks]
(d) Prove, by structural induction, that the identity (1) holds for the two functions
you defined.

 

(a) Consider the "eigenfaces" approach to face recognition in computer vision.
(i) What is the rˆole of the database population of example faces upon which
this algorithm depends? [4 marks]
(ii) What are the features that the algorithm extracts, and how does it
compute them? How is any given face represented in terms of the existing
population of faces? [4 marks]
(iii) What are the strengths and the weaknesses of this type of representation
for human faces? What invariances, if any, does this algorithm capture
over the factors of perspective angle (or pose), illumination geometry, and
facial expression? [4 marks]
(iv) Describe the relative computational complexity of this algorithm, its
ability to learn over time, and its typical performance in face recognition
trials. [4 marks]
(b) What is the following block of code doing over the image array image[i][j]
as it computes the resulting new image array result[i][j] ? Give the
appropriate mathematical name for this operation, and describe what it
accomplishes. What are some computer vision tasks that might use this block
of four nested for loops?
for (i = 0; i < iend; i++) {
for (j = 0; j < jend; j++) {
sum = 0;
for (m = 0;

 m < mend; m++) {
for (n = 0; n < nend; n++ ) {
sum += kernel[m][n] * image[i-m][j-n];
}
}
result[i][j] = sum/(mend*nend);
}
}

 

A simple D-type flip-flop is represented by the Prolog predicate dff whose definition
is as follows:
dff(D, 0, Q, Q).
dff(D, 1, Q, D).
The first argument is the input to the flip-flop, the second is the clock with 0
representing a falling edge and 1 representing a rising edge. The third and fourth
arguments are the previous and next states of the flip-flop. As can be seen the state
of the flip-flop changes on a rising edge of the clock.
A clocked circuit consists of three d-type flip-flops with inputs and states (D1, Q1),
(D2, Q2) and (D3, Q3). They are wired in such a way that
D1 = (Q1 ∧ Q2) ∨ (Q1 ∧ Q2)
D2 = (Q1 ∧ Q3) ∨ (Q2 ∧ Q3)
D3 = (Q1 ∧ Q3) ∨ (Q2 ∧ Q3)
(a) Using s(Q1, Q2, Q3) to represent the state of the circuit, define a predicate
that will compute the state after the next rising edge of the clock. You may
find it helpful to define predicates to represent and, or and not gates.
[14 marks]
(b) Define a predicate testcc(N, s(Q1,Q2,Q3), List) that will compute the list
of states (List) through which the circuit passes from the given initial state
s(Q1,Q2,Q3) as a result of a sequence of N rising edges of the clock. [6 marks]
6
CST.2002.13.7
8 Databases
(a) Define the operators in the (core) relational algebra. [6 marks]
(b) The core relational algebra is often extended with other operators. For the
following operators give a definition and an example of their behaviour:
(i) the full outer join operator; [3 marks]
(ii) the aggregate and grouping operator. [5 marks]
(c) X, Y and Z are all relations with a single attribute A. A na¨ıve user wishes
to compute the set-theoretic expression X ∩ (Y ∪ Z) and writes the following
SQL query.
SELECT X.A
FROM X,Y,Z
WHERE X.A=Y.A OR X.A=Z.A
(i) Give the relational algebra term that this query would be compiled to.
[2 marks]
(ii) Does the SQL query satisfy the user's expectation? J

 

 

(a) Briefly discuss the compromises that must be made when standardising a
programming language. [8 marks]
(b) Discuss the relative merits to (1) the application programmers and (2) compiler
writer of the following ways of specifying a programming language.
(i) A concise readable user manual for the language in English containing
many useful programming examples.
(ii) A very long and highly detailed description, in English, of every feature
of the language. This manual contains no programming examples.
(iii) A concise but rigorous description using a formal grammar to describe
the language syntax and making extensive use of mathematical notations
taken from set theory, λ-calculus, predicate calculus and logic to describe
the semantics of the language.
(iv) The source code for a clean and elegant machine-independent interpretive
implementation of the language

 

Explain a possible implementation technology for Java classes and objects. Your
answer should focus on storage layout for objects and on how class variables and
methods are accessed—it is not necessary to explain access qualifiers such as public
and private. Illustrate your answer with the following program; in particular
indicate its eventual output.
class test {
public int n;
public static int s = 100;
public void f(int x) { System.out.println("f1 " + (x+n)); }
public static void main(String args[]) {
test p = new test();
test2 q = new test2();
test r = q;
p.n = 4;
q.n = 5;
q.m = 6;
r.n = 7;
p.f(p.s);
q.f(p.s);
r.f(q.s);
}
}
class test2 extends test {
public int n, m;
public static int s = 200;
public void f(int x) { System.out.println("f2 " + (x+n+m)); }
}

 

(a) Give a precise definition of what is meant by the statement that a decision
problem A is polynomial-time reducible to a decision problem B. [2 marks]
(b) Consider the following three decision problems on graphs.
Connect—the collection of graphs G such that there is a path between
any two vertices of G.
Hamilton—the collection of graphs that contain a Hamiltonian cycle.
non-3-colour—the collection of graphs that are not 3-colourable.
For each of the following statements, state whether it is true, false or an
unresolved open question. Give a brief justification for your answer.
(i) Connect is decidable by a polynomial time algorithm.
(ii) Hamilton is decidable by a polynomial time algorithm.
(iii) non-3-colour is decidable by a polynomial time algorithm.
(iv) Connect is polynomial-time reducible to Hamilton.
(v) Hamilton is polynomial-time reducible to non-3-colour.
(vi) non-3-colour is polynomial-time reducible to Connect.

 

 

Arithmetic encoding compactly represents a string of characters by an enormously
precise number in the range [0,1) represented in binary by a finite sequence of
digits following the decimal point. What is remarkable is that this number can be
processed efficiently using only fixed point arithmetic on reasonably small integers.
As a demonstration, if the original text contained only the characters A, B, C and
the end-of-file mark w, such text can be arithmetically encoded using only 3-bit
arithmetic. Illustrate how it can be done by decoding the string 101101000010 on
the assumption that the character frequencies are such that the decoding tables
of size 8 and 6 are, respectively, wAABBCCC and wABBCC. The first few lines of your
working could be as follows:
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
101 101000010 |-w---A---A---B---B-+(C)++C+++C+| => C
Your answer should include a brief description of how the decoding algorithm works.
[20 marks]
2 Computer Design
(a) What is microcode and how does it differ from assembler? [6 marks]
(b) In assembler, branch instructions are used to change the flow of control. How
can flow control be determined in a microcode environment? [4 marks]
(c) With the aid of a diagram, explain what a feedback path (sometimes called a
bypass) is and how it is used to improve the throughput of a pipeline.
[6 marks]
(d) What is a branch delay slot?

 

(a) An ML program makes the following declarations:
val x = ref 0;
fun f n = (x := !x + 1; n + !x);
fun g n =
let val x = ref 0
in x := !x + 1; n + !x end;
Consider evaluating each of the following expressions:
map f [1,2,3,4];
map g [1,2,3,4];
map ref [5,5,5];
What value is returned in each case and how are the references affected?
[5 marks]
(b) Code the function filter such that filter p xs returns the list of those
elements of the list xs satisfying the predicate p. [1 mark]
(c) Use filter to express Quicksort. [4 marks]
2 Discrete Mathematics
(a) Prove the fundamental theorem of arithmetic, that any natural number can
be expressed as a product of powers of primes and that such an expression is
unique up to the order of the primes

 

 

(a) State and prove the time hierarchy theorem. [10 marks]
(b) For each of the following statements, state whether or not it can be derived
as a consequence of the time hierarchy theorem. Give justification for your
answer.
(i) There is a language in TIME(n
2
) that is not in TIME(n log n). [3 marks]
(ii) There is a language in TIME(2n) that is not decidable in polynomial time.
[4 marks]
(iii) There is a language in TIME(2n) that is not in NP.

Define a resource in a digital communication system as anything whose use by one
instance of communication prevents simultaneous use by another. Channel capacity
is one example.
(a) Give two more examples of resource in digital communication systems.
[4 marks]
(b) For the three resources, indicate how the amount of total resource can be
increased. [6 marks]
(c) How are allocations of each of these resources to instances of communication
performed?