Have a C compiler which is ANSI conforming in all respects except that it has no facility for the definition, declaration or use of standard C structures. Outline a set of routines written in this language to provide a mechanism for handling structures. Your solution should contain the following: (a) function prototypes for each of the routines [10 marks] (b) a few sentences describing the behaviour of each function [10 marks] Note: no code other than the prototypes is required. 6 Programming Language Compilation Discuss the issues that must be considered when designing the calling sequence to be used for recursive procedures on a machine with several general-purpose central registers. Assume that the language allows procedures to be declared within other procedures and that procedures may be passed as arguments in calls. Pay particular attention to how arguments, local variables and free variables are accessed

Describe the functionality you would expect to find in the file system directory service of a multi-user operating system. [10 marks] Describe two ways in which multiple names for the same file can be supported, and what problems arise as a result. [10 marks] 7 Data Structures and Algorithms A strictly binary tree is a binary tree in which every node that is not a leaf has two children. Suppose that for a strictly binary tree there exists c > 1 such that the ratio of the lengths of any two root-to-leaf paths is no greater than c. For a tree of height h, derive the upper and lower bounds on N, the number of nodes in the tree. [15 marks] Suppose instead that every node that is not a leaf has n children. What then would be the upper and lower bounds? For a given problem with inputs of size n, algorithms A, B, C are executed. In terms of running time, one of the algorithms is O(n), one O(n log n) and one O(n 2 ). Some measured running times of these algorithms are given below: INPUT SIZE 512 1024 2048 A 70 134 262 ALGORITHM B 135 517 2053 C 42 86 182 Identify which algorithm is which and explain the observed running times. Which algorithm would you select for different values of n? [20 marks] 9 Graphics I RasterOp is the name given to an operation which generates, from a number of rasters of pixel values, another raster of pixel values. Describe suitable versions that could be used (a) to move a window on screen while preserving background [12 marks] (b) to blend two images in proportions given by a mask [8 marks] 5 [TURN OVER CST.93.3.6 10 Numerical Analysis t do the parameters p (precision), emin and emax specify? How is the value of an exponent e stored? [3 marks] Explain the terms normalised number , denormal number , hidden bit and NaN . [4 marks] In terms of the stored bit-pattern, how can each of the following be recognised: 0, , denormal number, NaN.

A number of techniques exist to reduce the penalty of control-flow hazards. Discuss four of the following: (a) delayed branches and annulment (b) predicated execution and conditional moves (c) dynamic branch prediction caches (d) jump target hints and subroutine call return prediction stacks (e) next-fetch predictors and branch target buffers [4 marks each] Why is good control-flow prediction so important to a dynamically scheduled superscalar processor? [4 marks] 5 Business Studies What is meant by a project's critical path and why is it important? [5 marks] An organisation which manufactures about 30 different kinds of widget has asked you to develop a web site which includes an on-line catalogue and order entry facility. You may assume that service provision (including access to a merchant system) will be provided by a service provider, at no cost to this project. Draw up a task list and project plan, and indicate the critical path. [5 marks] Estimate a price and time to completion for the job, and how much working capital will be required, stating your assumptions. [5 marks] What precautions can be taken to ensure that the project completes to the customer's satisfaction?

A posting on a newsgroup announces the invention of a new compression algorithm, and claims that the method will guarantee to compress at least 10% of all possible input files by at least 10% of their original size, but that it might (unfortunately) cause some of the other 90% of possible inputs to expand by a factor of up to 90. Discuss how believable and reasonable the claim is. [8 marks] Various compression utilities running on personal computers typically reduce text files to 1/3 of their original size. Estimate the proportion of all possible files (including binary ones) whose original length is less than 64 kbytes that could be compressed to this extent by an ideal compression algorithm. What proportion of the same set of files consists of just alphanumeric characters, blanks and newlines?

Summarise the idea of the 3-address instruction and briefly indicate its advantage over stack-oriented instructions as intermediate code. Explain the notion of the flowgraph containing such instructions, giving such a flowgraph for the C function: int f(int x, int g()) { return x==0 ? g(x) : x*f(x-1, g); } You should explain how arguments and results of functions in your example are communicated; also make clear any difference in the representation of calls to f and g. [8 marks] Given a flowgraph in which each node contains a single 3-address instruction (not grouped into basic blocks), design dataflow equations (and thence an algorithm) for reaching definitions. [9 marks] The reaching definitions RD(n) of a node n are the set of nodes m such that m contains a 3-address instruction such as m : x := a + b which writes to ("defines") one of its operands (here x), and such that there is a path in the flowgraph from m to n by which the value given to x at m may still be unchanged (by other assignments to x) when it reaches n. Hence in 1: y := 1; 2: if x<=1 goto 5; 3: y := x*y; 4: x := x-1; goto 2; 5: return we would have RD(3) = {1, 3, 4} and RD(4) = {3, 4}; note that the definition (of y) at 3 reaches via the loop back to 3 even though it would not be available because of node 4. Develop a program in which m RD(n) but which no run-time execution can cause the value assigned at m to reach n. To what extent can we fix this problem? [3 marks] [Hint: work by analogy from live variable or available expression analysis; determine the direction of the analysis and suitable gen and kill properties of nodes. You may find it convenient to consider cases like "l contains a statement x := e" or "l contains some other statement".]

Some banks issue their Automatic Teller Machine (ATM) card customers with a randomly selected personal indentification number (PIN). Others issue their customers with an initial PIN only, and let the customers choose their own PIN the first time they use the card in an ATM. Describe the advantages and disadvantages of these approaches. [5 marks] Again, some banks compute the customer PIN by encrypting the account number using DES and a key known only to their central systems and ATMs, taking the first four hex digits of the result, replacing the digits A, . . . , F with 0, . . . , 5 respectively, and finally, if the first digit of the result is 0, replacing it with a 1. What is the probability that a criminal can get the PIN right given three guesses? [5 marks] Yet other banks have used DES, and a key known only to their central systems and ATMs, to encrypt the PIN (whether randomly generated or customer selected); they then write the result on the magnetic strip on the customer's card, so that the ATM can verify it without reference to the central system. Describe the disadvantages of this arrangement. [5 marks] In order to prevent attacks based on manipulating magnetic strips, banks in some countries have moved to using smart cards. What effect would you expect such a move to have on the incidence of card-based fraud?

Explain how a parse-tree representation of a program may be converted into a stack-based intermediate language giving sketches of code to translate expressions, assignments and the if-then-else command; you should also explain how occurrences of a variable in an expression or assignment are translated. The program may be assumed to conform to the following syntax: E -> n | x | E + E | f(E,E) D -> let f(x,x) = {Dseq; Cseq; E} | let x = E C -> x := E; | if E then C else C Cseq -> C | C Cseq Dseq -> D | D Dseq with start symbol Dseq. Here n corresponds to integer constants, x corresponds to identifiers used as variable names and f corresponds to identifiers used as function names (you may assume these are disjoint). The function declaration construct has the effect of defining a function which, when called, makes declarations, performs commands and then returns the result of its expression; note that therefore functions may be defined within functions, but the above restriction on identifiers means that they cannot be returned as results. [20 marks] 8 Prolog for Artificial Intelligence Write Prolog programs that define the following predicates. Your programs should ensure that backtracking does not produce spurious alternative solutions. (a) The nth element of a list: nth(X,N,L) instantiates X to the Nth element of list L. Assume that list elements are numbered increasing from 1. [4 marks] (b) The last element of a list: last(X,L) instantiates X to the last element of list L. [4 marks] (c) Remove an element from a list: remove(X,L,M) instantiates M to a list containing all the elements of list L except for every occurrence of term X. [6 marks] (d) Substitute one element for another: subst(L,X,Y,M) instantiates M to a list containing all the elements of list L except that every occurrence of term X in L is replaced by term Y in M.

The relational model of data was introduced in the early 1970s in a sequence of papers by E.F. Codd. This model proposes a tabular view of data, with a simple Data Manipulation Language (DML) based on relational algebra or relational calculus. Briefly explain the essential features of the model and its DML. [6 marks] Later work by Codd and others addressed weaknesses in the expressive power of the relational model. For each of the following give an example to show how the weakness arises, and explain an approach proposed to resolve the difficulty: (a) computing the transitive closure [4 marks] (b) manipulating collections of records [4 marks] (c) handling entity specialisation [6 marks] In case (c) you should outline the proposals of either the Object-Oriented Database System Manifesto or the Third Generation Database System Manifesto. 10 Introduction to Functional Programming Write an ML function upto of type int -> int list such that upto n generates the list [1,2,3,...,n]. [7 marks] What is wrong with the following function to take the head of a list? fun wrong_headed [h,t] = h; What is the type of wrong_headed? [5 marks] Why is the following function to evaluate Fibonacci numbers inefficient? fun fib 0 = 1 | fib 1 = 1 | fib n = fib(n-1) + fib(n-2); Write a similar but more efficient version.

Give three examples of problems in computer vision which are formally ill-posed. In each case explain how one or more of Hadamard's criteria for well-posed problems has failed to be satisfied. Illustrate how the addition of ancillary constraints or assumptions, even metaphysical assumptions about how the world behaves, enables one to convert the ill-posed problem into a well-posed problem. Finally, discuss how the use of Bayesian priors can perform this function. [20 marks] 12 Complexity Theory (a) Describe the problem 3-SAT. [2 marks] (b) Show how any instance of the seemingly more general problem n-SAT can be reduced to an equivalent one where each term has exactly three literals in it. Estimate how much larger the reduced problem would be than the original one. [4 marks] (c) A certain computation using a non-deterministic Turing machine completes in T time-steps. The Turing machine has k states and uses an alphabet of N symbols. A major theorem underpinning the concept of NP-completeness is based on a conversion of a description of such computations to boolean formulae which characterise them. Explain how, in such a reduction, boolean variables may be used to describe states that the Turing machine might be in. Show how to derive those components of the boolean formula that relate just to the way in which the Turing machine moves its read-write head. Your explanation should be sufficiently complete and carefully explained that it could be used as a specification of a program that would perform that part of the translation from Turing machine descriptions to boolean formulae. You should not attempt to explain the rest of the boolean formula or how it fits into a complete proof or program. [11 marks] (d) In terms of T, k and N, about how many symbols does it take to write the boolean expression you generate?

Write java program that takes both n (as input) and n integer inputs and add the given values to a defined array

Write program to print your name on the screen. Write program to print "Welcome to C++" on the screen Describe the Minimax Algorithm for searching game trees.

Explain how the Alpha-Beta Algorithm is a better way to search game trees. [10 marks] These two algorithms depend on certain assumptions about how the game is played. What are they? [5 marks] 9 Database Topics Describe briefly what is involved in extending a programming language to support persistence of data. [5 marks] What are the advantages and drawbacks of using a persistent programming language for database management as opposed to a conventional DBMS based on the ANSI/SPARC architecture? [8 marks] To what extent may it be said that the ODMG proposals offer the advantages of persistent programming within a framework of conventional database management? [7 marks] 10 Information Retrieval Give a formula for weighting the index terms in a query for an initial search of a document file, and indicate how an overall query-document matching score is computed. [5 marks] Outline the main features of the general model underpinning this method of weighting and scoring. [5 marks] What is the motivation for using the various types of information employed in the method you have described? [5 marks] What further information could you use after conducting an initial search over the file? Sketch how you would apply this to modify the original query and construct a new one

(a) Write down the marginal distribution for X and compute the marginal entropy H(X) in bits. [3 marks] (b) Write down the marginal distribution for Y and compute the marginal entropy H(Y ) in bits. [3 marks] (c) What is the joint entropy H(X, Y ) of the two random variables in bits? [4 marks] (d) What is the conditional entropy H(Y |X) in bits? [4 marks] (e) What is the mutual information I(X; Y ) between the two random variables in bits? [2 marks] (f ) Provide a lower bound estimate of the channel capacity C for this channel in bits. [2 marks] (g) Draw a Venn diagram that describes the relationships among the quantities H(X), H(Y ), H(X|Y ), H(Y |X), H(X, Y ), and I(X; Y ). [2 marks]

Consider a single processor system in which multiple processes are running. (a) What does it mean for a process to be I/O bound? What does it mean for it to be CPU bound? [2 marks] (b) What is the difference between preemptive and non-preemptive scheduling? Which one requires specific hardware support and what is that hardware support? [3 marks] (c) Two processes, A and B, have the following sequential execution patterns: A: [cpu 4 ms; I/O 2 ms; cpu 4 ms; I/O 2 ms; cpu 4 ms] B: [cpu 1 ms; I/O 2 ms; cpu 1 ms; I/O 2 ms; cpu 1 ms] I/O operations for the two processes do not interfere with each other and are blocking. (i) If the processes are run consecutively one after another, what is the elapsed time for all to complete? [2 marks] (ii) Sketch the execution pattern under non-preemptive scheduling and determine the total elapsed time for completion. You may assume that processes are scheduled in the order in which they become ready to run and that in the event of a tie A has priority over B. You may further assume that the scheduler and context switches take negligible time. [6 marks] (iii) Repeat (c)(ii) but for a preemptive scheduler that operates on a time slice of 2 ms, that is, no process can run for more than 2 ms at a time (unless no other process is runnable). [6 marks] (iv) Is there any evidence from your results for (c)(ii) and (c)(iii) of a significant advantage for either scheduling method?

(a) What is the difference between a logical or virtual memory address and a physical memory address? [2 marks] (b) Consider a variable which is bound to a single logical address for the duration of process execution. How is it possible for the variable to be bound to different physical addresses during process execution? [3 marks] (c) In a demand paging system, what are the factors that can be taken into account when deciding which valid page should be made a victim? [5 marks] (d) Consider a demand paging system in which hardware can trap unauthorised read or write accesses, but cannot perform any update to use counts or written/dirty bits. How can these be performed efficiently in software? [6 marks] (e) What is copy-on-write? How can it be implemented in a demand paging system? [4 mark

Explain the notion of scale-space and how it is used in various areas of computer vision. Include the following: (a) Pyramidal representations of image structure across successive scales of blurred undersampling. (b) Edge detection operators that extract edges at particular scales of analysis, but not at others. [5 marks] (c) The behaviour of zero-crossings, their trajectories and "fingerprints" in scale-space. (d) The generalised wavelet transform as a self-similar mapping into scale-space, and its attempt to capture invariances under the transformations of dilation, translation and rotation. [5 marks] 13 Specification and Verification II In the context of the specification and verification of hardware, explain the key ideas of each of the following: (a) binary decision diagrams (b) temporal logic (c) model checking (d) higher-order predicates [5 marks each] 9 [TURN OVER CST.97.8.10 14 Numerical Analysis II Define the Chebyshev polynomial Tk(x). Evaluate T4( 1 2 ) using the formula Tk+1(x) = 2xTk(x) Tk1(x). What is the leading coefficient of Tk(x)? [4 marks] The best L approximation to f(x) C[1, 1] by a polynomial pn1(x) of degree n 1 has the property that max x[1,1] |e(x)| is attained at n + 1 distinct points 1 6 0 < 1 < . . . < n 6 1 such that e(j ) = e(j1) for j = 1, 2, . . . n. Let f(x) = x 2 . Show, by means of a clearly labelled sketch graph, that the best polynomial approximation of degree 1 is a constant. [3 marks] Now suppose f(x) = x

Describe the MUTEX type and the LOCK..DO..END construction in Modula-3 for restricting concurrent access to critical regions. Illustrate your answer with an example. [6 marks] Show how the LOCK..DO..END construction is expanded by the compiler into calls to the Thread library and some exception handling. [4 marks] The built-in facilities for restricting concurrency in Modula-3 allow only one thread at a time to be executing within the critical region. A different approach is to distinguish shared and exclusive access to a critical region; any number of readers may share access at the same time but only one writer may acquire exclusive access, also excluding any readers while it does so. Define a MultiMutex type and sketch suitable library procedures to implement such a scheme. Common Lisp Consider trees that have two kinds of nodes. A node is either a leaf, labelled by a number, or a branch, and has one or more subtrees. For example: 3 9 1 8 7 2 5 One imagines that the edges from each branch node are numbered from left to right starting from 0. A list of these numbers thus designates the path from the root to a node. In the tree shown above, the path (2 1 1) designates the path to the node labelled 2. (a) Describe a good representation for such trees in Lisp. [3 marks] (b) Write a Lisp function getnode such that (getnode path tree) returns the node of tree designated by path, assuming that the tree contains such a node. [5 marks] (c) Write a Lisp function maxpath such that (maxpath tree) returns the maximum of the leaf nodes in the tree, together with the path to that node. For the tree shown above, maxpath should return 9 as the maximum and (0 1) as the path. [12 marks] 2 CST.93.3.3 3 Foundations of Logic Programming Consider the following set of clauses, where x is a variable and b is a Skolem constant: {P(x), Q(x), P(f(x))} (1) {P(x), Q(x)} (2) {P(b)} (3) {P(f(f(f(f(x)))))} (4) (a) How many resolution steps are required to derive the empty clause from these clauses? Justify your answer clearly. [5 marks] (b) Prolog uses resolution in a restricted form. How many Prolog-style resolution steps are required to derive the empty clause, taking (4) as the goal clause and (1)-(3) as program clauses? Justify your answer clearly. [5 marks] (c) How do a resolution theorem-prover and a Prolog system differ in their implementation of resolution?