CST.20assign data

Extract = dataStore; endmodule (a) What would be suitable comments on the behaviour of the code at points "comment A" to "comment D"? [4 marks] (b) In the synthesised implementation, how will the reset and clock signals be connected to the D flip-flops that are used to hold the state inside the always block? [2 marks] (c) In Verilog a wire can transmit not only Boolean values 0 and 1, but also the values x and z. How is x used in simulation and what will it be converted to when synthesised to real hardware? Illustrate your answer with reference to assignments to dataStore in FIFO one. [3 marks] (d) What is the state diagram describing the empty/full status of FIFO one? Include the inputs (insert, extract) and outputs (insertComplete, extractComplete) on the arcs of the state diagram and ignore the data path. [4 marks] (e) Is it possible to insert and extract data on the same clock cycle? [1 mark] (f ) How could two instances of FIFO one be joined to produce a two-element FIFO? [4 marks] (g) For your design in part (f ), how many clock cycles of latency would there be from input to output if data were always extracted as quickly as possible? [2 marks] 2 Computer Design instruction decode and execute memory write fetch register fetch access back With reference to the pipeline above: (a) What is a control hazard and how can it be dealt with? [4 marks] (b) What are data hazards and how can they be eliminated? [4 marks] (c) A branch could be executed in either the decode or the execute stages. Assuming that branch prediction and branch delay slots are not used, how many bubbles would be introduced into the pipeline in either case? [4 marks] (d) If the memory access results in a cache miss, what happens to the pipeline? [4 marks] (e) For arithmetic operations the result is available after the execute stage. These results could be written directly to the register file during the memory access stage, but what would be the disadvantages of doing so? [4 marks] 3 (TURN OVER) CST.2007.6.4 3 Digital Communication I (a) Define the term flow control as used in communication networks. [4 marks] (b) Describe on-off flow control, window-based flow control, and flow control used in circuit switching. [9 marks] (c) Consider a channel of capacity b and delay , over which packets of size p are sent. Compare the performance of window-based flow control protocols having: (i) a window size of one packet; (ii) a window size of two packets; and (iii) a window size of one packet, but with a packet size of 2p. [7 marks] 4 CST.2007.6.5 4 Concurrent Systems and Applications (a) For each of the following tasks, give a code fragment that achieves as much of the task as is possible using the introspection API of the Java programming language and state which aspect(s) of the requirement is/are impossible in Java. (i) Given a (non-null) object reference, determine whether or not the object has a public, static method named myMethod which takes no arguments. [4 marks] (ii) Invoke the static method public foo(java.lang.Integer x) on a class definition named MyClass with argument myInt when the overloaded, static method foo(java.lang.Number x) is also defined on MyClass. [4 marks] (iii) Given an object reference to an instance of a class named Rocket, set the value of its public field numberOfEngines to the (primitive) int value 5 and make the method launch() into a synchronized method. [4 marks] (b) You are porting the JVM to a new processor that does not have a compare-and-swap (CAS) instruction but does offer test-and-clear (TAC): tac(addr) atomically reads the value stored at memory address addr, overwrites it with zero, and returns the value that was seen. Construct a Java-style re-entrant mutex using TAC. [4 marks] (c) A server daemon has an object of type Client for each currently-active connection. Instances of Client each contain an object reference to a java.lang.Socket which must be closed (by calling close()) when the Client object is garbage collected. Show, by means of Java code fragments, how Phantom References and Reference Queues can be used to invoke the close() method in a timely fashion following an instance of Client becoming unreachable. [4 marks] 5 (TURN OVER) CST.2007.6.6 SECTION B 5 Computer Graphics and Image Processing (a) Explain what a MIPmap is, how to create one, why one would want to use one, where one would be used, and how one is used. [8 marks] (b) Describe an algorithm that converts a greyscale image into a black and white image using halftoning. Assume that the black and white image has eight times the resolution of the greyscale image in each dimension. [6 marks] (c) Various types of visual artifact ("aliasing") occur if images are rendered using only one sample per pixel. (i) Describe at least three different artifacts that occur. [3 marks] (ii) Describe a straightforward method to ameliorate these artifacts. [3 marks] 6 Compiler Construction (a) Garbage Collection. (i) Explain how it is possible to "leak memory" using a reference counting garbage collector. [3 marks] (ii) Describe any technique that might be used to address this problem. [3 marks] (b) Explain in detail how we might translate code generated for a stack-only machine (such as the JVM) to a register-based machine (such as ARM). [6 marks] (c) Describe in detail how static and dynamic methods are compiled differently for object-oriented languages with single inheritance. [8 marks] 6 CST.2007.6.7 7 Concepts in Programming Languages (a) Give an overview of the LISP abstract machine (or execution model) and comment on its merits and drawbacks from the viewpoints of programming, compilation, execution, etc. [5 marks] (b) Define the following parameter-passing mechanisms: pass-by-value, pass-byreference, pass-by-value/result, and pass-by-name. Briefly comment on their merits and drawbacks. [5 marks] (c) What is aliasing in the context of programming languages? Explain the contexts in which it arises and provide examples of the phenomenon. [5 marks] (d) Consider the Simula declarations CLASS A; A CLASS B; which have the effect of producing the subtype relation B<:A, and REF(A) a; REF(B) b; Recall that Simula uses the semantically incorrect principle that if B<:A then REF(B)<:REF(A) and consider now the following Simula code PROCEDURE ASSIGNa( REF(A) x ) BEGIN x :- a END ; ASSIGNa(b); Does it statically type check? If so, will it cause a run-time type error? Justify your answers. [5 marks] 7 (TURN OVER) CST.2007.6.8 8 Databases (a) Define the notion of a functional dependency. [2 marks] (b) Consider the following "rule" for functional dependencies. if A B and B, C D, then A, C D. Either prove this rule is correct, or present a counter-example showing that the rule is false. [4 marks] (c) The union rule for functional dependencies states that if F |= X Y and F |= X Z, then F |= X Y Z (this can also be written as F |= X Y, Z). Prove this rule using only Armstrong's axioms. [4 marks] (d) Suppose that R(A, B, C) is a relational schema. Write a relational algebra query that evaluates to the empty set exactly when the functional dependency B C holds on R. [4 marks] (e) The schema R(A, B, C, D, E) has the following functional dependencies. A B, C C, D E B D E A Is D, E a candidate key for R? Explain your answer. [6 marks] SECTION C 9 Logic and Proof For each of the following formulae, state (with justification) whether it is satisfiable, valid or neither: ((P Q) R) (P (Q R)) (P Q) (R Q) (R P) (P Q R) (P Q R) h x y (P(x) Q(x, y)) x z y (Q(x, y) P(z))i x y Q(x, y) [4+7+9 marks] 8 CST.2007.6.9 10 Semantics of Programming Languages Concurrent threads can interfere with each other by accessing the same store, so their behaviour can be nondeterministic and hard to reason about. This question develops a simple sufficient condition to rule that out, showing that two threads that do not share any store locations cannot interfere with each other's behaviour. Consider the following mild variant of L1, with distinguished grammars of expressions and processes, and corresponding reduction relations and . Integers n Z Locations ` L = {l, l 0, l 1, l 2, . . .} Expressions e ::= n | skip |!` | ` := e | e1; e2 Processes p ::= e | p1 p2 Stores s, finite partial functions from L to Z (e-deref) h!`, si hn, si if ` dom(s) and s(`) = n (e-assign1) h` := n, si hskip, s + {` 7 n}i if ` dom(s) (e-assign2) he, si he 0 , s 0 i h` := e, si h` := e 0 , s 0 i (e-seq1) hskip; e2, si he2, si (e-seq2) he1, si he 0 1 , s 0 i he1; e2, si he 0 1 ; e2, s 0 i (p-thread) he, si he 0 , s 0 i he, si he 0 , s 0 i (p-par1) hp1 , si hp 0 1 , s 0 i hp1 p2 , si hp 0 1 p2 , s 0 i (p-par2) hp2 , si hp 0 2 , s 0 i hp1 p2 , si hp1 p 0 2 , s 0 i Write s ] s 0 for the union of two stores that have disjoint domain, and let loc(e) denote the set of store locations mentioned in e. (a) Give a counterexample to [One-step determinacy for processes]: If hp, si hp1 , s1i and hp, si hp2 , s2i then hp1 , s1i = hp2 , s2i. [1 mark] (b) Prove [One-step determinacy for expressions]: If he, si he1, s1i and he, si he2, s2i then he1, s1i = he2, s2i. [5 marks] (c) Assume [Irrelevant store can be added]: If he, si he1, s1i and dom(s)dom(s0) = {} then he, s]s0i he1, s1]s0i. (d) Prove [Irrelevant store can be removed]: If he, s ] s0i he1, s1i and loc(e) dom(s) then there exists s 0 such that he, si he1, s 0 i and s1 = s 0 ] s0. [8 marks] (e) Using (b), (c) and (d), prove [One-step confluence for store-disjoint threads]: If p = e1 e2, loc(e1) loc(e2) = {}, hp, si hp 0 , s 0 i, and hp, si hp 00 , s 00i, then either hp 0 , s 0 i = hp 00 , s 00i or p 000 , s 000 . hp 0 , s 0 i hp 000 , s 000i hp 00 , s 00i hp 000 , s 000i. [6 marks] 9 (TURN OVER) CST.2007.6.10 11 Foundations of Functional Programming (a) Define transformations that translate the -calculus to and from a language using only combinators and application. [8 marks] (b) Define transformations that translate the -calculus to and from continuationpassing style. [8 marks] (c) Indicate the complexity of your given transformations above in terms of size of output term as a function of size of input term. [4 marks] 12 Complexity Theory Let Bounded Factor denote the following decision problem: Given positive integers n and k, decide whether n has a proper factor that is less than k. For each of the following questions, give a detailed justification of your answer. Note that, in some cases, the answer may not be a simple "yes" or "no" but may instead be linked to open problems in complexity theory such as whether P=NP or the existence of one-way functions. In such cases, you should clearly explain the links and state what the consequences might be of both a positive and a negative answer to the question. (a) Is Bounded Factor in NP? [4 marks] (b) Is Bounded Factor in co-NP? [4 marks] (c) Is Bounded Factor NP-hard? [6 marks] (d) Is Bounded Factor in P?1 Comparative Architectures (a) Why is branch prediction so important in modern processors? [2 marks] (b) Why are saturating, two-bit counters used? [2 marks] (c) How does a local branch predictor operate? [2 marks] (d) How does a global branch predictor operate? [2 marks] (e) How may local and global branch predictors be used together? [3 marks] (f ) Give an example sequence of branches that will fail to be completely predicted with a branch history of four. [3 marks] (g) How can the compiler assist with branch prediction? [3 marks] (h) Suggest methods for jump prediction. [3 marks] 2 Digital Communication II Recent advances in consumer electronics have led to the potential demand for Home Area Networks (HANs). Given that this would include monitoring and control of the home environment, linking home entertainment (television, radio, MP3 players etc.), and communications (Voice, Data, possibly video) within the home and to and from the outside world, one can consider the relative merits of various forms of HAN. (a) What would be the distinguishing features of an IP-based HAN? [4 marks] (b) What would be the distinguishing features of a cell-switched HAN? [4 marks] (c) What are the comparative merits of the two solutions, considering the application requirements such as guaranteed throughput and jitter; the separation of control and data; the management complexity of the network; and the complexity of the interconnection systems such as switches or routers? [12 marks] 2 CST.2007.7.3 3 Security A rapidly-growing online crime is phishing, in which victims are lured by an e-mail to log on to a website that appears genuine but that actually steals their passwords. You have been hired by a bank to help them harden their online banking service against phishing attacks. (a) Explain briefly the strengths and weaknesses of the following four possible countermeasures: (i) SSL/TLS client certificates issued to each customer; [4 marks] (ii) a handheld password calculator issued to each customer; [4 marks] (iii) displaying a unique picture to each customer during the login process; [4 marks] (iv) requiring that large payments, or payments to new recipients, be authorised by telephone or SMS as well as online. [4 marks] (b) You are told that the budget will accommodate only two of the above options. Which two would you recommend, and why? [4 marks] 4 Advanced Graphics (a) A NURBS curve is defined by control points P1, P2, . . . , Pn+1 and knot vector (t1, t2, . . . , tk+(n+1)). (i) State the formul for deriving the basis functions Ni,k(t). [3 marks] (ii) Graph all seven of the linear basis functions, Ni,2(t), for the knot vector (0, 1, 2, 4, 5, 5, 5, 6, 7). [3 marks] (iii) Draw seven points, P1, P2, . . . , P7, equi-spaced around a circle and draw the linear NURBS curve defined by those points and the basis functions from part (ii). [2 marks] (iv) Derive the formula for and sketch a graph of the basis function N3,3(t) for the knot vector in part (ii). [3 marks] (b) Choose one of the Doo-Sabin, Catmull-Clark and Loop subdivision schemes. Describe your chosen scheme, including an explanation of how it works in regular regions of the mesh, how it works at and around extraordinary polygons, and how it works at and around extraordinary vertices. [9 marks] 3 (TURN OVER) CST.2007.7.4 5 Information Retrieval (a) Information retrieval systems are commonly compared against each other in large-scale evaluative conferences. Which difficulties do designers of such evaluations face? Describe three difficulties and how they could be addressed. [5 marks] (b) 11-pt avg. precision is an area-based evaluation measure which combines precision and recall. (i) Why are simpler evaluation metrics insufficient for comparative IR evaluation exercises? [3 marks] (ii) Give the formula for 11-pt avg. precision, defining all variables used. [2 marks] (iii) The following table shows the output of an information retrieval system on two queries. You can assume that there are no relevant documents in ranks lower than the top 10 ranks shown. Calculate 11-pt avg. precision for these two queries, using an appropriate interpolation method if necessary, and sketch it in a precision-recall graph. [5 marks] Rank Q1 Q2 1 X - 2 - X 3 - - 4 X X 5 X - 6 - X 7 - X 8 - - 9 - X 10 - X Output of an IR system on two queries Q1 and Q2; top 10 ranks. Crosses correspond to relevant documents, dashes to irrelevant documents. (c) Large-scale evaluations of information extraction systems use a different setup from IR evaluations, and different evaluation metrics. Describe in detail how you would organise the evaluation of information extraction systems on the task that SNOWBALL solves, i.e. the determination of pairs of company names and headquarters. Which data would you prepare, and which evaluation metrics would you use? Justify your decisions. [5 marks] 4 CST.2007.7.5 6 Specification and Verification I (a) Describe how the meaning of {T} X := Y {X=Y} differs from the meaning of {Y=y} X := Y {X=y}. [2 marks] (b) Is the total correctness specification [Y=0] X := X/Y [X=X] true? Justify your answer. [2 marks] (c) Give an expression E such that {T} X := E {X = E} is not true. [2 marks] (d) Explain how specifications containing VDM's hooked variables like ( X can be translated to specifications that do not use hooked variables. [2 marks] (e) What is the relationship between the provability of verification conditions and the provability of the specification from which they were generated? [2 marks] (f ) Define the weakest liberal precondition wlp(C,Q) in higher-order logic. [2 marks] (g) What is the relationship between {P} C {Q} and wlp(C,Q)? [2 marks] (h) Explain how x. P(x) is represented in terms of -abstraction and function application in higher-order logic. [2 marks] (i) Show how to derive a proof rule for the one-arm conditional from the proof rule for the two-arm conditional and the definition of IF S THEN C as IF S THEN C ELSE SKIP. [4 marks] 5 (TURN OVER) CST.2007.7.6 7 Specification and Verification II (a) Explain the use of the following when representing circuits in logic: (i) higher-order variables; [2 marks] (ii) conjunction (); [2 marks] (iii) existential quantification (). [2 marks] (b) Describe a representation of binary words in logic and define a function that maps a word to the natural number it encodes in binary. [2 marks] (c) Describe how the following components are modelled in higher-order logic: (i) unit-delay; [2 marks] (ii) clocked, edge-triggered D-type register. [2 marks] (d) Let [t, t0 ] denote the closed interval starting at t and ending at t 0 (t t 0 and both t and t 0 are included in the interval). Give definitions in higher-order logic of the predicates (i) Stable (ii) Odd where: Stable f (t, t0 ) is true if and only if the value of f is constant on the interval [t, t0 ] and Odd f (t, t0 ) is true if and only if f is true an odd number of times in the interval [t, t0 ]. [2 + 4 marks] (e) Contrast the simple switch model of transistors with the difference switching model. [2 marks] 6 CST.2007.7.7 8 Information Theory and Coding (a) Suppose that the following sequence of Yes/No questions was an optimal strategy for playing the "Game of seven questions" to learn which of the letters {A, B, C, D, E, F, G} someone had chosen, given that their a priori probabilities were known: "Is it A?" "No." "Is it a member of the set {B, C}?" "No." "Is it a member of the set {D, E}?" "No." "Is it F?" "No." (i) Write down a probability distribution for the seven letters, p(A), . . . , p(G), for which this sequence of questions was an optimal strategy. [3 marks] (ii) With this probability distribution, what was the uncertainty, in bits, associated with each question? [1 mark] (iii) What is the entropy of this alphabet? [1 mark] (iv) Now specify a variable length, uniquely decodable, prefix code for this alphabet that would minimise the average code word length. [3 marks] (v) What is your average coding rate R for letters of this alphabet? [1 mark] (vi) How do you know that a more efficient code could not be developed? [1 mark] (b) The signal-to-noise ratio SNR of a continuous communication channel might be different in different parts of its frequency range. Explain how the information capacity C of a noisy continuous communication channel, whose available bandwidth spans from frequency 1 to 2, may be defined in terms of its signal-to-noise ratio as a function of frequency, SNR(). Define the bit rate for such a channel's information capacity, C, in bits/second, in terms of the SNR() function of frequency. [5 marks] (c) An invertible transform generates projection coefficients by integrating the product of a signal with 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? [2 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 - i.e. that it exists in only a limited number of independent quanta? [3 marks] 7 (TURN OVER) CST.2007.7.8 9 Types (a) What is meant by the term type soundness in connection with type systems for programming languages? [1 mark] (b) Explain by example how ML-style polymorphism for let-expressions combined with reference types leads to an unsound type system. (As part of your answer you should define the type system, but you need not give a formal definition of how expressions in the language evaluate.) [14 marks] (c) How does Standard ML restrict the typing rule for let-expressions in order to restore type soundness? Why does the restriction render untypeable the example you used in part (b)? [5 marks] 10 Computer Systems Modelling (a) Let U be a uniform (0, 1) random variable. Show that for any continuous distribution function F(x), the random variable X defined by X = F 1 (U) has the probability distribution function F(x). [4 marks] (b) Use your result in part (a) and a uniform (0, 1) random variable, U, to construct random variables for the following two distributions: (i) the uniform (a, b) distribution where a and b are real numbers such that a < b; [3 marks] (ii) the exponential distribution Exp() with parameter > 0. [3 marks] (c) Suppose that X1, X2, . . . , Xn are independent, identically distributed random variables with mean and variance 2 . Use the central limit theorem to derive an approximate 100(1 ) percent confidence interval for . [5 marks] (d) How would you obtain a confidence interval similar to that given in part (c) that is exact in the special case where the random variables X1, X2, . . . , Xn have a Normal distribution? [5 marks] 8 CST.2007.7.9 11 VLSI Design (a) Sketch a transistor-level circuit for a 2-input AND gate in static CMOS. [2 marks] (b) Consider the design of a 16-input AND gate in static CMOS. (i) Explain why the 2-input design could not simply be scaled up. [2 marks] (ii) Sketch alternative designs using two and four levels of NAND and NOR gates. [2 2 marks] (iii) Use logical effort to estimate the delay of both the designs, assuming that the conducting channel in a pFET has twice the resistance of that in an nFET. [10 marks] (iv) Determine the approximate value of the electrical effort at which their speeds are equal. [2 marks] 12 Human-Computer Interaction You have been asked to work as a usability consultant, for a company where the development team has created a new version of an existing product. Two important requirements were that the new user interface should be both efficient and intuitive. (a) How would you interpret each of these requirements, in the light of your knowledge of HCI? [1 mark each] (b) The development team claim that their new user interface is already more efficient than the old one. Explain in detail how you could measure whether this claim is justified. [7 marks] (c) The developers also claim that their new version is already more intuitive than the old one. Explain in detail how you could measure whether this claim is justified. [7 marks] (d) What technique could you have used to predict each of these measured improvements, if you had been consulted earlier in the design cycle? [2 marks each] 9 (TURN OVER) CST.2007.7.10 13 Business Studies (a) Give five criteria an investor might apply to a start-up proposal. [5 marks] (b) What are the differences between debt and equity finance? [5 marks] (c) A software start-up company is developing computer games software. They believe their game will have potential market of a million units selling at a retail price of 49.99. They have already raised 1M from Angel investors for 33% of the company, which has been mostly spent on development. They estimate they can complete development and become cash flow positive following initial marketing, but that this will cost a further 1M and take another year. They intend to raise this money by selling further equity. (i) Price this issue. [5 marks] (ii) They receive a letter of intent from a publisher confirming their market estimation and offering 10% royalty on the retail price with 500k recoupable but non-refundable advance (where the publisher will take the first 500k of royalty earned to recoup the advance, but will not demand a refund if the game fails to sell). Should the company take this offer and how does this affect the proposed share offer? [5 marks] 14 E-Commerce (a) Outline five business models for e-commerce. [5 marks] (b) Outline five methods of valuing an e-commerce business. [5 marks] (c) Give plausible reasons why Google purchased YouTube for $1.65Bn in October 2006, when YouTube had never made a profit. [10 marks] 10 CST.2007.7.11 15 Additional Topics A large ski resort is organised as a consortium of hundreds of independently-owned lifts, each serving one or more ski slopes. The resort sells a non-transferable, photo-id based "skipass" ticket that lets its owner ride on a specified subset of the lifts, for a specified range of dates, for an unlimited number of rides. Each ticket has a different barcode and is scanned at the entry gate of each lift to decide whether to let the skier through. The whole resort is about to upgrade from barcode to passive RFID: tickets with embedded RFID tags can be read through the pocket of the skier from a distance of about 5 cm. You have been hired as a security consultant by the resort to oversee the planned changeover. (a) The operators have requested offline operation: like its barcode-based predecessor, the new system must permit the verification of tickets without requiring individual lifts to have a live connection to the central server all day long (or at all). Justify this request, then design a suitable system architecture and discuss the security implications of this requirement. [6 marks] (b) Discuss as many ways as possible in which the consortium might be defrauded and suggest appropriate countermeasures. Label each fraud as "made easier by RFID" or "made harder by RFID". Your employers are slightly less interested in frauds that carry over unchanged between barcode and RFID: so, do mention them if you wish but don't over-analyse them. [8 marks] (c) Small but vocal consumer groups complained about loss of privacy as soon as they heard that the system used RFID. Highlight any privacy threats introduced by RFID in this system. Design an alternative RFID-based architecture offering strong privacy protection for customers. Compare it, from any relevant viewpoints, against the legacy barcode system and against the privacy-indifferent RFID system you designed in part (a). [6 marks] 11 (TURN OVER) CST.2007.7.12 16 Additional Topics You are required to design a security system that uses location information about objects and people. The application scenario is that of a warehouse containing many large boxes. The boxes can be anywhere in the warehouse and are also stacked vertically. Every part of the warehouse is under video surveillance using a very large number of cameras. When a box goes missing there are two requirements. The first is to produce an audit trail of the movements and location of the box in the warehouse during the previous month. The second is to review quickly the vast amount of recorded video data and select only those sceneThe aim is to find a sequence of moves that re-arranges the puzzle to the state shown on the right, where each move involves sliding a single square into the empty space. (a) Explain in detail how this problem can be treated as a planning problem by translating it into a Boolean satisfiability (SAT) problem. Your answer should address the following issues, and in each case should provide specific examples of the SAT representation: (i) The representation of the start state and goal state. [4 marks] (ii) The representation of the relevant actions using successor-state axioms. [4 marks] (iii) The need for precondition axioms. [2 marks] (iv) The need for action-exclusion or state-constraint axioms, and why one might be preferred over the other. [3 marks] (v) The algorithm that can be used to employ a SAT-solver to solve a given sliding blocks problem, and the method for extracting a solution. [3 marks] (b) You do not have a SAT-solver available. You do however have a solver for general local search problems. Explain how you might use the latter to solve the SAT problem obtained in Part (a). [4 marks] 2 CST1.2018.6.3 2 Artificial Intelligence Evil Robot is updating his visual system. He has a single camera that produces an n n matrix I of pixel values. His visual system is arranged as follows: I n n m m o H The input I is reduced to an m m matrix H(I). The elements Hi,j are Hi,j (I) = Xn k=1 Xn l=1 w (i,j) k,l Ik,l + b (i,j) ! where is an appropriate function, and w (i,j) k,l and b (i,j) are the weights and bias for element (i, j). A single output o(H) is computed as o(H) = Xm k=1 Xm l=1 wk,lHk,l + b ! . (a) If Evil Robot has a training example (I 0 , y0 ) and is using an error E(w) where w is a vector of all weights and biases available, derive an algorithm for computing E w for the example. [12 marks] (b) A modification to the system works as follows: o H m m I n n The mapping from I to H is replaced by an n 0 n 0 convolution kernel. This has a single set of parameters vk,l and c used to compute every element of H as the weighted sum of a patch of elements in I Hi,j (I) = nX0 k=1 nX0 l=1 vk,lIi+k1,j+l1 + c ! . Provide a detailed description of how the algorithm derived in Part (a) must be updated to take account of this modification. [8 marks] 3 (TURN OVER) CST1.2018.6.4 3 Complexity Theory (a) Give a precise definition of each of the complexity classes NP and co-NP. [4 marks] (b) Give an example each of (i) an NP-complete language; and (ii) a co-NP-complete language, in each case giving a precise statement of the decision problem involved. [4 marks] (c) If A and B are the two languages identified in Part (b), give an example of a language that is polynomial-time reducible to both A and B. Justify your answer. [4 marks] (d) Consider the following statement: There is a polynomial p such that every valid Boolean formula of length n has a proof of length at most p(n). Moreover, there is a polynomial-time algorithm that can check the correctness of the proofs. This statement is not known to be true or false. Explain what would be the consequences of this statement being true or false for the relationship between NP and co-NP, giving full justification for your answer. [8 marks] 4 CST1.2018.6.5 4 Complexity Theory Consider the following two decision problems: Reach - the problem of deciding, given a directed graph G and two vertices a and b in G, whether there is a path in G from a to b. UReach - the problem of deciding, given an undirected graph G and two vertices a and b in G, whether there is a path in G from a to b. It is known that Reach is NL-complete (under logarithmic-space reductions) and that UReach is in the complexity class L. (a) Based on the above information, for each of the following statements, state whether it is true, false, or unknown. In each case, give justification for your answer and in the case where the truth of the statement is unknown, state any implications that might follow from it being true or false. (i) Reach L UReach, i.e. Reach is reducible in logarithmic-space to UReach. (ii) UReach L Reach. (iii) UReach is in P. (iv) If Reach is in L, then P=NP. [3 marks each] (b) Let us say that a nondeterministic Turing machine M is symmetric if for any two configurations c1 and c2 of M, if c1 M c2, then c2 M c1. We write SL for the class of all languages that are accepted by a symmetric Turing machine using O(log n) work space on inputs of length n. By considering the configuration graph of a machine and using the fact that UReach is in L, explain why it follows that SLL. [8 marks] 5 (TURN OVER) CST1.2018.6.6 5 Computation Theory (a) Give a precise definition of the class of partial recursive functions. [3 marks] (b) We can associate with each natural number i N the partial recursive function fi : N*N computed by the register machine coded by the number i. Explain why (i) for every partial recursive function f : N*N, there is an i such that f = fi ; and (ii) the partial function g : N N*N given by g(i, n) = fi(n) is computable. [8 marks] (c) Show that the total function T : N N N given by: T(i, n) = 1 if fi(n) 0 otherwise is uncomputable. Here fi refers to the partial function associated with i N as in (b). [9 marks] 6 CST1.2018.6.7 6 Computation Theory (a) What does it mean to say that a partial function f : N k*N is register machine computable? [2 marks] (b) Show that the following functions are register machine computable: (i) add(x, y) , x + y; (ii) max(x, y) , y if x y x otherwise ; and (iii) comp(x, y) , 0 if x y 1 otherwise. [9 marks] (c) What does it mean to say that a function f : N k N is -definable? [2 marks] (d) Is every -definable function register-machine computable? Give a detailed justification for your answer. [7 marks] 7 (TURN OVER) CST1.2018.6.8 7 Foundations of Data Science Let X1, . . . , X100 be independent samples drawn from the Exp() distribution, for some unknown parameter > 0. [Note: The Exp() distribution has density function f(x) = ex, for x > 0. It has mean 1/, and variance 1/2 .] (a) Show that the maximum likelihood estimator for is = 100/ P100 i=1 Xi . [3 marks] (b) Using the central limit theorem, find a and b such that P

1/ [a, b] 0.95 explaining your calculations carefully. Hence find real numbers and such that P

[, ] 0.95 . [6 marks] (c) Explain how to use the bootstrap resampling method to approximate the probability P

(1 ), (1 + )

where is given. In your answer, include an explanation of what is meant by 'resampling'. [6 marks] (d) Using your answer to Part (c), give pseudocode to compute such that P

(1 ), (1 + )

0.95 . Comment your code appropriately. [5 marks] s that contain the missing box.