Write an alternative definition that is tail-recursive (iterative) and makes use of accumulator variables. [10 marks] Explain why your alternative definition executes more efficiently. [3 marks] 1 [TURN OVER CST.94.11.2 2 Programming Language Compilation Carefully describe how to construct the precedence matrix for a given grammar, illustrating your answer by investigating whether the following is a precedence grammar. S -> a P Q b | c Q P d P -> X Q -> Y X -> p | X x Y Y -> q | y Y z [10 marks] Explain why replacing the productions S -> a P Q b | c Q P d by S -> a X Y b | c Y X d would introduce conflicts in the precedence matrix. [2 marks] Give a detailed description of a parsing algorithm that uses a precedence matrix. [8 marks] 3 Formal Languages and Automata Explain what is meant by a context-free language. Show that the union of two context-free languages (over the same alphabet ) is again context-free. Consider the language L over the alphabet {a, b, c} consisting of all strings of the form a ` b mc n, where `, m, n > 0 and either ` = m or m = n. Is L context-free? Is it a regular language? Justify your answers, stating carefully any well-known results that you use. [10 marks] 2 CST.94.11.3 4 Operating System Functions Describe the use of a table of pointers and a table of extents to store the list of disc blocks which compose a file. Pay particular attention to how such data structures can be designed to enable the efficient support of very large files, and give estimates of their performance for finding the location of a block chosen at random. [14 marks] Describe how such data structures would be used in the implementation of a log-structured file system with consideration of the impact of garbage collection. Study For the UNIX operating system, define (a) process [2 marks] (b) the execution environment of a process [3 marks] (c) the fork system call [3 marks] Explain how a command line of the form given below is implemented: command & [9 marks] Outline the essential difference in the implementation of command lines of the form given below: command1 & command2 command1 | command2 [3 marks] 6 Data Structures and Algorithms Give an algorithm which selects the median value from an array of n values explaining how the possible execution time depends on n. (You should clarify the word "possible".) [10 marks] Describe two tests. The first should determine whether two line segments intersect. The second should determine whether a given (half-infinite) straight line from a point (x, y) in the direction (u, v) [thus the points on the line are (x + u, y + v) for  > 0] intersects a given polygon other than at a vertex. 

The IT industry is presently interested in minimising the power consumption associated with technology. (a) Explain what is meant by the term energy-proportional computing in relation to server farms and show how it might be achieved. (b) Minimising the power consumption of desktop and mobile devices has traditionally been done by adapting system components such as the CPU to support multiple power states. An alternative is to incorporate two or more chips designed to give the same result but with different power/performance characteristics and to switch between them. For example, a system may switch between a high power and a low power CPU. Compare and contrast these two approaches. (c) Engineering for energy efficiency is a common task for mobile computing devices such as laptops. By considering the typical work load profiles of laptops and servers, and the environments in which they operate, discuss whether the same solutions developed for laptops are likely to be applicable to servers. 

Describe briefly the facilities provided in Java for synchronising concurrent threads. An alternative scheme would be to model the system used in some shops where a machine issues numbered tickets to customers, and customers are served in numeric order. A ticket machine holds an integer, initially zero, and has a single atomic operation: turn() increments the integer and returns its previous value A scheduler also holds an integer, initially zero, and has two atomic operations: next() increments the integer count queue(value) suspends the calling thread until the count is at least as large as the value given as an argument Given a ticket machine, m, and a scheduler, s, a critical region could then be coded as follows: number = m.turn(); s.queue(number); . . protected code . s.next(); Write Java classes TicketMachine, with a turn method, and Scheduler, with next and queue methods. [8 marks] Show how a synchronised buffer holding a single value could be implemented using this new scheme. 3 [TURN OVER CST.98.4.4 4 Compiler Construction Sketch parsers based on (a) recursive descent, and [8 marks] (b) a table-driven method of your choice (e.g. SLR(1)) [12 marks] suitable for parsing the following grammar: S -> E eof E -> E + T | E - T | T T -> P ^ T | P P -> ( E ) | n with S as the start symbol. The table-driven parser should include the associated algorithm which interprets the table. The parsers do not need to produce a parse tree, merely to report whether the input string is generated by the above grammar. You may assume there is a routine lex() which when called places the next symbol (+, -, ^, (, ), n, eof) in variable token. 5 Data Structures and Algorithms Describe and justify Dijkstra's algorithm for finding the shortest path between two vertices in a directed graph with non-negative lengths associated with its edges. [8 marks] For the case where the nodes represent towns and the costs Cuv represent distances by road, Hart, Nilsson & Raphael proposed a variation where the next node to be considered is based on minimising D(a) + H(a, destination) instead of the usual D(a). H(u, v) is a heuristic function which here should be taken as some constant (k, say) multiplied by the Euclidean distance between towns u and v. Explain what benefits such a modification might bring and investigate how the correctness and speed of the modified algorithm changes with the value of k. Can such a variation help in finding the shortest routes to all nodes from a given starting node? Justify your answer. [12 marks] 4 CST.98.4.5 6 Computer Design Briefly describe the differences between a memory bus, an I/O bus and a device interface on a typical PC, with emphasis on latency and bandwidth characteristics. [8 marks] What is the difference between serial and parallel data transmission? [2 marks] The physical layer for Universal Serial Bus (USB) is simpler and yet faster than old fashioned RS232. What has made this possible and economic? [5 marks] Why is it that you can "plug-and-play" with USB devices but you cannot easily "plug-and-play" with RS232 devices? [5 marks]

You have been asked to design a programming environment for use by teachers and school children in rural India, that will run on a mobile phone. (a) Using the Cognitive Dimensions of Notations, describe four different usability issues that are likely to arise specifically when a user is creating and modifying programs on a mobile phone. [2 marks each] (b) Describe techniques that you would use to research the requirements of the teachers and children. [4 marks] (c) What factors are likely to be important in assessing whether the environment will be of value to school children? How would you measure and evaluate those factors? [4 marks] (d) What factors are likely to be important in assessing whether the environment will be of value to teachers? How would you measure and evaluate those factors? [4 marks] 9 (TURN OVER) CST.2010.7.10 11 Information Theory and Coding (a) Let X and Y be two discrete random variables whose respective sets of possible outcomes {x} and {y} are described by probability distributions p(x) and p(y), and by a joint probability distribution p(x, y). (i) Give an expression for the mutual information I(X; Y ) between X and Y , using only the probability distributions p(x), p(y), and p(x, y). [2 marks] (ii) In case X and Y are independent random variables, what becomes of their mutual information, and why? [1 mark] (iii) Let the marginal entropy of random variable X be H(X), and suppose that the two random variables X and Y are perfectly correlated with each other. In that case, prove that I(X; Y ) = H(X). [2 marks] (iv) What is I(X; X), the mutual information of a random variable with itself, in terms of H(X)? [1 mark] (b) 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. [3 marks] (c) An invertible transform generates projection coefficients by integrating the product of a signal onto each of a family of functions. In a reverse process, expansion coefficients can be used on those same functions to reproduce the signal. If the functions in question happen to form an orthonormal set, what is the consequence for the projection coefficients and the expansion coefficients? What penalty must be paid in the absence of orthogonality? Name one such penalised transform. [3 marks] (d) In the Information Diagram (a plane whose axes are time and frequency), why does the Gabor-Heisenberg-Weyl Uncertainty Principle imply that information is quantised even in continuous signals - i.e., that a signal's information content consists of a countable, limited number of independent quanta? [3 marks] (e) Define the Kolmogorov algorithmic complexity K of a string of data. For a string of length N bits, how large might its Minimal Description Length be, and why? Comment on how, or whether, you can know that you have truly determined the Minimal Description Length for a set of data. Give a reasonable estimate of the Kolmogorov complexity K of a fractal, and explain why it is reasonable. [5 marks] 10 CST.2010.7.11 12 Optimising Compilers A new programming language follows an "evaluate only on need" strategy. The consequence is, for example, that in a program fragment int x = SomeExpression; if (SomeBoolean) print x; if (x == 0) x = SomeOtherExpression; the given (potentially complicated) expression is not evaluated on the line that declares x, but only gets evaluated if and when x is used, as in the print statement on line 2. On line 3 the value of x is certainly needed, so if the expression had not been evaluated earlier it must be there. Optimising compilation normally improves performance of compiled code based on transformations that are "safe" in some sense. Propose forms of analysis and hence optimisation relevant in this case in the circumstances: (a) It is safe but undesirable to evaluate an expression even if its value will not subsequently be used, but it must not be evaluated a second time. [8 marks] (b) It is safe to evaluate an expression repeatedly if is evaluated at all, but if the program would not use the value it must not be computed at all. [7 marks] (c) Extra executable logic has to be put in the program to ensure that each expression is evaluated exactly once if its value is needed, but not at all otherwise. It is desirable to minimise the amount of this extra logic, preserving semantics exactly. [5 marks] You need only consider the case of optimisation of a single procedure at a time. (a) (i) Explain the collision detection mechanism applied in standard wired medium access control associated with CSMA and indicate why this might be unsuitable for wireless networks. [2 marks] (ii) Describe how CSMA/CA (Collision Avoidance) works and explain its limitations. [2 marks] (iii) Illustrate how MACAW works and indicate its limitations on the exposed terminal problem through an example. [3 marks] (iv) Would the deployment of MACAW be needed in an installation of a MAC protocol for a single base station that communicates with some mobile terminals? Why? [3 marks] (b) You are called upon, as expert, to design and deploy a wireless sensor network to monitor environmental factors in a 500 m2 area within a forest. (i) Describe the network architecture you would deploy to collect sensed data in the forest. [2 marks] (ii) Briefly illustrate two different MAC layer protocols for sensor networks and then indicate which one you would employ for your network and why. [4 marks] (iii) Explain the salient characteristics of Directed Diffusion (DD). Describe the process through which DD is able to reconfigure when sensor nodes fail in the network. [4 marks] 4 CST.2010.7.5 4 Artificial Intelligence II Professor Elbow-Patch is not the man he used to be, and in particular has a tendency to fall over for no apparent reason. This problem is made worse if he has drunk port with his dinner. He almost always drinks port on a Sunday, and if he drinks on any given day he is unlikelyfor the sake of his long-suffering liverto drink port on the following day. However, if he does not drink on a given day then he is very likely to succumb to temptation on the following day. The probability that he falls over after drinking is Pr(fall|drank) = 0.7. The probability that he falls over when he has not drunk is Pr(fall|drank) = 0.1. He drinks on a Sunday with probability 0.9. If he has not drunk on a given day then the probability that he drinks the following day is Pr(drink today|drank yesterday) = 0.8. If he has drunk on a given day then the probability that he drinks the following day is Pr(drink today|drank yesterday) = 0.1. (a) Explain how this problem can be represented as a hidden Markov model. What assumptions are required? [4 marks] (b) Denoting observations at time i by Ei and states at time i by Si give a derivation of the filtering algorithm for computing Pr(St|E1, . . . , Et). [8 marks] (c) You observe the Professor on Sunday, Monday and Tuesday and notice that he does not fall over at all. Use the filtering algorithm to compute the probability that he drank port on Tuesday. [8 marks] 5 Bioinformatics (a) Discuss the space-time complexity of dynamic programming algorithms in sequence alignment. [7 marks] (b) Discuss with one example how to score a multiple sequence alignment. [5 marks] (c) Describe the use of principal component analysis in microarray data analysis.

(a) Explain, with prose and no more than 15 lines of pseudocode, the "Jarvis's march" algorithm for finding the convex hull of a set of points. Marks awarded for: clarity of explanation, legibility of pseudocode, correctness of algorithm. [5 marks] (b) Consider the following claim: "The cross-product trick can be used as a plug-in substitution for the comparison operation between two arguments that gives a three-way result (namely <, > or =). Therefore, given an arbitrary set of 2D vectors all starting from the origin, I can sort them in order of increasing polar angle, from 0 to 2, without computing any angles, merely by applying a standard sort algorithm with the comparison operation replaced by the crossproduct trick". (i) Explain the "cross-product trick". [3 marks] (ii) Prove the correctness of the above claim or refute it with a clearly explained graphical or numerical counterexample. [7 marks] (c) Traditionally, Jarvis's march handles the left side and the right side of the hull separately. Clearly explain why a single pass would not work as desired and then describe a variant implementation to handle the problem in one pass, highlighting its advantages and disadvantages. [Hint: see part (b)(ii).] [5 marks] 3 (TURN OVER) CST.2011.3.4 3 Programming in C and C++ In this question, where appropriate, you may use a short fragment of code to complement your explanation. (a) What is the difference between declaration and definition? (b) Describe the layout of the memory components: Dynamic Memory Allocation, Data Segment, Code Segment and Stack. You may use an illustration as part of your explanation. (c) Using an example, explain what stack unwinding is in C++. (d) How may I use template meta programming to inline recursive functions? (e) Why did the designers of the C++ language decide to make an empty class 1 byte in length? [4 marks each] 4 Compiler Construction (a) In a stack-based runtime system, what problem does the static link method attempt to solve, and how does it work? [4 marks] (b) Can static linking be used to implement a language with first-class functions? If yes, then explain how. If no, give an example and explain how static linking fails. [6 marks] (c) Explain how exceptions (ML-like raise and handle) could be implemented with a stack-oriented machine. [5 marks] (d) A program may evaluate to an exception that has been raised all the way to the top-level and never handled. Discuss how you might modify your implementation in part (c) to dump debugging information when such toplevel exceptions are raised. The debugging information should include some description of the state of the computation just before the top-level exception was raised. [5 marks] 4 CST.2011.3.5 5 Compiler Construction Consider a simple grammar for arithmetic expressions: E ::= n | x | E | E + E | ( E ) with n ranging over integer constants and x ranging over variables. We want to compile expressions to code for a simple stack-based machine with the following instruction set. instruction meaning pushvar k push the value of the k-th variable on top of stack push n push n on top of stack add replace the top two stack items with their sum neg replace the top stack item with its negation For this problem, we will not worry about how variables are bound to values nor how abstract syntax trees are produced. (a) How will your compiler generate code from expressions of the form E? [4 marks] (b) How will your compiler generate code from expressions of the form E1 + E2? [4 marks] (c) What code will your compiler generate for the expression -(-x + (17 + y))? [4 marks] (d) Suppose we now want to extend the language of integer expressions with multiplication E ::= | E E but we cannot extend the machine with an instruction for multiplication. Can you implement this extended language directly with the machine instruction set presented above? If not, suggest a minimal extension to the instruction set that allows for the implementation of multiplication using the addition from the instruction set. Explain the semantics of your extensions and how you would use them to implement multiplication. [8 marks] 5 (TURN OVER) CST.2011.3.6 6 Concepts in Programming Languages (a) Give one difference and one similarity between the programming languages: (i) Algol and SIMULA [2 marks] (ii) LISP and Smalltalk [2 marks] (b) What is the type of the expression fn f => fn x => f(f(x)) inferred by the SML interpreter? Explain your answer. [6 marks] (c) Give an example in the SML Modules language of two distinct signatures, say IN and OUT, and of a functor that takes structures matching IN to produce structures matching OUT. [6 marks] (d) Comment on the mechanism for parameter-passing in the programming language Scala. [4 marks] You may wish to consider the following two code samples. def whileLoop( cond: => Boolean )( comm: => Unit ) { if( cond ) comm; whileLoop( cond )( comm ) } def qsort[T]( xs: Array[T] )( implicit o: Ord[T] ): Array[T] = if( xs.length <= 1 ) xs else { val pivot = xs( xs.length/2 ) Array.concat ( qsort( xs filter (x => x.lt(x,pivot)) ) , xs filter (x => x == pivot ) , qsort( xs filter (x => x.lt(pivot,x)) ) ) } 6 CST.2011.3.7 7 Further Java In this question you will need to fill in missing parts of a Java program. You may ignore any exception handling and will not be penalised for minor syntactic errors. You are provided with a class Eval: public class Eval { public static int f(Record r) { ... } } (a) Add another method Integer maxf(Iterator it) to the class Eval. Your method should return the maximum value computed by f for every Record returned by the iterator or null if there are no records available. The relevant portion of the Iterator interface is as follows: interface Iterator { // return true if there are more values available public boolean hasNext(); // return the available value and advance to the next one public T next(); } [5 marks] (b) Complete the methods run() and join() in the following abstract class. You may add additional fields or methods if you wish. abstract class Joinable implements Runnable { abstract void exec(); final public void run() { // ... call the exec() method ... } void join() throws InterruptedException { // block the calling thread until exec() completes in run() } } [7 marks] (c) Provide a method Integer parmaxf(Iterator it, int n) which is functionally equivalent to Eval.maxf, except that it should create n parallel threads of execution to speed up the calculation of the result. You may assume that Iterator is thread-safe. You may find it helpful to subclass the Joinable class

Java program to read 2D matrix of type integer, with size 6*6, and display the diagonal matrix. Write java program to read two integer and swap the values using third variable. Java program to read a full names (first and last together) from a text file and print the name in the' last, first' Write java program to read a last name. Print the number of characters in the name and also the number of vowels in the name.

Explain the difference between uninformed and informed search. List two examples of each type of algorithm. [2 marks] (b) In the context of planning, describe what a heuristic is and what it means for it to be admissible. List two examples of typical heuristic functions. [Hint: consider the problem in part (d) below.] [2 marks] (c) Explain what A* search is, including the advantages and disadvantages with respect to its theoretical properties. [3 marks] (d) Draw a search tree for the 8-puzzle problem up to depth 4 (start state is depth 0) using the A* algorithm (omit repeated states) with the evaluation function f(n) = p(n) + h(n), where p(n) is the number of steps from the start state (start state is step 0) and h(n) is the number of misplaced tiles. Note that the actions for sliding tiles should be used in this order: right, left, up and down. Write the values of f and of its components p and h under each state. You may use an abbreviated notation indicating only the tiles that change. [10 marks] Start state Goal state 1 2 3 1 2 3 4 8 5 4 5 6 7 6 7 8 (e) Briefly explain IDA* search and its advantages and disadvantages. What happens when using IDA* in the search problem in part (d) if the IDA* limit is 3? What happens if the limit is 4 (in terms of number of states)? [3 marks]