Operating concurrently on each link direction, the device will receive the data stream, delay it, then transmit it onwards to the other node. The network uses a serial link operating at one gigabit per second, and the researchers require to be able to vary the delay such as to simulate links of between 1 and 5000 kilometres in length. network node network node delay simulator How much buffer memory is required to implement the device? [3 marks] How can the data on the high-speed serial links be converted to a more manageable form? [4 marks] Outline a design for the delay simulator, and hence address the following points: • How many banks of memory does your design require, and what type(s) will be used? • How will the control logic function, and what technology will it be built using? • How will the delay inserted by the device be adjusted?

 

Consider a two-bit multiplier with inputs x1, x0, y1, y0 and outputs z3, z2, z1, z0 such
that
Z = Y × X
where Z, Y, X are the positive integers represented by z3z2z1z0, y1y0 and x1x0
using the obvious representation.
Find a minimal sum of products expression for each of z3, z2, z1 and z0. [10 marks]
Comment on the complexity of building an eight-bit multiplier using a minimal
sum of products form. [3 marks]
Describe another way of building an eight-bit multiplier. [5 marks]
2
CST.2000.2.3
3 Digital Electronics
You are required to build a circuit whose inputs are a data input D and a clock C.
The data input D is used to pass a stream of bits into the circuit. Every 64 bits, an
8-bit synchronisation pattern 01100110 appears in the stream, followed by 56 bits
of changing information.
(a) Design a combinational circuit incorporated with an 8-bit shift register that
recognises the synchronisation pattern and asserts a signal r for 1-bit time
whenever the pattern appears. [5 marks]
(b) The pattern 01100110 may of course appear in the changing information bits.
Thus we must have some means of remembering if we are in sync so that we
can expect the 01100110. Let us use the following state diagram, where e
(expected) will be true whenever we expect to see r true.
e¯
e.r¯
IN SYNC HUNTING r¯
e.r
e.r¯
e.r r
ONE
SIGHTING
e¯
Explain what each of the states is for and implement the finite state machine
described in the diagram, including the equation of s which is true while the
machine remains in synchronisation. [10 marks]
(c) Explain briefly how the signal e might be produced. [2 marks]
(d) Another output, the byte clock b, is to have a low to high transition every eight
bits, with one such transition occurring when an expected synchronisation
pattern appears in the shift register (and then eight bits later, etc.). Explain
how this signal might be produced. [3 marks]
3 [TURN OVER
CST.2000.2.4
SECTION C
4 Probability
An ordinary fluorescent light tube exhibits a lack of memory property in that its
life expectancy does not depend on how long it has been working. A typical tube
may be expected to work for another 5040 hours no matter how long it has been
working so far.
If a room contains eight such tubes and all are working, one may expect the first
failure after 630 hours (5040/8). If the dud tube is not replaced, after how many
more hours may one expect the second failure and (again assuming no replacement)
after how many more may one expect the third failure? [2 marks]
Consider a meeting room which is equipped with four light fittings, each equipped
with two such tubes. The management has decided that the room lighting is
acceptable provided at least one tube in each pair is working. As soon as a second
tube fails in any one fitting, a maintenance crew replaces all dud tubes in the room.
Starting with eight working tubes, the crew may be called out as early as the second
failure or as late as the fifth failure.
Let X be a random variable whose value r is the number of dud tubes at the
moment the maintenance crew is called out. Clearly P(X = 0) = P(X = 1) = 0.
Determine the values of P(X = 2), P(X = 3), P(X = 4) and P(X = 5). Express
all four results as fractions. It may be assumed that all fittings are permanently
switched on and that tubes fail independently. [12 marks]
What is the expectation, E(X)? [4 marks]
The management rounds the value of E(X) down to the nearest integer and uses
the derived value for estimating the number of tubes that have to fail between
successive call-outs of the maintenance crew and the time interval between such
call-outs. What is this time interval in hours?

 

 

(a) Suppose that L1 and L2 are regular languages (over the same alphabet Σ)
accepted by deterministic finite automata M1 and M2 respectively. Show that
there is a deterministic finite automaton M such that for all strings u over Σ,
M accepts u if and only if u /∈ L1 or u ∈ L2. [8 marks]
(b) Show that if a deterministic finite automaton M over alphabet Σ accepts all
strings of length less than the number of states in M, then it must accept all
strings over Σ. [4 marks]
(c) What does it mean for two regular expressions over an alphabet Σ to be
equivalent? Using parts (a) and (b), or otherwise, describe an algorithm
for deciding equivalence of regular expressions. State carefully any standard
results that you rely upon. [8 marks]
9 Professional Practice and Ethics
(a) Name two kinds of ethical theory and give a defining characteristic for each.
[4 marks]
(b) The Code of Conduct of the British Computer Society has 17 clauses. The
clauses are organised under four main headings: The Public Interest, Duty to
Relevant Authority, Duty to the Profession, and Professional Competence and
Integrity. State one of the requirements under each heading. [4 marks]
(c) The Computer Misuse Act 1990 created three new offences. Name two of
them. Apart from the person who actually commits the offence, to whom else
does the law extend? [4 marks]
(d) The Data Protection Act 1998 sets out eight principles for the protection
of privacy in data collection, handling and distribution. Name two of these
principles and explain how each serves to protect privacy

(a) FIFO, LRU, and CLOCK are three page replacement algorithms.
(i) Briefly describe the operation of each algorithm. [6 marks]
(ii) The CLOCK strategy assumes some hardware support. What could you
do to allow the use of CLOCK if this hardware support were not present?
[2 marks]
(iii) Assuming good temporal locality of reference, which of the above three
algorithms would you choose to use within an operating system? Why
would you not use the other schemes? [2 marks]
(b) What is a buffer cache? Explain why one is used, and how it works. [6 marks]
(c) Which buffer-cache replacement strategy would you choose to use within an
operating system? Justify your answer.

(a) Devices are ultimately connected to the CPU via a bus.
(i) What are the main components of a bus? [3 marks]
(ii) Describe how the CPU uses a bus to communicate with a device.
[3 marks]
(iii) How does the situation become more difficult when we have DMA-capable
devices? [2 marks]
(iv) Why does a typical computer have more than one bus? [2 marks]
(b) A programmer at MegaCorp is given the task of optimising a program for
which no source code exists; all that is available is an executable file.
(i) How could the programmer modify the operating system to work out
which parts of the program are executed frequently, and thus might be
candidates for optimisation? [4 marks]
(ii) The programmer determines that the slowest parts of the program involve
loops which perform repeated integer multiplications, and where the
multiplicand is always either 8 or 15. How could the program be modified
to use faster ALU operations instead? [6 marks]
6
CST.2006.1.7
SECTION D
9 Programming in Java
For each of the following Java language features, give an example of a place in a
large Java library where you might expect it to be used. Explain exactly what the
feature achieves, why that is a benefit in the context you describe, and what risk
or inconvenience might arise if the feature were not deployed.
(a) Methods that have been declared as protected. [4 marks]
(b) Classes that are labelled as final. [4 marks]
(c) Generic methods - that is, ones where the types of their arguments
and results involve other types enclosed in angle brackets, as in
ClassName. [4 marks]
(d) Fields within a class that are marked as private. [4 marks]
(e) Parts of the library defined as an interface rather than as a class.
[4 marks]
In some cases you may refer to a concrete example present in the existing Java
libraries. You may also propose uses that current libraries do not exploit. Marking
will pay attention to the extent to which you cover the topics you have been
explicitly asked to explain: ill-structured general discussions of the Java features
concerned will attract little credit.
 

The "Game of Life" is played on a board of square cells. Each cell is either "live"
or "dead". Initially most cells are dead, but a seeding pattern of live ones is set
up. Each square cell has eight immediate neighbours (North, South, East, West,
and four diagonal ones). At each time step all cells transform simultaneously. If
a cell is dead, it becomes alive if it had (just before this time step) exactly three
live neighbours. If it is alive, it becomes dead unless it has two or three live
neighbours. In this question, locations beyond a 1000 × 1000 board are to be
treated as permanently dead.
(a) Show how to set up a simple Java 2-dimensional array of boolean values to
represent a Life Board, with all cells initially "dead". [2 marks]
(b) For a location (i, j) on the board, give code that will decide whether the next
state of that cell should be alive or dead. Make it clear how your code copes
if the cell is at the boundary of the board. [4 marks]
(c) Referring to part (b),te code that takes one board representing the current
state of the game and fills in a second board-array with the state arrived at
after one time step. What would happen if instead of using two arrays you
wrote the new cell state directly back, using just a single copy of the board?
[3 marks]
(d) Re-work your solution to part (c) so that you can perform a time step using just
one board. You may need to use a 1000-element vector to store information
in a way that makes the update safe. [7 marks]
(e) All the code you have written so far uses an array of boolean values. Some
programmers would instead use an array of int values and treat each of
the 32 bits in each int as giving the status of a cell. Suppose you have a
2-dimensional array of integers of size 1024 by 32 (that size is chosen so the
array of integers may be viewed as a 1024 by 1024 array of bits): give code to
retrieve a bit from a given position (i, j). [4 marks]
8
CST.2006.1.9
SECTION E
11 Algorithms
(a) What is the time complexity of binary search on a list of N items? [1 mark]
(b) Binary search requires list items to be in sorted order. What is the best
possible worst-case time complexity achievable by a comparison-based sorting
algorithm? Credit will be given for a clear explanation of your answer, but
there is no need to provide a formal mathematical analysis or proof. [7 marks]
(c) A researcher proposes a ternary search algorithm which repeatedly compares
the search key with the two list items that most accurately trisect the
remaining sorted search space.
(i) Derive asymptotic expressions for the number of list items queried by
binary search and by ternary search in the worst case. Explain your
derivations in terms of worst-case executions of the search algorithms.
[6 marks]
(ii) Approximately how many extra list items are queried by a ternary search
compared with an equivalent binary search, in the worst case? Express
your answer as a numeric percentage. If required, you may assume that
the list being searched is very large and that log2
(3) ≈ 1.6.