Solve the following Questions.

A Java program is being developed to assist with the processing of examination marks. A test program begins as follows: public class Exam { private static Mark[] question = {new Mark(8), new Mark(), new Mark(6), ... The program makes use of a class Mark which begins: class Mark { public boolean attempted; public int score; ... The Mark array question has one entry for each candidate so the length of the array indicates the total number of candidates. An entry such as new Mark(8) sets up a Mark object whose data eld attempted is set to true and whose data eld score is set to 8, indicating that the candidate attempted the question and was awarded 8 marks. It may be assumed that every score is an integer in the range 0 to 10 inclusive. An entry such as new Mark() sets up a Mark object whose data eld attempted is set to false (and whose data eld score is arbitrary) indicating that the candidate did not attempt the question. (a) Supply suitable constructors for class Mark [4 marks]

(a) Assume x = y = z = m. Using worst-case analysis, estimate xy, xy. Find an expression for w where w = zxy. [4 marks] (e) Working to 4 signicant decimal digits only, compute w when x = 2.018, y = 2.008,z = 4.058. Given m ' 0.5103, how many signicant decimal digits of w can be relied on? [3 marks]

Let A,B,C be sets. Dene the Cartesian product (AB) and the disjoint union (A + B). [3 marks] Let f (AB),g (BC) be relations between A and B, B and C respectively. Dene the inverse relation f1 between B and A and the product relation (f g) between A and C. [3 marks] What conditions must be satised for the relation f to be a function f : A B? [2 marks] Writ (A B) for the set of all functions from A to B. If A,B are both nite, |A| = a,|B| = b, how many elements are there in (AB), (A + B), (A B)? [2 marks] If f and f1 are both functions, we say that f is a bijection, and we writ A = B. If A,B are both nite and f : A B is a bijection, prove that a = b. (?) [2 marks] Establish explicit bijections between the following pairs of sets: (a) A (BC), (A B)(A C); [3 marks] (b) (A + B) C, (A C)(B C). [4 marks] If A, B, C are all nite, verify that the cardinality condition (?) above is satised in each case. [1 mark]

(a) What is DeMorgan's theorem? [4 marks] (b) What are minterms, essential terms and prime implicants? [6 marks] (c) What are the prime implicants, essential terms and minimum sum of products for f = (a.b)(c + d)? [6 marks] (d) Whenever g = a.b is true, if we do not care what the output of f is, determine the new minimum sum of products form for f. [4 marks] TLBs and caches are examples of content-addressable memories (CAMs). (a) What is the principal dierence between a CAM and a RAM? [4 marks] (b) What is the dierence between fully associative, set associative and direct mapped lookup? [6 marks] (c) Why are TLBs always much smaller than caches? [4 marks] (d) Which of the lookup mechanisms in part (b) is usually used for a TLB and why aren't the other mechanisms usually used? [6 marks] (b) Write two methods int getCount() and double getMean() which, when handed the actual argument question, return the number of candidates who attempted the question and the mean mark achieved by those candidates respectively. If no candidates attempted the question, getMean() should return -1d. [9 marks] (c) Writ a method int[] getRank() which begins: private static int[] getRank(Mark[] q) { int[] rank = {0,0,0,0,0,0,0,0,0,0,0}; This method should return the int array rank with each element rank[i] set to the number of candidates who scored more than i marks. Note that if the maximum score is 9 then both rank[9] and rank[10] will be zero and rank[8] will be the number of candidates who scored 9. [7 marks] (a) Describe how the Lempel Ziv text compression algorithm works, illustrating your answer by deriving the sequence of numbers and corresponding bit patterns it would generate when applied to a string starting with the following 24 characters: ABCDABCDABCDABCDABCDABCD ... You may assume that the initial table is of size 256 (containing bytes 0 to 255) and that the codes for "A", "B", "C" and "D" are 65, 66, 67 and 68, respectively. [12 marks] (b) Estimate how many bits the algorithm would use to encode a string consisting of 1000 repetitions of the character "A". [8 marks] (a) Discuss to what extent a programmer can expect a program that conforms to a standard to generate identical results when run under dierent conforming compilers on dierent machines. [6 marks] (b) ALGOL 60 provided call by value and call by name, Pascal provided call by value and call by reference, and ALGOL-W provided a variety of calling methods including call by result and call by value-result. Briey describe the calling mechanisms just mentioned and discuss why most modern programming languages provide only call by value. [8 marks] (c) Discuss the reasons why languages such as Fortran, Algol and PL/I designed in 1950s and 1960s are less widely used than languages designed in the last 20 years. [6 marks] (a) Describe a scheduling algorithm with the following properties: favours I/O-intensive processes responds dynamically when processes change their behaviour: e.g. enter a compute-bound or I/O-intensive phase has acceptable context switching overhead avoids indenite overlook (starvation) of a process [7 marks] (b) In order to carry out its functions, a ling system holds metadata on each stored object. (i) What is this metadata likely to comprise? [6 marks] (ii) Describe the directory service functions of a ling system, including how the metadata is used. [7 marks] (a) For Single Precision in the IEEE binary oating-point standard (IEEE 754) the precision is dened as 24, and the exponent requires 8 bits of storage. With reference to IEEE Single Precision, explain the terms exponent, signicand, precision, sign bit, normalised number, denormal number. [6 marks] (b) Explain the term hidden bit. What are the values of the hidden bit for normalised and denormal numbers? How is the exponent stored and why? How are the exponent, signicand and sign bit arranged in memory? [4 marks] (c) Let x denote the oating-point representation of a number x. Dene the terms absolute error (x) and relative error (x) in representing x. How are x and x related? Dene machine epsilon (m). [3 marks]