An investor interested in speculating on volatility in the stock price is considering two investment strategies. The first is a 40-strike straddle. The second is a strangle consisting of a 35-strike put and a 45-strike call. Determine the range of stock prices in 3 months for which the strangle outperforms the straddle. The current price of a stock is 200, and the continuously compounded risk-free interest rate is 4%. A dividend will be paid every quarter for the next 3 years, with the first dividend occurring 3 months from now. The amount of the first dividend is 1.50, but each subsequent dividend will be 1% higher than the one previously paid. Calculate the fair price of a 3-year forward contract on this stock.

(a) A programmer plans to replace single-precision floating-point arithmetic in a subroutine with a fixed-point implementation that is guaranteed to have at least the same range and precision. Roughly how many bits must the fixed-point representation have? okayThe designers of a new computer architecture provide an instruction that uses the fixed-point implementation of Part (a) to sum long lists of single-precision floating-point numbers. This implements the rounding and re-normalisation only once at the end of the operation. What are the benefits of such an instruction compared with folding the standard two-argument addition operator over the list? [4 marks] (c) A tri-diagonal square matrix has all entries zero except for the leading diagonal and the two diagonals on either side of the leading diagonal. (i) What is the execution cost, in terms of the number of operations, of Gaussian Elimination without pivoting, both for 'school method' and for L/U decomposition? [3 marks] (ii) Without any pivoting, the L/U decomposition of a tri-diagonal matrix results in L having ones on its leading diagonal and another partial diagonal of non-zero coefficients and U also being largely all zeros. Write out the equations or pseudocode that determine L and U. What is the cost of solving a tri-diagonal set of simultaneous equations? [5 marks] (iii) What happens to the tri-diagonal structure when pivoting is used? ] 8 CST0.2018.1.9 SECTION D 7 Algorithms This question considers sorting arrays of numbers. (a) Mergesort can be implemented as a conventional two-way mergesort or a three-way mergesort. The latter splits the input into three and applies three-way mergesort recursively to each segment. (i) Derive an expression for the worst-case number of comparisons needed to merge two sorted arrays of length n 2 . [2 marks] (ii) Derive an expression for the worst-case number of comparisons needed to merge three sorted arrays of length n 3 . Consider merging three arrays at once as well as merging in pairs. [5 marks] (iii) Using your answers for Parts (a)(i) and (a)(ii) and solving suitable recurrence relations, find expressions for the total number of comparisons needed for two-way and three-way mergesort. [6 marks] (iv) Assuming comparisons to be the dominant cost, would you expect two-way or three-way mergesort to perform faster on an arbitrary array? [2 marks] (b) Consider a large dataset of numbers between 0.0 and 1.0 drawn from some known non-uniform distribution. Describe a sorting algorithm that would be expected to perform better than the above mergesort on this data. What complexity would your algorithm have in terms of space and time in the worst and average cases? [5 marks] 9 (TURN OVER) CST0.2018.1.10 8 Algorithms A 2-3 tree is analogous to a 2-3-4 tree but has only 2-nodes and 3-nodes. (a) Show in detail the steps to build a 2-3 tree from the sequence {7,3,9,8,11,10}. Highlight any procedural differences to building a 2-3-4 tree. [7 marks] (b) A red-black tree can be based on a 2-3 tree. An example red violation for such a structure is sketched below, with red nodes represented using unfilled circles. Sketch examples of the remaining red-violation cases, providing example values within the nodes. For each case, sketch its resolution, assuming each case occurs as a sub-tree of a larger tree. [5 marks] (c) Consider restricting the 2-3 variant of a red-black tree so that red nodes may only lie on the left of a parent. (i) Discuss the effect this has on the search and insert performance. How does it impact the implementation? [5 marks] (ii) How does it affect the worst-case costs of finding the minimum and maximum values in the tree? [3 marks] 10 CST0.2018.1.11 9 Algorithms The chaining collision-resolution scheme for hash tables uses an array where each element is a linked list. (a) For a hash table that uses chaining to resolve collisions with an array of length m and n keys inserted, the average asymptotic complexity for search and insert is O(1 + n m ). (i) Explain why search and insert are considered to be O(1) and not O(n) in practice. [2 marks] (ii) Give the worst-case complexities for search and insert. State the factors that determine the performance observed in practice. [5 marks] (b) An alternative hash-table implementation replaces the linked lists in each slot with red-black trees. Discuss the advantages and disadvantages of this change. [4 marks] (c) The linked lists may also be replaced by dynamically sized arrays. When full, an array is expanded by a factor of k. (i) Derive a potential to compute the amortised cost of adding an element to such an array using the potential method. On inserting an element that triggers an expansion, your potential should be zero just after the expansion but before the insertion of the new element. [3 marks] (ii) Use your potential to compute the amortised cost of adding an element to the array.

1 Foundations of Computer Science (a) Sets containing integers can be represented as int list values. Consider two such representations called unordered and ordered. In the former elements can appear in any order; in the latter elements are required to be in ascending order. In both representations elements must not be repeated. (i) Using the unordered representation give ML functions corresponding to set intersection and set union. [3 marks] (ii) For your answers to Part (a)(i) give the associated time complexities, assuming both input sets have at most n elements. [2 marks] (iii) Now, using the ordered representation, give ML functions corresponding to set intersection and set union along with their time complexities, noting reasons for any differences in complexity compared to those for the unordered representations. [4 marks] (iv) Without giving any ML code, suggest a technique whereby set intersection for unordered can be implemented in O(n log n) time. [1 mark] (b) One often hears "in ML, all functions take exactly one argument". Explain two techniques which enable us to circumvent this rule, illustrating your answer by giving ML definitions for the standard map and a variant which "takes the same arguments in the same order". Call the variant map'

A car manufacturer uses Java software to track current vehicles being built. The UML diagram below shows an excerpt of the current software structure. You should assume the presence of other appropriate fields and methods. (a) Each car can be built to one of three trim levels: base, luxury or sport. They can also be configured with an electric or petrol engine. At various points in the manufacturing process the customer can choose to change the trim level. (i) Explain in detail why the current structure does not support this. [3 marks] (ii) Show how to refactor the structure to allow trim-level change using a standard design pattern, which you should identify. Explain how it addresses the problems you identified in Part (a)(i) and show how you would implement getTrimLevel() in Car. [5 marks] (iii) Compare and contrast your solution to Part (a)(ii) with an alternative approach that stores the current trim level as a private String field within Car. [2 marks] (b) The manufacturer decides to offer a vehicle with a hybrid engine that is both an electric engine and a petrol engine. (i) Some languages support multiple inheritance of type, method implementation and state. Identify the problems each introduces and discuss the extent to which Java supports them. [5 marks] (ii) Refactor the software structure to achieve the effect of multiple inheritance of type and method implementation for HybridEngine in Java without using default methods. Show how your solution would support an accelerate() method for HybridEngine that uses the electric engine if the battery level is above some threshold or the petrol engine otherwise. (a) Consider implementing the natural logarithm function ln(t) for floating-point numbers using the McLaurin series: ln(1 + x) = X n=1 (1)n1 x n n = x x 2 2 + x 3 3 x 4 4 + (i) List all special behaviours the natural logarithm function should have in different parts of its range and when t takes the special values NaN and . [2 marks] (ii) The function must accept a broad range of numerical values but the series only converges when the absolute value of x is less than one, |x| < 1. Describe a range-reduction procedure that pre-processes the argument and post-processes the result so that the series always acts on small values of x. [6 marks] (iii) State the two precision requirements normally expected for mathematical libraries. Considering the worst-case value(s) of x after range reduction, approximately how many terms are needed to meet one of these requirements for a single-precision implementation? Do you expect the other requirement to be met?