You are given the following information about two options, A and B: i) Option A is a one-year European put with exercise price 45. ii) Option B is a one-year American call with exercise price 55. iii) Both options are based on the same underlying asset, a stock that pays no dividends. iv) Both options go into effect at the same time and expire at t = 1. You are also given the following information about the stock price: i) The initial stock price is 50. ii) The stock price at expiration is also 50. iii) The minimum stock price (from t = 0 to t = 1) is 46. iv) The maximum stock price (from t = 0 to t = 1) is 58. Determine which of the following risk management techniques can hedge the financial risk of an oil producer arising from the price of the oil that it sells. I. Short forward position on the price of oil II. Long put option on the price of oil III. Long call option on the price of oil.

(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.

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.

(a) What is a data cache and what properties of data access does it exploit? [5 marks] (b) What is a direct mapped cache and under what conditions will it exhibit poor performance? [5 marks] (c) Under what circumstances might a word of data in main memory be simultaneously held in two separate first-level cache lines? [5 marks] (d) A translation look aside buffer is a specialised cache. What does it typically store and why is it often a factor of 1000 smaller than a data cache? [5 marks] 3 Digital Communication I (a) Define the terms circuit and packet in the context of communication systems. [5 marks] (b) What sort of guarantee does circuit switching provide? [5 marks] (c) What advantages does packet switching provide over circuit switching? [5 marks] (d) Which of frequency division multiplexing, time division multiplexing and code division multiplexing lend themselves to circuit switching? Which to packet switching? Explain why or why not in each case. [5 marks] 4 Computer Graphics and Image Processing (a) Describe the z-buffer polygon scan conversion algorithm. [10 marks] (b) In ray tracing, once we have determined where a ray strikes an object, the illumination at the intersection point can be calculated using the formula: I = Iaka + X i Iikd(Li N) +X i Iiks(Ri V) n Explain what real effect each of the three terms is trying to model and explain what each of the following symbols means, within the context of this formula: I, Ia, i, Ii , ka, kd, ks,Li , N, Ri , V, n [10 marks] 3 [TURN OVER CST.2001.13.4 5 Business Studies (a) What is meant by the terms supply curve and demand curve, and what is significant about the point where they cross? [5 marks] (b) What is meant by the terms cost curve and break-even point? Draw a diagram to show the relation between them and the demand curve. How would you attempt to establish a demand curve in practice?

A weighted binary tree can be defined using compound terms in the following way. A node of the tree is represented by the term n(V, L, R), where V stands for the value of the node, and L and R stand for the left and right branches, respectively. A terminal node has the R and L components instantiated to the null list. Given an input tree T, write a Prolog program that constructs a tree of the same shape as T, but in which the value of each node has been set to the value of the maximum value node in T. [Note: Maximum marks are available only for programs that perform this task in one recursive descent of the input tree, and which use no more than four clauses.] [20 marks] 5 [TURN OVER CST.2001.13.6 9 Databases The environmental agency is setting up an SQL database to monitor long-term trends in the climate. Data are collected from observatories of a number of different kinds. Flood risk is of particular concern. Each water authority measures river levels and rates of flow hourly at major points, and records reservoir levels daily. In addition, the agency maintains weather stations both inland and at sea. These record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind. Values of new precipitation, temperature, pressure, and wind speed and direction are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur. Maximum and minimum temperature and pressure, the total number of hours of sunshine and the total precipitation are recorded daily. Inland stations can be grouped by water authority. By default these primary data will be relegated to archive after 2 years. Selected information is retained permanently in a data warehouse. This serves two purposes. First, it holds monthly summary data consisting of the maximum (and minimum as appropriate) day value for each statistic, together with the monthly totals of sunshine and precipitation. The warehouse also keeps detailed information relating to periods of extreme weather from the relevant observatories, with one or more keywords describing the nature of the incident (flood, blizzard, hurricane etc.) and an optional comment. Write notes to assist in the design of the schema for the relational data warehouse, including any diagrams that you find helpful. Explain how your design will enable meteorologists to find relevant past records, noting any assumptions that you make about the nature of the data.

The PS index has the following characteristics: One share of the PS index currently sells for 1,000. The PS index does not pay dividends. Sam wants to lock in the ability to buy this index in one year for a price of 1,025. He can do this by buying or selling European put and call options with a strike price of 1,025. The annual effective risk-free interest rate is 5%. Determine which of the following gives the hedging strategy that will achieve Sam's objective and also gives the cost today of establishing this position. (A) Buy the put and sell the call, receive 23.81 (B) Buy the put and sell the call, spend 23.81 (C) Buy the put and sell the call, no cost (D) Buy the call and sell the put, receive 23.81 (E) Buy the call and sell the put, spend 23.81 6. The following relates to one share of XYZ stock: The current price is 100. The forward price for delivery in one year is 105. P is the expected price in one year Determine which of the following statements about P is TRUE. (A) P < 100 (B) P = 100 (C) 100 < P < 105 (D) P

A non-dividend paying stock currently sells for 100. One year from now the stock sells for 110. The continuously compounded risk-free interest rate is 6%. A trader purchases the stock in the following manner: The trader pays 100 today The trader takes possession of the stock in one year Determine which of the following describes this arrangement. (A) Outright purchase (B) Fully leveraged purchase (C) Prepaid forward contract (D) Forward contract (E) This arrangement is not possible due to arbitrage opportunities 8. Joe believes that the volatility of a stock is higher than indicated by market prices for options on that stock. He wants to speculate on that belief by buying or selling at-themoney options. Determine which of the following strategies would achieve Joe's goal. (A) Buy a strangle (B) Buy a straddle (C) Sell a straddle (D) Buy a butterfly spread (E) Sell a butterfly spread