class Queue using no other data structures than Item, Boolean, int and Stack. The amortized running time of each Queue method must be constant. (Note that you may only use the Stack as a black box: you are not allowed to access its internal implementation.) [7 marks] (iii) Using the potential method, prove that the amortized running time of all your Queue methods from part (b)(ii) is indeed constant. [5 marks] 2 CST.2009.4.3 2 Algorithms II (a) Given the following Fibonacci heap, where nodes with an asterisk are "marked", perform extractMin() on it and then decreaseKey() on the node whose key is currently 66, bringing it down to 4. Redraw the changed heap as you go along. You need only draw any significant intermediate states of the heap, adding any necessary explanations so that a reader can follow what you are doing and why. [5 marks] 5 10 32 58 30 70 51 43 40* 50 44* 66 77 (b) Fibonacci heaps are designed so that their trees never become excessively "wide and shallow". Why? Justify this design goal in detail and then explain how it is achieved. [5 marks] (c) Nothing, however, stops the trees in a Fibonacci heap from growing "tall and narrow". Prove this by describing a sequence of Fibonacci heap operations that, given an integer n, produces a Fibonacci heap made of a single tree consisting of a linear chain of n nodes (in other words, each node in the tree except for the last one is the parent of exactly one node, and each node except for the first one is the child of exactly one node). [10 marks] 3 (TURN OVER) CST.2009.4.4 3 Artificial Intelligence I (a) 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] 4 CST.2009.4.5 4 Artificial Intelligence I (a) Describe the following in the context of planning: (i) STRIPS operators; [1 mark] (ii) situation space versus plan space (point out the differences); [2 marks] (iii) partial order planning (briefly explain key features). [2 marks] (b) Consider the following partial order planning problem for creating a picture of an aquarium. The goal is to have painted background and also drawn(Fish), drawn(Crab) and drawn(Seahorse). The start state is empty(Picture). You can use the following: paint background with precondition empty(Picture) and with effects painted background and empty(Picture) draw(x) with no preconditions and with effects drawn(x) and empty(Picture)

(a) The polymorphic curried function delFirst takes two arguments, a predicate (Boolean-valued function) p and a list xs. It returns a list identical to xs except that the first element satisfying p is omitted; if no such element exists, then it raises an exception. Code this function in ML. [4 marks] (b) Use the function delFirst to express the polymorphic function delFirstElt, where delFirstElt x xs returns a list identical to xs except that it omits the first occurrence of x. [2 marks] (c) Carefully explain the polymorphic types of these two functions, paying particular attention to currying and equality. [4 marks] (d) A list ys is a permutation of another list xs if ys is obtained by rearranging the elements of xs. For example, [2,1,2,1] is a permutation of [2,2,1,1]. Code an ML function to determine whether one list is a permutation of another. [4 marks] (e) A list ys is a generalised permutation of xs if ys is obtained by rearranging the elements of xs, where one element of xs is specially treated: it may appear any number of times (including zero) in ys. For example, [1,2,1] is a generalised permutation of [1,2] but [1,2,2,1] is not because two elements (1 and 2) appear the wrong number of times in it. Code an ML function to determine whether one list is a generalised permutation of another. [6 marks] All ML code must be explained clearly. 2 CST.2009.1.3 2 Foundations of Computer Science (a) Write brief notes on top-down merge sort, contrasting it with insertion sort. State its worst-case and average-case complexity, with brief justification. (There is no need to present ML code.) [5 marks] (b) Write brief notes on preorder, inorder and postorder tree traversal. Present efficient code for one of them and state, with justification, its worst-case complexity. [5 marks] (c) The binary search tree t1 is superseded by t2 provided every (key, value) entry in t1 is also present in t2. Code an ML function to determine whether one binary search tree is superseded by another. Express its cost in terms of n1 and n2, the numbers of entries in t1 and t2, respectively. For full credit, the worst-case cost should be no worse than O(n1 + n2). [10 marks] All code must be explained clearly. You may assume that any necessary ML data structures or functions are available. 3 (TURN OVER) CST.2009.1.4 SECTION B 3 Discrete Mathematics I (a) State the structured-proof rules for implication introduction and disjunction elimination. [3 marks] (b) Give either a structured proof or a counterexample for each of the following. (i) ((P Q) (P R)) (P (Q R)) (ii) ((P Q) R) ((P R) (Q R)) [8 marks] For a set of sets A, write S A for the set {x | X A.x X}. For a non-empty set of sets A, write T A for the set {x | X A.x X}. (c) Suppose A P(X) and B P(X). Prove or give a counterexample for each of the following. (i) If S A and S B are disjoint, then A and B are disjoint. (ii) If A and B are disjoint then S A and S B are disjoint. (iii) If A and B are non-empty and X A.Y B.X Y then S A T B. [9 marks] 4 CST.2009.1.5 4 Discrete Mathematics I (a) Define what it means for a relation R A A to be: (i) irreflexive [1 mark] (ii) symmetric [1 mark] (iii) antisymmetric [1 mark] (b) Define a non-trivial irreflexive symmetric relation R over the set of natural numbers, showing why it has those properties. [3 marks] (c) If A is a finite set with n elements, how many distinct irreflexive symmetric relations over A are there? [3 marks] (d) If A is a finite set with n elements, how many distinct relations that are symmetric and antisymmetric over A are there? [3 marks] (e) Suppose R and S are irreflexive symmetric relations over A. For each of the following relations, either prove that they are irreflexive and symmetric or give a counterexample. (i) R S (ii) R; S (iii) the relation Q defined to be {(X, Y ) | X A Y A x X.y Y.(x, y) R} [8 marks] 5 (TURN OVER) CST.2009.1.6 SECTION C 5 Algorithms I (a) State the five invariants of Red-Black Trees and briefly explain the advantages and disadvantages of Red-Black Trees over Binary Search Trees. [4 marks] (b) For each of the possible types of 2-3-4-tree nodes, draw an isomorphic node cluster made of Red-Black nodes. The node clusters you produce must have the same number of keys and external links as the 2-3-4 nodes they replace and they must respect all the Red-Black tree rules when composed with other node clusters. [3 marks] (c) What are the minimum and maximum possible number of nodes of a Red- Black tree with black-height h? Justify your answer. [4 marks] (d) Explain, with clear pictures, what a "rotation" operation is, in the context of Binary Search Trees. [2 marks] (e) Give a procedure for reshaping an arbitrary n-node Binary Search Tree containing n distinct keys into any other arbitrary Binary Search Tree with the same keys. [7 marks] 6 CST.2009.1.7 6 Algorithms I (a) State the defining properties of a min-heap. Show how to convert between the tree and the (zero-based) array representation of a min-heap. [3 marks] (b) "An array sorted in ascending order is always a min-heap." True or false? If false, offer a counter-example; otherwise, prove the correctness of this statement with respect to the defining properties of a min-heap you listed in response to part (a). [3 marks] (c) The array A I E R P M S N L is not a min-heap. Why? Redraw it as a binary tree and turn it into a heap using the O(n) heapify() procedure normally used as part of heapsort. Draw the intermediate stages as you go along and add any necessary explanations so that a reader can follow what you are doing and why. [4 marks] (d) Perform extractMin() on the min-heap you produced in part (c). As before, draw the intermediate stages and add explanations as necessary. [3 marks] (e) What is the asymptotic running time of the heapsort algorithm on an array of length n that is already sorted in ascending order? Justify your answer. [3 marks] (f ) What is the asymptotic running time of the heapsort algorithm on an array of length n that is already sorted in descending order?

(a) Describe the difference between a class and an instance. Show typical examples of each as they would be represented in UML diagrams and in source code. [4 marks] (b) Explain the relationship between information hiding and loose coupling. Your explanation should mention class interfaces, visibility modifiers, and accessor methods. [6 marks] (c) Consider the design of a future student records database system for Cambridge, and in particular, a module for examination registration and grading. Use this example to illustrate some of the separate phases of a software design project, by showing outline examples of: (i) a usage scenario, (ii) a class diagram related to that scenario, (iii) a collaboration diagram related to the scenario, and (iv) the public interfaces and fields for two of the classes in these diagrams. You should not attempt to describe a complete design, but simply include enough detail to show the differences and relationships between these kinds of design model. [10 marks] 8 CST.2009.1.9 8 Programming Methods and Java (a) Consider the method sum defined in Java as public byte sum (int n) { byte result=0; for (int i=0;i

Write the start state and the finish state. Draw a partial order plan with preconditions above the operators and effects below the operators. Draw the causal links. [8 marks] (ii) Define what threats are. Comment on whether there are any in your partial order plan above, and how you would solve them. Add temporal links to your partial plan as dotted arcs. [4 marks] (iii) How many solution plans are there in your partial order plan? List all solution plans with total ordering of steps implied by your partial order plan. [3 marks] 5 Computer Graphics and Image Processing (a) Describe an algorithm that draws a Bezier cubic curve to a specified tolerance using straight lines. [7 marks] (b) Describe an algorithm for clipping a line against a rectangle. [7 marks] (c) A Bezier cubic curve could be clipped and drawn using the algorithm in part (a) to produce straight lines and the algorithm in part (b) to do the clipping. Describe a more efficient algorithm that draws a Bezier cubic curve clipped against a rectangle. [6 marks] 5 (TURN OVER) CST.2009.4.6 6 Computer Graphics and Image Processing (a) Describe the A-buffer polygon scan conversion algorithm using 44 sub-pixels for each pixel. [10 marks] (b) It is possible to represent continuous tone greyscale images using just black ink on white paper because of limitations in the human visual system. Explain how and why. [4 marks] (c) Describe an algorithm that, given a greyscale image, will produce a black and white (bi-level) image of four times the resolution in each dimension which provides a good approximation to the greyscale image. [6 marks] 7 Databases (a) Define Boyce-Codd Normal Form (BCNF). [3 marks] (b) Suppose that R(A, B) is a relational schema with two attributes, A and B. Show that this schema must be in BCNF. [6 marks] (c) Describe a procedure that can take as input any relation schema R(X) together with functional dependencies F over the attributes of the set X, and return a decomposition of the input schema where each relation is in BCNF. Make sure you argue that the procedure is correct and terminates. [8 marks] (d) Does your BCNF decomposition procedure always preserve all functional dependencies? Explain your answer. [3 marks] 6 CST.2009.4.7 8 Databases (a) Define the concept of a functional dependency. [2 marks] (b) Let R(A, B, C, D, E, F) be a database schema with functional dependencies A, B C B, C A, D D E C, F B (i) Compute the closure of {A, B}. [3 marks] (ii) Is A, B D, F a functional dependency over R? Justify your answer. [1 mark] (c) Define the concept of a multivalued dependency. [2 marks] (d) Suppose the functional dependency X Y holds on a relational schema. Does this mean that the multivalued dependency X Y holds? Justify your answer. [3 marks] (e) Define the concept of a lossless-join decomposition. [3 marks] (f ) Let R(X) be a database schema, where X is a set of attributes. Show that S(Y Z) and T(Y (X Z)) is a lossless-join decomposition of R(X) if and only if the multivalued dependency Y Z holds over R.