Estimate the number of bits needed to Huffman encode a random permutation of As, Bs and Cs, with each letter occurring one million times. [3 marks] (c) Estimate the number of bits needed to Huffman encode a random permutation of As, Bs and Cs, where A occurs two million times and B and C each occur one million times. [3 marks] (d) Estimate how many bits would be needed to encode the sequence in part (b) above using arithmetic coding. You may assume that log2 3 is about 1.6. [4 marks] (e) Estimate, with justification, how many bits would be needed to encode the sequence in part (c) above using arithmetic coding. [4 marks] 3 Artificial Intelligence I (a) What are the advantages and disadvantages of constraint satisfaction problem (CSP) solvers compared with search algorithms such as A? search, etc? [3 marks] (b) Give a general definition of a CSP. Define the way in which a solution is represented and what it means for a solution to be consistent and complete. [5 marks] (c) Assuming discrete binary constraints and finite domains, explain how breadthfirst-search might be used to find a solution and why this is an undesirable approach. [3 marks] (d) Give a brief description of the basic backtracking algorithm for finding a solution. [4 marks] (e) Describe the minimum remaining values heuristic, the degree heuristic and the least constraining value heuristic

answer all

Why is it important for an operating system to schedule disc requests? [4 marks] Briefly describe each of the SSTF, SCAN and C-SCAN disc scheduling algorithms. Which problem with SSTF does SCAN seek to overcome? Which problem with SCAN does C-SCAN seek to overcome? [5 marks] Consider a Winchester-style hard disc with 100 cylinders, 4 double-sided platters and 25 sectors per track. The following is the (time-ordered) sequence of requests for disc sectors: { 3518, 1846, 8924, 6672, 1590, 4126, 107, 9750, 158, 6621, 446, 11 } The disc arm is currently at cylinder 10, moving towards 100. For each of SSTF, SCAN and C-SCAN, give the order in which the above requests would be serviced. [3 marks] Which factors do the above disc arm scheduling algorithms ignore? How could these be taken into account?

What is meant by the term flow control? [3 marks] What is meant by the term credit-based flow control? [4 marks] What is meant by start-stop (or XON-XOFF) flow control? [4 marks] A start-stop system is used on a 10 kbps link with a constant delay of 5 ms. How much buffer must a receiver keep in reserve for "stopping time" in order to prevent information loss? [3 marks] Which system is more appropriate to use across the Internet and why? [6 marks] 4 Computer Graphics and Image Processing Explain how a cathode ray tube (CRT) works, including details of how colour is achieved. [8 marks] Describe a run-length encoding scheme for encoding images whose pixels have eight-bit intensity values. [8 marks] Calculate the best possible compression ratio achievable with your scheme and describe the situation(s) in which this ratio would be achieved. [2 marks] Calculate the worst possible compression ratio achievable with your scheme and describe the situation(s) in which this ratio would be achieved.

Let N be the natural numbers {0, 1, 2 . . .}. What is meant by each of the following statements? The subset S N is recursive. The subset S N is recursively enumerable. [5 marks] How would you extend the definition of recursive enumeration to sets of computable functions? [3 marks] A sequence of natural numbers is a total function s : N N. The sequence is recursive if and only if s is computable. A finite sequence of natural numbers is specified by a pair (l, x), where l N is the number of elements, and x : [1, l] N is a function that defines those elements. The case l = 0 defines the null sequence. In each of the following cases, establish whether the set defined is recursively enumerable: (a) the set of all recursive subsets of N

A Java programmer is attempting to write a class BigNo which is intended to handle integers of arbitrary size. An integer is represented as a list of single digits arranged so that the least significant digit is at the head of the list. In outline, class BigNo is declared thus: class BigNo { private int dig; private BigNo rest; public BigNo(int n) { this.dig = n%10; if (n/10 == 0) this.rest = null; else this.rest = new BigNo(n/10); } private BigNo add(int c) . public BigNo add(BigNo that) . private BigNo add(BigNo that, int c) { if (this.rest == null) return that.add(this.dig+c); if (that.rest == null) return this.add(that.dig+c); int d = this.dig + that.dig + c; return new BigNo(d%10, this.rest.add(that.rest,d/10)); } The final return statement refers to a constructor which is not shown. Why are two constructors needed? Provide the missing constructor. Does it have to be public? Why are there three add() methods? Explain why one is public and two are private. Provide bodies for the two add() methods for which only heading lines are shown. [6 marks] Provide a suitable toString() method. [4 marks] Suppose jack and jill are BigNo representations of the integers 46 and 57 respectively. Describe carefully the effect of the call jack.add(jill)

Write brief notes on the facilities for lightweight concurrency in Java. You should cover the following topics, using code fragments to illustrate your answer: (a) creating a thread (b) mutual exclusion (c) signalling (d) asynchronous interruption (e) managing priority [4 marks each] 4 Compiler Construction With reference to a strictly-typed block-structured programming language, write brief notes on the following topics: (a) the allocation and recovery of records stored in a heap (b) the implementation of variables of union type (c) the allocation of arrays with non-manifest bounds (d) the implementation of labels and GOTO commands

The parameters for IEEE Double Precision are: = 2, p = 53, emin = 1022, emax = 1023. Explain the terms significand, sign bit, exponent, normalised number, denormal number, hidden bit, precision as used in IEEE arithmetic. What values does the hidden bit have for normalised and denormal numbers? [8 marks] In which order are the significand, sign bit and exponent stored? How is the exponent stored? Deduce how many bits are required to store the Double Precision exponent. How many bits are required to store a Double Precision number?

: Write complete C++ program to ask the user to enter 4 integers. The program must use a function to find the LARGEST integer among them and print it on the screen. function that accepts three arguments: an array, the size of the array, and a number n. Assume that the array contains integers. The function should display all of the numbers in the array that are greater than the numbern.

Write program that receives a positive integer n from the user and then calculates the sum below by using a loop. Your program needs to ask the user to re-enter a different number if the user enters a non-positive one.

What are the differences between profit and loss and cash flow statements? [5 marks] What are the differences between debt and equity finance? [5 marks] What is an option and how might it be valued? [5 marks] Comment on the current prices of high-tech stocks. [5 marks] 6 Comparative Programming Languages Outline how you would implement complex numbers in C++. Your implementation should attempt to make complex numbers look as if they were built into the language by allowing new complex numbers to be declared, initialised, assigned and operated on by the normal arithmetic operators. [13 marks] Discuss to what extent a good C++ compiler could implement your version of complex numbers as efficiently as if they had been a primitive type in the language. [7 marks] 7 Compiler Construction Give a brief description of the main features of either Lex and Yacc or the corresponding Java tools JLex and Cup. [5 + 5 marks] Illustrate their use by outlining how you would construct a parser for expressions composed of identifiers, integers, unary minus and binary operators +, , and /. Your parser is expected to create a parse tree in a format of your choice representing the expression that is presented to it. If it helps, you may assume that expressions will be terminated by writing a semicolon after them.

Consider the following problem to be solved using a Prolog program: Given a closed planar polygon chain represented as a list of n vertices [v(x1,y1), v(x2,y2), . . . , v(xn,yn)] compute the area of the enclosed polygon, and the orientation of the chain. The area is computed by the line integral 1/2 R x dyy dx where the integral is over the polygon chain. A nave solution is given by the following program, which defines the predicate area. The goal area(Chain,Area) succeeds when Chain is the list of vertices, and the magnitude of Area is the area of the polygon bounded by the chain. The sign of Area is positive if the orientation of the polygon is anticlockwise and negative if it is clockwise: area([X],0). area([v(X1,Y1),v(X2,Y2)|VS],Area):- area([v(X2,Y2)|VS],Temp), Area is Temp + (X1 * Y2 - Y1 * X2) / 2. Explain how vertices are processed by this procedure. [4 marks] Why does this program execute inefficiently? [3 marks] Write an alternative definition that is tail-recursive and makes use of accumulator variables.