Question: Consider the finite strings over the alphabet {A, B, C}. Say that a string is valid if it does not contain either of the substrings AA, AB. List the invalid strings of length 3. Let (n) be the number of valid strings of length n. Show that for all n > 0 (n + 2) = 2.(n + 1) + (n). [7 marks] Hence determine a general formula for (n).

An operating system supports multi-threaded processes. Within a given user-level address-space two threads cooperate by means of a shared, circular, N-slot buffer. Semaphores are supported by the language system. Outline programs that may be executed by the thread which writes data into the buffer and the thread which reads data from it. [8 marks] How would you ensure that several threads could write to, and read from, the buffer? [4 marks] Explain how the semaphore implementation in the language system uses the thread implementation in the operating system. For the following, n is a positive integer and G is a graph of N nodes (vertices) and E arcs (edges) each with a given weight (or cost). For seven of the following indicate, with a short justification, whether the statement is true or false. (a) All functions f of the form f(n) = Ank (with A and k being constants) are in the class O(2n). (b) All sorting methods for an array of n elements take time O(n 5 ). (c) It is possible to sort an array of n elements using binary comparisons in (n log n) time. (d) It is possible to sort an array of n elements using binary comparisons using O(1) (i.e. constant independent of n) additional space. (e) Radix sorting can sort any set of integers in linear time. (f ) All straight lines from the inside of a polygon to the outside intersect the points on the edges forming its boundary an odd number of times. (g) It is always cheaper to find the shortest distance between two given nodes u, v of G than to find all N shortest distances from u to every other node. (h) It is possible to find the shortest paths between all N2 pairs of nodes of G in O(N3 ) time. (i) If G is connected then the minimal spanning subtree of G contains the N 1 edges whose weights are smallest. (j) Given n points (xi , yi), 1 6 i 6 n in a plane, then the four points (xa, ya), (xb, yb), (xc, yc), (xd, yd) such that xa is minimal of the xi , xb is maximal of the xi , yc is minimal of the yi , yd is maximal of the yi form a quadrilateral Q which can be used to speed up a convex hull algorithm by preprocessing to remove points which lie inside Q. Marks will be awarded for overall succinctness, attention to detail and absence of random guesses lacking justification. [20 marks] 6 CST.94.10.7 8 Data Structures and Algorithms Compare and contrast three implementations for a priority queue in terms of an explanation of: what the data structures represent; a sketch of the principal routines; and O(f(n)) timings when it is implemented as (a) an (unsorted) array [5 marks] (b) a sorted array [5 marks] (c) a heap [10 marks] You should consider the routines insert, extract and test-for-emptiness for a priority queue holding n elements. Consider also a routine to initialise a priority queue to hold a given set of n elements. 9 Graphics Explain with a diagram how a shadow mask cathode ray tube works. [12 marks] What might be the point of extending the scheme to accommodate five electron guns?

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