Describe an algorithm to generate G2 from G1. [12 marks] How could this algorithm be used to generate the transitive closure of a graph given its adjacency matrix? [5 marks] What is the cost of this transitive closure algorithm in terms of n and m, where m is the maximum path length in the transitive closure? [3 marks] 9 Graphics II When scan-converting items for display, a Z-buffer is sometimes used to avoid some sorting. Outline its operation and limitations. [12 marks] The use of an A-buffer will improve matters. Explain why. [8 marks] 4 CST.93.4.5 10 Numerical Analysis I What is meant by the term loss of significance? What is the essential difference between the terms condition andd stability in numerical analysis? Define the term machine epsilon and explain why it is an important parameter. [6 marks] Use the recurrence formula cos[(k + 1)] = 2 cos cos[k] cos[(k 1)] with starting values cos 0 = 1, cos = 1 2 + to evaluate cos 2 and show that loss of significance occurs. [4 marks] Evaluate cos 3 and cos 4, ignoring terms O( 3 ). On this evidence, comment on the stability of the formula.

) For the bubblesort algorithm, state its best-case complexity and describe, for any given input of arbitrary size n, one permutation that would trigger this best-case behaviour. Then give the corresponding permutation of [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]. Then repeat the above for the worst case: state the complexity, saying when it is achieved, and exhibit as a concrete example a permutation of the 10 numbers given. [4 marks] (b) Repeat Part (a) for the heapsort algorithm. [4 marks] (c) Repeat Part (a) for the basic quicksort algorithm, where the pivot is simply chosen as the last element in the range. [4 marks] (d) Write clear and efficient pseudocode to eliminate all duplicates from a linked list of n elements, without changing the order of the remaining elements. Then derive and justify its complexity. [4 marks] (e) [Hint: The notation, like the notation, is typically used to describe the asymptotic behaviour of a worst-case cost function f(n). When we say, by extension, that a certain task has a complexity bound of (g(n)), we mean that this bound applies to the worst-case cost function of every possible algorithm that could solve that task.] Give a formula for f(n) (g(n)), in a format similar to that of the Reminder above, and briefly explain it. Then derive, with a clear justification, a tight complexity bound for the task of eliminating all duplicates from a linked list of n elements. [4 marks] 9 (TURN OVER) CST0.2020.1.10 9 Algorithms We are given a directed graph g = (V, E). A vertex v V is said to be an origin if for any other vertex w V there is a directed path from v to w. (a) Consider the dfs recurse(g,s) algorithm as described in lecture notes. Show carefully that, once it terminates, if it has visited a vertex v then it has also visited all vertices reachable from v. [4 marks] (b) Suppose g has an origin. Give an algorithm that returns an origin, and which has O(V + E) running time. [Hint: Consider dfs recurse all(g). What happens after it visits an origin?] [5 marks] (c) Suppose g has an origin. Prove that the vertex returned by your algorithm in part (b) is indeed an origin. [6 marks] (d) Give an algorithm that returns all origins, and which has O(V + E) running time. If the graph has no origins, your algorithm should return an empty set. Explain briefly why your algorithm is correct. [5 marks] 10 CST0.2020.1.11 10 Algorithms This question concerns unbalanced binary search trees. In some scenarios, most searches are for a small interval in the key space. For example, if we are searching a social media feed for posts keyed by timestamp, perhaps 90% of searches might be for the newest 5% of posts. (a) Explain why, in a balanced binary search tree with N items, the worst-case cost of searching for an item is (log N). [1 mark] (b) Define amortized cost. [2 marks] (c) Consider an unbalanced binary search tree with N items, where the root holds a dummy key, the left subtree holds (1 )N items, the right subtree holds N items, and where each subtree is balanced. Call this an -BALANCED tree. Suppose there are m searches, (1 )m for items on the left and m for items on the right. Find the amortized worst-case cost of a search. For = 5% and = 90%, would you prefer -BALANCED or a fully balanced tree? [5 marks] (d) Describe the weighted union heuristic and the path compression heuristic, for the Disjoint Set data structure. Explain what is meant by a rotation of a binary search tree. [6 marks] (e) We speculate that for real-world search frequencies it might be useful to have an binary search tree that is unbalanced not just at the root but also at other levels. We would also like the data structure to adjust its shape automatically, as searches occur.

Define a purely functional alternative spotter that calculates the next stree in sequence, using only the input arguments to the function to calculate the return value. Write down an example application of this function with the input arguments and the expected output result.(Hint: you may need to pass in the complete sequence as one of the arguments.) [5 marks] 2 CST0.2020.1.3 2 Foundations of Computer Science In this exercise, we will develop a game engine to play a simplified version of the game of Mastermind. In simplified Mastermind, player A selects a list of n colours among 3 possible colours: Red, Green and Blue (e.g., [Red; Red; Green; Blue] if n = 4). Player B has to guess player A's list of colours by proposing lists of colours in sequence until she finds the list proposed by player A. Every time player B proposes a list of colours, she gets feedback in the form of a number x. (x is the number of colours that are in the correct position). For example, if player A's list is [Red; Red; Green; Blue] and player B guessed [Red; Green; Green; Red], then x = 2 (the first Red and second Green are at the right positions). Note that x n. (a) Define a type colour to represent a colour. [2 marks] (b) Given two colour lists, write a function feedback that returns x. The first argument a is the list of player A, and the second argument b is a list of player B. Raise a SizeMismatch exception if the lengths of both lists do not match. You may need to introduce a helper function. [4 marks] (c) Using currying, define a test function that takes a list proposed by player B and returns x. This function should assume that player A's list is [Blue; Green; Red]. [2 marks] (d) What is the type of test in Part (c)? [2 marks] (e) Write a function generate lists that generates all possible colour lists of a given length n. The function takes a single argument n. You may use the concatenation operation @ and List.map function. Tip: generate 2 should output 32 = 9 lists. [6 marks] (f ) Given a colour list of player B and a feedback x, write a function valid lists that takes two arguments b and x and returns all possible lists that player A could have chosen (such that they match the feedback given to player B). You may use generate lists, feedback, List.length and/or List.filter. [4 marks] 3 (TURN OVER) CST0.2020.1.4 SECTION B 3 Object-Oriented Programming You have been asked to implement a user-interface component ButtonCanvas which is both a button that can be clicked by the user and a canvas which the user can draw on. Your existing code contains a Button class and a Canvas class. Both of these extend GuiComponent. (a) ButtonCanvas could be built using multiple inheritance. What does this mean in this context? [2 marks] (b) Give two reasons why this might be desirable. [2 marks] (c) Give two complexities that arise in this case. [2 marks] (d) Java interfaces originally contained only abstract methods and static final fields. How did this restriction avoid the complexities of extending multiple classes? [3 marks] (e) Draw a UML diagram for building ButtonCanvas using abstract interfaces rather than multiple inheritance. Explain how your design attempts to preserve the desirable properties arising from multiple inheritance. You do not need to recall the exact UML specification, instead you may provide a key explaining your notation. [9 marks] (f ) Recent versions of Java added default methods to interfaces. What is the impact of this with respect to multiple inheritance?

Explain how Java's implementation of generics precludes substituting T with a primitive type. [2 marks] (e) You are asked to redesign the standard library to incorporate an immutable list. Explain the relative merits of: (i) MutableList being a subtype of ImmutableList [2 marks] (ii) ImmutableList being a subtype of MutableList [2 marks] (iii) ImmutableList and MutableList having no common supertype [2 marks] (iv) ImmutableList and MutableList both subtyping CommonList [2 marks] 5 5 Introduction to Probability (a) You are looking forward to the European Cup 2020. The tournament is going to last for 30 days. Each day during the tournament, you want to invite all of your 100 classmates to your house. But people might be busy on any given day, so you expect each classmate to come with probability 0.03 on each day, and they show up independently of one another. Let X denote the number of classmates that show up on any given day. Note: In parts (ii), (iii) and (iv) you do not have to compute explicit numerical values. (i) Give the exact and approximate distributions of X along with parameters. Explain why the approximation is valid. [3 marks] (ii) What is the approximate probability that between 2 and 4 classmates, inclusive, show up on any given day? [3 marks] (iii) What is the exact probability that at least 2 classmates show up on any given day? [3 marks] (iv) What is the probability that there will be more than 27 days where at least 2 classmates show up? [3 marks] (b) Suppose that each classmate is asked to arrive at 8pm, but the actual arrival time differs in minutes by a continuous uniform distribution [, +], where is an unknown parameter. Your data set Y1, Y2, . . . , Yk is a realisation of independent random samples from that distribution, for some integer k 1. (i) Show that T = 3 k (Y 2 1 + Y 2 2 + + Y 2 k ) is an unbiased estimator for 2 . [3 marks] (ii) Is T also an unbiased estimator for ? [1 mark] (iii) Justify your answer in (b)(ii). [4 marks] 6 CST0.2020.1.7 6 Introduction to Probability (a) Give the probability mass function of each of the three distributions: (i) Poisson distribution, [2 marks] (ii) Bernoulli distribution, [2 marks] (iii) Binomial distribution. [2 marks] (b) The football association has asked you to analyse the England team football matches from previous big tournaments. For each of the three situations below, choose a suitable distribution and compute its expectation and variance. Note: In Part (b)(ii) you do not have to compute explicit numerical values. (i) You analyse 2000 penalty kicks from the last 10 years of big tournaments. It turns out that 1200 of those 2000 penalty kicks were goals. A penalty kick is chosen at random. Let X be a success if a goal is scored. [2 marks] (ii) Consider again the setting from (b)(i). If you pick 50 penalty kicks without replacement, let Y be the number of missed goals out of that sample. [2 marks] (iii) Taking into account all games from the last 10 years of big tournaments, the England football team scored an average of 1 goal every 30 minutes. Let Z be the number of scored goals during a match of 90 minutes.