re

Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton whose language of accepted strings is L. Justify your answer. [5 marks] (b) Explain what is meant by a regular expression r over an alphabet and by the language L(r) determined by r.

Explain why it is always possible, given a regular expression r over , to find a regular expression r with the property that L(r) is the set of all strings over that are not in L(r). Any standard results you use should be carefully stated, but need not be proved.

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? 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. the question is okay 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 Ax, 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 ' 1015 and the singular values of A are 1, 106 , 1010 , 1017 , 0 write down the generalised inverse W+ that you would use.

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.

Explain how to code register machine programs P as numbers pPq N so that each e N can be decoded to a unique register machine program prog(e). [10 marks] (b) Find a number e1 N for which prog(e1) is a register machine program for computing the function one N N with one(x) = 1 for all x N. [2 marks] (c) Why is it important for the theory of computation that the functions involved in the coding and decoding given in part (a) are themselves register machine computable? (You are not required to prove that they are computable.) [2 marks] (d) Define what it means for a set of numbers S N to be register machine decidable. [2 marks] (e) Let e N*N denote the partial function of one argument computed by the register machine with program prog(e). Prove that {e N | e = one} is register machine undecidable (where one is the function mentioned in part (b)). State carefully any standard results that you use in your proof.

(a) Moore's law is an observation by Gordon Moore in the 1960s that trends in electronic manufacturing technology would result in transistor density doubling every 18 to 24 months. (i) Explain how Moore's law can be applied to processor speed and hard disk density. [5 marks] (ii) Today transistor scaling favours transistors over wires and thermal densities limit performance. Why is this resulting in commercial chips having many processor cores rather than one high-performance processor core? [5 marks] (b) PCI, used to connect I/O boards to a PC, has been replaced with PCIe. This transition has resulted in parallel communication being replaced by bundles of serial communication channels. (i) What is the difference between parallel and serial communication? Why are multiple serial channels now preferred to a parallel link? [5 marks] (ii) Why might the latency of a single load of a register on a PCIe device take longer than on PCI?

(a) A spy elects to use a self-synchronizing scrambler to encode his secret message. Explain why this will not give him any privacy and why his self-synchronising approach would be better used by a communications engineer. [5 marks] (b) With the assistance of annotated diagrams explain CSMA/CD and CSMA/CA. In your explanation, note the physical constraints on packets and networks that these approaches impose. [10 marks] (c) Consider the network buffer sizing formula B = 2T C (i) Explain this formula. [2 marks] (ii) Discuss the network architecture and traffic assumptions made in the use of this formula.

Here are four options for improving web page performance. Option 1: HTTP Caching with a Forward Proxy Option 2: CDN using DNS Option 3: CDN using anycast Option 4: CDN based on rewriting HTML URLs You have been asked to help reduce the costs for networking in the University. (a) The University pays its service provider networks'r'us, based on the bandwidth it uses; bandwidth use is dominated by students downloading external web pages. Which, if any, of the above four options would reduce the bandwidth usage? Explain your choice. (b) The delivery of online courses has become a tremendous success - but this has led to a significant increase in network costs for the University. You must select one of the options above to minimize load on the servers. Compare the operation of each option and justify a selection that provides the finest granularity of control over load to the content-servers and a selection that will serve each customer from the closest CDN server. [12 marks] (c) You have looked up the IP address of your favourite search engine on the University network and noticed the answer is different from that given to your friend when he did the lookup in Newfoundland, Canada. For each option above, indicate why it might, or might not, be used by your favourite search engine to improve web page performance.

4 Computation Theory (a) Give the recursion equations for the function n (f, g) N n+1 N defined by primitive recursion from functions f N n N and g N n+2 N. [2 marks] (b) Define the class PRIM of primitive recursive functions, giving exact definitions for all the functions and operations you use. [5 marks] (c) Show that the addition function add(x, y) = x + y is in PRIM. [2 marks] (d) Give an example of a function N 2 N that is not in PRIM. [3 marks] (e) The Fibonacci function fib N N satisfies fib(0) = 0, fib(1) = 1 and fib(x + 2) = fib(x) + fib(x + 1) for all x N. (i) Assuming the existence of primitive recursive functions pair N 2 N, fst N N and snd N N satisfying for all x, y N fst(pair (x, y)) = x snd(pair (x, y)) = y prove by mathematical induction that any function g N N satisfying g(0) = pair (0, 1) g(x + 1) = pair (snd(g(x)), fst(g(x)) + snd(g(x))) for all x N, also satisfies x N(fst(g(x)) = fib(x) snd(g(x)) = fib(x + 1)). [4 marks] (ii) Deduce that the Fibonacci function fib is in PRIM.

5 Logic and Proof (a) Proof methods for propositional logic include the sequent calculus, DPLL and BDDs. Describe briefly each of these methods. State, with reasons, which method is to be preferred for a problem that makes heavy use of the and symbols. (Note that denotes exclusive or.) [7 marks] (b) Describe briefly the procedure for constructing a BDD, illustrating your answer using the formula ((P Q) R) (P (Q R)). [7 marks] (c) Consider the following set of n + 1 propositional formulas, where n 0: Pi Pi+1 (for i = 1, . . . , n) P1 Pn+1 Describe a possible execution of the DPLL procedure to determine whether this set is satisfiable or not.

6 Logic and Proof (a) Describe briefly the concept of a decision procedure, listing at least three separate examples of decidable theories. [4 marks] (b) Outline the basic ideas behind Fourier-Motzkin variable elimination, demonstrating them with reference to the following small set of constraints: x + 2y 10 x + z 5 y 3 z 2 0 [6 marks] (c) Call a clause positive if it consists of positive literals only. Negative selection is a refinement of resolution where two clauses can be resolved only if one of them is positive; if a clause contains any negative literals, then only one of those may be resolved with a literal in another (necessarily positive) clause. Negative selection reduces the number of combinations of literals to be compared, thereby improving performance. Consider the following set of clauses: {R(0), R(1)} {P(h(z)), R(z)} {P(x), R(y)}. With negative selection, the first resolution step must involve {R(0), R(1)}, as no other positive clauses are available at the start. (i) If a set of clauses includes no positive clauses, can it be unsatisfiable? Justify your answer. [3 marks] (ii) Use resolution with negative selection to derive a contradiction from the clauses above.

(a) For each of the following claims, state whether it is true or not and give a brief justification. (i) For any linear program with n variables and m constraints, there are at most n+m m

different basic solutions. [2 marks] (ii) The Simplex Algorithm has a worst-case polynomial runtime. [2 marks] (iii) In each iteration of the Simplex Algorithm, the value of the objective function changes. [2 marks] (iv) The auxiliary linear program in Initialize-Simplex always has a feasible solution. [2 marks] (v) The fundamental theorem of linear programming also holds if linear constraints are allowed to be strict. [2 marks] (vi) The set of feasible solutions of any linear program forms a convex set. [2 marks] (b) For the following linear program, write down the auxiliary linear program used by Initialize-Simplex in slack form: [3 marks] minimize 4x1 + x2 subject to 4x1 + 2x2 4 x1 6x2 3 (c) Recall the algorithm for the unweighted vertex cover problem that is based on rounding the solution of a linear program. (i) What is the approximation ratio of this algorithm? [1 mark] (ii) Give an example of a graph and the corresponding linear program for which the gap between the linear program solution and optimal solution is as large as possible. [4 marks]

. Write program to read data using CL register and check whether it's positive or negative. java program that takes both n (as input) and n integer inputs and add the given values to a defined array

: Write program that takes n number of elements from user (where, n is specified by user), stores data in an array and calculates the average of those numbers. program that will read data from a file. The program will allow the user to specify the filename. Use a loop that will check if the file is opened correctly, otherwise display an error message and allow the user to re-enter a filename until successful.

The objective of this part of the assignment is to develop a simple unit test using JUnit and automate the process of development with ant.

Write a simple class named LengthConverter which converts kilometers to miles and vice versa (1 kilometer = 0.621371192 miles). It has the following two methods

public double kmToMile(double km) public double mileToKm(double mile) If the argument is negative, an IllegalArgumentException should be

thrown.

Write a JUnit test named LengthConverterTest to test both methods of LengthConverter. Results within 0.0001 (km or mile) of the expected results will be accepted. You should include test cases that test both valid and invalid input conditions.

Write an Ant build file, build.xml, to compile and run the JUnit tests you have developed. You should define a target named testAll that accomplishes all the tasks above.

Use Ant to compile and run the JUnit tests you have developed in Assignment 2. Invoke ant from the command-line with the testAll target. Inspect the test report (TEST-*.txt) produced as a result.

(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(it) whose frequency is , what happens to the Fourier spectrum of the signal?

Probability (a) Suppose that X is a random variable whose value r is distributed Geometric(p). Write down the expression for the probability P(X = r). [3 marks] (b) By using a suitable generating function or otherwise, show that the expectation E(X) = (1 p)/p. [5 marks] The University Computing Service define a serious power outage as a power cut that lasts for longer than their Uninterruptable Power Supply equipment can maintain power. During the course of an academical year the number of serious power outages is a random variable whose value is distributed Geometric(2/5). Accordingly, the probability of having no serious power outages during the course of a year is 2/5. pay the Computing Service 1000 for every such outage (including the first) if the total number of serious power outages in a year were two or more. Determine the expected annual sum that the Computing Service would receive. [8 marks] (d) To what value would the parameter of the Geometric Distribution have to be changed (from 2/5) for the expected annual sum to be 750? [4 marks] 6 Probability (a) Give a brief account of the Trinomial Distribution and include in your explanation an expression that is equivalent to n! r!(nr)! p r q nr for the Binomial Distribution. [5 marks] (b) An indicator light can be in one of three states: OFF, FLASHING and ON, with probabilities 1/2, 2/5 and 1/10 respectively. A test panel has five such lights whose states are mutually independent. (i) What is the probability that all five lights are OFF? [3 marks] (ii) What is the probability that three lights are OFF, one light is FLASHING and one light is ON? [3 marks] (iii) What is the probability that three or more lights are OFF and at most one is ON? [9 marks] All results must be expressed as fractions. 6 CST.2008.2.7 SECTION D 7 Software Design Software systems often incorporate structural representations of the application domain in which they operate. For example, a vehicle control system should be aware of the fact that the car has precisely four wheels. This kind of information must be captured, encoded and tested at each stage of the software design process. Using the number of wheels in a car as a simple example, describe relevant design activities and products at each of the following phases of a software project: (a) inception; [4 marks] (b) elaboration; [4 marks] (c) construction; [4 marks] (d) transition; [4 marks] (e) system operation. [4 marks] 8 Regular Languages and Finite Automata (a) Explain what is a context-free grammar and the language it generates. [4 marks] (b) What does it mean for a context-free grammar to be regular? Given any deterministic finite automaton M, describe a regular context-free grammar that generates the language of strings accepted by M. [4 marks] (c) Construct a non-deterministic finite automaton with -transitions whose language of accepted strings is equal to the language over the alphabet {a, b, c} generated by the context-free grammar with non-terminals q0 and q1, whose start symbol is q0 and whose productions are q0 abq1, q1 , q1 q0 and q1 abc. [4 marks] (d) Is every language generated by a context-free grammar equal to the set of strings accepted by some non-deterministic finite automaton with -transitions? Justify your answer. (Any standard results about regular languages you use should be carefully stated, but need not be proved.) [8 marks] 7 (TURN OVER) CST.2008.2.8 9 Professional Practice and Ethics (a) The British Computer Society Code of Conduct has four sections. What kind of professional conduct does each section cover, and how does each of these kinds of conduct benefit the profession and its members? [8 marks] (b) True or False questions: (i) A User can provide occasional use of the University computer system for a friend who is a temporary visitor. (ii) Circumstances that mitigate minor infractions of the rules promulgated by the Information Technology Syndicate include, among other things, inebriation. (iii) Appropriate use of the Cambridge University Data Network (CUDN) means bona fide academic activity plus a low level for private purposes. (iv) Small amounts of commercial activity are acceptable as long as the User is acting in a private capacity. [4 marks] (c) The IT industry is increasingly aware of its own environmental impact. Describe at least one environmental problem to which the industry contributes and how, as an IT professional, you can help to solve this problem. [4 marks] (d) "Social engineering is a greater threat to computer security than computer cracking software." What is social engineering and what measures can be taken to guard against it? [2 marks] (e) What is copyleft and how is it used to protect free, open-source, software? [2 marks]

Floating-Point Computation (a) Write a function in a programming language of your choice that takes a (32-bit IEEE format) float and returns a float with the property that: given zero, infinity or a positive normalised floating-point number then its result is the smallest normalised floating-point number (or infinity if this is not possible) greater than its argument. You may assume functions f2irep and irep2f which map between a float and the same bit pattern held in a 32-bit integer. [6 marks] (b) Briefly explain how this routine can be extended also to deal with negative floating-point values, remembering that the result should always be greater than the argument. [2 marks] (c) Define the notions of rounding error and truncation error of a floating-point computation involving a parameter h that mathematically should tend to zero. [2 marks] (d) Given a function f implementing a differentiable function that takes a floatingpoint argument and gives a floating-point result, a programmer implements a function f 0 (x) f(x + h) f(x h) 2h to compute its derivative. Using a Taylor expansion or othe rwise, estimate how rounding and truncation errors depend on h. You may assume that all mathematical derivatives of f are within an order of magnitude of 1.0. [8 marks] (e) Suggest a good value for h given a double-precision floating-point format that represents approximately 15 significant decimal figures. [2 marks] 4 CST.2008.10.5 4 Programming in C and C++ A hardware engineer stores a FIFO queue of bits in an int on a platform with 32-bit ints and 8-bit chars using the following C++ class: class BitQueue { int valid_bits; //the number of valid bits held in queue int queue; //least significant bit is most recent bit added public: BitQueue(): valid_bits(0),queue(0) {} void push(int val, int bsize); int pop(int bsize); int size(); }; (a) Write an implementation of BitQueue::size, which should return the number of bits currently held in queue. [1 mark] (b) Write an implementation of BitQueue::push, which places the bsize least significant bits from val onto queue and updates valid bits. An exception should be thrown in cases where data would otherwise be lost. [5 marks] (c) Write an implementation of BitQueue::pop, which takes bsize bits from queue, provides them as the bsize least significant bits in the return value, and updates valid bits. An exception should be thrown when any requested data is unavailable. [4 marks] (d) The hardware engineer has built a communication device together with a C++ library function send to transmit data with the following declaration: void send(char); Use the BitQueue class to write a C++ definition for: void sendmsg(const char* msg); Each of the characters in msg should be encoded, in index order, using the following binary codes: 'a'=0, 'b'=10, 'c'=1100, and 'd'=1101. All other characters should be ignored. Successive binary codes should be bit-packed together and the code 111 should be used to denote the end of the message. Chunks of 8-bits should be sent using the send function and any remaining bits at the end of a message should be padded with zeros. For example, executing sendmsg("abcd") should call the send function twice, with the binary values 01011001 followed by 10111100. [10 marks] 5 (TURN OVER) CST.2008.10.6 5 Computer Graphics and Image Processing (a) Most liquid crystal displays divide a pixel into three sub-pixels coloured red, green, and blue. Explain why this is so. [4 marks] (b) Some liquid crystal displays divide a pixel into four sub-pixels coloured red, green, blue, and white. Explain why this might be useful, what advantages it has, and what limitations it has. [6 marks] (c) Compare and contrast half-toning and error diffusion. Include in your answer an explanation of the situations in which each is superior to the other. [6 marks] (d) One method of anti-aliasing is to sample at high resolution, n n higher than the final image, and then to average each block of n n pixels to give a single pixel value. Discuss the advantages and disadvantages of using (i) Gaussian blurring, and (ii) median filtering in place of simple averaging. [4 marks] 6 CST.2008.10.7 6 Introduction to Functional Programming (a) Write an SML function propercuts: ( list) ( list * list) list that given a list ` outputs the list of all pairs of non-empty lists (`1, `2) such that `1@`2 = `. [5 marks] (b) Consider the following datatypes datatype tree = leaf of | node of tree * tree ; datatype symbol = Lbracket | Rbracket | token of ; and the SML function rep: tree ( symbol) list that represents a binary tree as a list of symbols, according to the following definition: fun rep ( leaf x ) = [ token x ] | rep ( node(l,r) ) = [ Lbracket ] @ (rep l) @ (rep r) @ [ Rbracket ] ; Write an SML function istree: ( symbol) list bool that given a list of symbols ` outputs true if there exists a (necessarily unique) tree t such that rep(t) = `, and outputs false otherwise. [10 marks] (c) Define the SML functions infix @ ; @: list * list list ; map: ( ) list list ; and rigorously argue for the correctness of the following identity: map f (`1 @ `2) = (map f `1) @ (map f `2) : list for all f : and `1, `2 : list. [5 marks] 7 (TURN OVER) CST.2008.10.8 7 Artificial Intelligence I (a) Give a general description of the operation of the Recursive Best-First Search (RBFS) algorithm. [6 marks] (b) Consider the following search tree. The numbers by the nodes denote the sum of some path cost and heuristic. The boxed nodes are goals. Describe in detail the way in which the RBFS algorithm searches this tree. Your answer should indicate the order in which nodes are expanded, the reason that this order is used, and should state which of the three goals is found and why. Note that smaller numbers represent more desirable nodes. [12 marks] (c) What shortcoming of the A? algorithm does the RBFS algorithm address, and how does it achieve this? [2 marks]

(a) Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly explain what a Reader is in the context of reading characters from data. [3 marks] A novice programmer has written the following copying program which is intended simply to read characters from data one at a time and to write them out. public class Copying { public static void main(String[] args) { int ch; while ((ch = System.in.read()) != -1) { System.out.printf("%c", (char) ch); } } } (c) Unfortunately this program causes a compile-time error. Explain what the problem is and modify the code so that the program compiles. [3 marks] (d) The amended program correctly copies data in simple cases but is found to fail when exotic characters are encountered. Why is this? [3 marks] (e) By exploiting a Reader, rewrite the program so that exotic characters no longer cause any problems. [8 marks] 2 CST.2008.10.3 2 Foundations of Programming (a) Outline the use of enum in Java programs and explain any similarities to and any differences from a Java class. [6 marks] The following fragment of code shows an early attempt to write and test a Java program to simulate the paper-scissors-stone game. In the method main() each of the identifiers a and b is assigned one of the items, paper, scissors or stone and the printf() method then says whether the first beats, draws with or loses against the second. [The rule is that paper beats stone, scissors beat paper and stone beats scissors.] public class Game { public static void main(String[] args) { Item a = allocateItem(); Item b = allocateItem(); int res = a.versus(b); System.out.printf("%s %s %s%n", a, res>0 ? "beats" : res==0 ? "draws with" : "loses against", b); } private static Item allocateItem() { ... } } enum Item { PAPER... The three possibilities PAPER, SCISSORS and STONE are declared in enum Item along with a constructor, the method versus() and any necessary additional data fields. (b) Using the method Math.random() or otherwise, provide a body for the method allocateItem() such that the method returns an Item PAPER, SCISSORS or STONE equiprobably. [6 marks] (c) Complete the enum Item so that the statements in the method main() operate as intended. [8 marks] 3 (TURN OVER) CST.2008.10.4 3 Floating-Point Computation (a) Write a function in a programming language of your choice that takes a (32-bit IEEE format) float and returns a float with the property that: given zero, infinity or a positive normalised floating-point number then its result is the smallest normalised floating-point number (or infinity if this is not possible) greater than its argument. You may assume functions f2irep and irep2f which map between a float and the same bit pattern held in a 32-bit integer. [6 marks] (b) Briefly explain how this routine can be extended also to deal with negative floating-point values, remembering that the result should always be greater than the argument. [2 marks] (c) Define the notions of rounding error and truncation error of a floating-point computation involving a parameter h that mathematically should tend to zero. [2 marks] (d) Given a function f implementing a differentiable function that takes a floatingpoint argument and gives a floating-point result, a programmer implements a function f 0 (x) f(x + h) f(x h) 2h to compute its derivative. Using a Taylor expansion or otherwise, estimate how rounding and truncation errors depend on h. You may assume that all mathematical derivatives of f are within an order of magnitude of 1.0. [8 marks] (e) Suggest a good value for h given a double-precision floating-point format that represents approximately 15 significant decimal figures. [2 marks] 4 CST.2008.10.5 4 Programming in C and C++ A hardware engineer stores a FIFO queue of bits in an int on a platform with 32-bit ints and 8-bit chars using the following C++ class: class BitQueue { int valid_bits; //the number of valid bits held in queue int queue; //least significant bit is most recent bit added public: BitQueue(): valid_bits(0),queue(0) {} void push(int val, int bsize); int pop(int bsize); int size(); }; (a) Write an implementation of BitQueue::size, which should return the number of bits currently held in queue. [1 mark] (b) Write an implementation of BitQueue::push, which places the bsize least significant bits from val onto queue and updates valid bits. An exception should be thrown in cases where data would otherwise be lost. [5 marks] (c) Write an implementation of BitQueue::pop, which takes bsize bits from queue, provides them as the bsize least significant bits in the return value, and updates valid bits. An exception should be thrown when any requested data is unavailable. [4 marks] (d) The hardware engineer has built a communication device together with a C++ library function send to transmit data with the following declaration: void send(char); Use the BitQueue class to write a C++ definition for: void sendmsg(const char* msg); Each of the characters in msg should be encoded, in index order, using the following binary codes: 'a'=0, 'b'=10, 'c'=1100, and 'd'=1101. All other characters should be ignored. Successive binary codes should be bit-packed together and the code 111 should be used to denote the end of the message. Chunks of 8-bits should be sent using the send function and any remaining bits at the end of a message should be padded with zeros. For example, executing sendmsg("abcd") should call the send function twice, with the binary values 01011001 followed by 10111100. [10 marks] 5 (TURN OVER) CST.2008.10.6 5 Computer Graphics and Image Processing (a) Most liquid crystal displays divide a pixel into three sub-pixels coloured red, green, and blue. Explain why this is so. [4 marks] (b) Some liquid crystal displays divide a pixel into four sub-pixels coloured red, green, blue, and white. Explain why this might be useful, what advantages it has, and what limitations it has. [6 marks] (c) Compare and contrast half-toning and error diffusion. Include in your answer an explanation of the situations in which each is superior to the other. [6 marks] (d) One method of anti-aliasing is to sample at high resolution, n n higher than the final image, and then to average each block of n n pixels to give a single pixel value.