g Describe an algorithm for clipping a line against a rectangle….

Question Answered step-by-step g Describe an algorithm for clipping a line against a rectangle…. g Describe an algorithm for clipping a line against a rectangle.  Show that it works using the above three examples. [3 marks] x y 1 1 2 2 B(0,0) A(0,1) B'(3,2) A’ 30? The above diagram shows a complicated 2D transformation applied to a unit square. The overall transformation can be described in terms of a number of simpler transformations. Describe each of these simple transformations and give a matrix representation of each using homogeneous coordinates. [6 marks] Use the matrices from the previous part to find the (x, y) coordinates of point A0 , the image of point A under the overall transformation. [2 marks] 3 [TURN OVER CST.98.12.4 5 Business Studies The figure shows a section of a PERT diagram for a small software project, together with the number of programmer-days each task is estimated to take. (a) What is the critical path in a PERT diagram and why is it important? What is the critical path in the PERT diagram shown below? [5 marks] (b) One analyst and two programmers are assigned to the project, in addition to the manager. How long will the project take? [5 marks] (c) Derive the equivalent GANTT chart for the project. [5 marks] (d) Task 8 slips by 2 days. How does this affect the project? What actions, if any are required, can be taken to alleviate the slippage? [5 marks] Task 1 3 days Task 2 10 days Task 3 5 days Task 4 5 days Task 5 7 days Task 6 5 days Task 10 5 days Task 7 5 d 2 Test 2 Integrate Specify final tests Code test harness Test the test harness Final tests Management 4 CST.98.12.5 6 Introduction to Security Some banks issue their Automatic Teller Machine (ATM) card customers with a randomly selected personal indentification number (PIN). Others issue their customers with an initial PIN only, and let the customers choose their own PIN the first time they use the card in an ATM. Describe the advantages and disadvantages of these approaches. [5 marks] Again, some banks compute the customer PIN by encrypting the account number using DES and a key known only to their central systems and ATMs, taking the first four hex digits of the result, replacing the digits A, . . . , F with 0, . . . , 5 respectively, and finally, if the first digit of the result is 0, replacing it with a 1. What is the probability that a criminal can get the PIN right given three guesses? [5 marks] Yet other banks have used DES, and a key known only to their central systems and ATMs, to encrypt the PIN (whether randomly generated or customer selected); they then write the result on the magnetic strip on the customer’s card, so that the ATM can verify it without reference to the central system. Describe the disadvantages of this arrangement. [5 marks] In order to prevent attacks based on manipulating magnetic strips, banks in some countries have moved to using smart cards. What effect would you expect such a move to have on the incidence of card-based fraud? [5 marks] 5 [TURN OVER CST.98.12.6 7 Compiler Construction Explain how a parse-tree representation of a program may be converted into a stack-based intermediate language giving sketches of code to translate expressions, assignments and the if-then-else command; you should also explain how occurrences of a variable in an expression or assignment are translated. The program may be assumed to conform to the following syntax: E -> n | x | E + E | f(E,E) D -> let f(x,x) = {Dseq; Cseq; E} | let x = E C -> x := E; | if E then C else C Cseq -> C | C Cseq Dseq -> D | D Dseq with start symbol Dseq. Here n corresponds to integer constants, x corresponds to identifiers used as variable names and f corresponds to identifiers used as function names (you may assume these are disjoint). The function declaration construct has the effect of defining a function which, when called, makes declarations, performs commands and then returns the result of its expression; note that therefore functions may be defined within functions, but the above restriction on identifiers means that they cannot be returned as results. [20 marks] 8 Prolog for Artificial Intelligence Write Prolog programs that define the following predicates. Your programs should ensure that backtracking does not produce spurious alternative solutions. (a) The nth element of a list: nth(X,N,L) instantiates X to the Nth element of list L. Assume that list elements are numbered increasing from 1. [4 marks] (b) The last element of a list: last(X,L) instantiates X to the last element of list L. [4 marks] (c) Remove an element from a list: remove(X,L,M) instantiates M to a list containing all the elements of list L except for every occurrence of term X. [6 marks] (d) Substitute one element for another: subst(L,X,Y,M) instantiates M to a list containing all the elements of list L except that every occurrence of term X in L is replaced by term Y in M. [6 marks] 6 CST.98.12.7 9 Databases The relational model of data was introduced in the early 1970s in a sequence of papers by E.F. Codd. This model proposes a tabular view of data, with a simple Data Manipulation Language (DML) based on relational algebra or relational calculus. Briefly explain the essential features of the model and its DML. [6 marks] Later work by Codd and others addressed weaknesses in the expressive power of the relational model. For each of the following give an example to show how the weakness arises, and explain an approach proposed to resolve the difficulty: (a) computing the transitive closure [4 marks] (b) manipulating collections of records [4 marks] (c) handling entity specialisation [6 marks] In case (c) you should outline the proposals of either the Object-Oriented Database System Manifesto or the Third Generation Database System Manifesto. 10 Introduction to Functional Programming Write an ML function upto of type int -> int list such that upto n generates the list [1,2,3,…,n]. [7 marks] What is wrong with the following function to take the head of a list? fun wrong_headed [h,t] = h; What is the type of wrong_headed? [5 marks] Why is the following function to evaluate Fibonacci numbers inefficient? fun fib 0 = 1 | fib 1 = 1 | fib n = fib(n-1) + fib(n-2); Write a similar but more efficient version. [8 marks] 7 [TURN OVER CST.98.12.8 11 Computer Vision Give three examples of problems in computer vision which are formally ill-posed. In each case explain how one or more of Hadamard’s criteria for well-posed problems has failed to be satisfied. Illustrate how the addition of ancillary constraints or assumptions, even metaphysical assumptions about how the world behaves, enables one to convert the ill-posed problem into a well-posed problem. Finally, discuss how the use of Bayesian priors can perform this function. [20 marks] 12 Complexity Theory (a) Describe the problem 3-SAT. [2 marks] (b) Show how any instance of the seemingly more general problem n-SAT can be reduced to an equivalent one where each term has exactly three literals in it. Estimate how much larger the reduced problem would be than the original one. [4 marks] (c) A certain computation using a non-deterministic Turing machine completes in T time-steps. The Turing machine has k states and uses an alphabet of N symbols. A major theorem underpinning the concept of NP-completeness is based on a conversion of a description of such computations to boolean formulae which characterise them. Explain how, in such a reduction, boolean variables may be used to describe states that the Turing machine might be in. Show how to derive those components of the boolean formula that relate just to the way in which the Turing machine moves its read-write head. Your explanation should be sufficiently complete and carefully explained that it could be used as a specification of a program that would perform that part of the translation from Turing machine descriptions to boolean formulae. You should not attempt to explain the rest of the boolean formula or how it fits into a complete proof or program. [11 marks] (d) In terms of T, k and N, about how many symbols does it take to write the boolean expression you generate? [3 marks] 8 CST.98.12.9 13 Numerical Analysis II Let n+ be the number of positive real roots of a polynomial pn(x). Let c be the number of changes of sign when the coefficients are taken in order. State Descartes’ rule of signs. [2 marks] If p3(x) = x 3 ? 8x 2 + 11x + 20 what does this rule say about the polynomials p3(x), p3(?x)? [2 marks] Newton’s method for solution of a system of n non-linear equations f(x) = 0 can be expressed in the form xk+1 = xk + hk+1. What is the formula for hk+1? [2 marks] Outline the damped Newton method in n variables. [4 marks] Apply the damped Newton method in one variable to find one root of the polynomial p3(x), using x0 = 1 as the starting value. Hence factorise p3(x) and draw a rough sketch of the polynomial, showing the first Newton step as a tangent. Discuss capability-based access control under the headings • protection of capabilities • control of transfer of capabilities between principals • delegation of rights • revocation of capabilities Your answer should mention the differences between the management of capabilities in distributed as opposed to centralised systems. You should consider alternative designs of capabilities. [20 marks] 2 Digital Communication II What is a leaky bucket algorithm? How can it be used to police traffic? How can it be used to shape traffic? [5 marks] You are required to provide a flow admission controller for a router. RSVP is used to request resources for flows with leaky bucket parameters. Outline how you would design the controller, bearing in mind the soft state nature of RSVP. [15 marks] 1 [TURN OVER CST.98.9.2 3 Computer System Modelling An M/M/m queue has an arrival process with mean rate ?, and processes customers at a mean rate of µ. (a) What are the distributions and parameters of the inter-arrival and service times of customers? [3 marks] (b) Sketch an outline proof showing that the distribution of the departure process from the queue is the same as that of the arrivals process. [10 marks] Briefly contrast analytical queueing analysis and discrete event simulation with regard to their fields of applicability and other important considerations for the systems modeller. [7 marks] 4 VLSI Write short notes on two of the following: (a) the fundamental limits which may slow down progress in semiconductor technology; (b) designing VLSI systems for low-power applications; (c) problems which can prevent an apparently properly designed chip from working to specification. [10 marks each] 2 CST.98.9.3 5 Business Studies You are assigned the role of UK sales and marketing manager for a new kind of low-cost computer, primarily aimed at the educational market. Whilst not directly PC compatible, the computer includes web access, PC-compatible word processing, other PC-compatible productivity tools, and a suite of educational programs. How would you approach this task? Draw up an outline business plan as follows. (a) Show what communication and distribution channels you propose. [5 marks] (b) Propose a selling price, and estimate the number of units you might sell at this price. [5 marks] (c) Estimate a 3-year budget for the sales and marketing activity. [5 marks] (d) State how you would refine your estimates, and what monitoring you would put in place. [5 marks] Background information: • There are about 32,000 schools in the UK. • The UK government has recently published a consultative document The National Grid for Learning with a proposal to spend £100M on provision of internet access in schools over the next 5 years. This sum includes infrastructure provision, content development and teacher training, as well as a contribution to provision of computers in schools. • The average school IT spend is projected to be £18,000 each year. Additional funding may be available from government and parents for specific projects. • The unit manufacturing cost is £200, delivered. 3 [TURN OVER CST.98.9.4 6 Advanced Algorithms Describe the structure of an ordinary heap, and document the costs associated with the following operations. (a) Create a heap from n items where the items are all available at once but are initially in a random order. (b) Remove the top (i.e. smallest) value stored in the heap. (c) Given a pointer to an arbitrary item in the heap, re-instate the heap property after the key associated with that single item is decreased in value. (d) Form a new heap whose elements are all those that are present in two other heaps (which may be destroyed in the combining process if that helps). You are not expected to give detailed accounts of the algorithms involved. [6 marks] Now explain the structure of a Binomial Heap and compare, with some explanation of your claims, the costs incurred in the same set of operations if Binomial rather than ordinary heaps were to be used. [14 marks] 4 CST.98.9.5 7 Optimising Compilers Consider the programming language with terms e having abstract syntax: e ::= x | c | ?x.e | e1e2 | let x = e1 in e2 where x ranges over a set of identifiers and c over a set of integer constants. For the rest of the question, your answers can be illustrated by reference to the program p: ?z.let id = ?x.x in id id 7 State how to label terms in p uniquely so that a subterm occurring repeatedly in a term has different labels. [4 marks] Show how such terms may be seen as a family of flowgraphs, one for each ? (you may find it useful to consider the above labelling as providing a unique function name for anonymous ?-abstractions). [4 marks] Define the call graph of such a family of flowgraphs, stating clearly how indirect calls are treated. [4 marks] Describe how to associate a flow-variable with each labelled node of a term such as p and to derive equations which can improve the above treatment of indirect calls to get a better approximation of the edges in the call graph. [8 marks] [Hint: you may find it useful to recall the shorthand of (? 7? ?) ? ? as representing the compound constraint that whenever (?xj .ek ) i ? ? we have ?j ? ? ? ? ? ?k where ?r is the flow variable associated with the node labelled r.] 5 [TURN OVER CST.98.9.6 8 Neural Computing When using a feed-forward network to solve a classification problem we can interpret the network’s outputs as posterior probabilities of class membership, and then subsequently use these probabilities to make classification decisions. Alternatively, we can treat the network as a discriminant function which is used to make the classification decision directly. Discuss the relative merits of these two approaches. [7 marks] Explain the concept of a likelihood function, and the principle of maximum likelihood. [3 marks] Consider a feed-forward network which implements a function y(x, w) in which y is the output variable, x is the vector of input variables, and w is the vector of weight parameters. We wish to use this network to solve a classification problem involving two classes A and B. The value of y, when the network is presented with an input vector x, is to be interpreted as the posterior probability P(t = 1|x) in which t = 1 denotes class A and t = 0 denotes class B. Write down the probability distribution of t given y. Use the principle of maximum likelihood to derive an expression for the corresponding error function defined over a set of training data comprising input vectors xn and targets tn, where n = 1, . . . , N. Write down a suitable form for the output unit activation function y = g(a). Hence evaluate the derivative of ln P(t|y) with respect to a. [10 marks] 6 CST.98.9.7 9 Security Describe those provisions of the following Acts of Parliament that are relevant to computer security: • The Civil Evidence Act of 1968 • The Police and Criminal Evidence Act of 1984 • The Data Protection Act of 1984 • The Computer Misuse Act of 1990 [12 marks] A software house incorporates a time-lock which causes their product to stop working if it is not supplied with a suitable password every 6 months. What risks are they running? [4 marks] A hospital de-identifies patient records by removing names and addresses, leaving only the patient’s postcode and date of birth as an identifier. These records are then sold to researchers and drug companies. What risk is the hospital running? [4 marks] 7 [TURN OVER CST.98.9.8 10 Denotational Semantics State, with justification, whether each of the following statements is true or false. (a) The set of natural numbers, N = {0, 1, 2, . . .}, equipped with the usual less-than-or-equal relation, 6, is a domain. [3 marks] (b) The set of all subsets of N, equipped with the relation of subset inclusion, is a domain. [4 marks] (c) For any domain D and element d ? D with d 6= ? fd(x) = > if d v x, ? otherwise defines a strict continuous function fd from D to the flat domain {>}?. [4 marks] (d) For any domain D and element d ? D with d 6= ? gd(x) = ? if x v d, > otherwise defines a strict continuous function gd from D to {>}?. [4 marks] (e) For any continuous functions h : D ? E and k : E ? D between domains D and E, fix (k ? h) v k (fix (h ? k)). [5 marks] 8 CST.98.9.9 11 Information Theory and Coding Consider Shannon’s third theorem, the Channel Capacity Theorem, for a continuous communication channel having bandwidth W Hertz, perturbed by additive white Gaussian noise of power spectral density N0, and average transmitted power P. (a) Is there any limit to the capacity of such a channel if its signal-to-noise ratio P N0W can be arbitrarily increased? If so, what is that limit? [2 marks] (b) Is there any limit to the capacity of such a channel if, leaving N0 and P unchanged, its bandwidth W in Hertz can be arbitrarily increased? If so, what is that limit? [3 marks] [Hint: ln(1 + x) = x ? x 2 2 + x 3 3 ? x 4 4 + · · · where ?1 < x < 1.] Explain why smoothing a signal, by low-pass filtering it before sampling it, can prevent aliasing. Draw a graph in the Fourier domain which illustrates the origin of aliasing, and also show in the picture how smoothing solves the problem. What would be the most effective low-pass filter to use for this purpose? Draw it in the Fourier domain. [10 marks] Suppose that women who live beyond the age of 70 outnumber men in the same age bracket by three to one. How much information, in bits, is gained by learning that a certain person who lives beyond 70 happens to be male? [5 marks] 9 [TURN OVER CST.98.9.10 12 Computer Vision It could be said that the central problem of pattern recognition is the relation between the within-class variability and the between-class variability for the patterns that one would like to recognise. Explain this problem in the case of face recognition, treating separately the problems of (a) face detection (distinguishing faces from non-faces) (b) face identification (c) face interpretation (classifying the expression and pose angle of the face) How do the forms of variability for faces influence each of the three tasks? Is within-class variability ever helpful, and between-class variability ever harmful, to the performance of the task? What role can statistical decision-theory play in formalising and solving these problems? [20 marks] 13 Types What is meant by the terms safety and type soundness in connection with programming languages and their type systems? [2 marks] Explain how a na¨?ve combination of ML-style polymorphism and references results in an unsound type system. Your account should include the axioms and rules of the type system, but need not give a formal definition of the operational semantics. [15 marks] State, without proof, how the rule for typing let-expressions can be restricted to restore type soundness.answer all Engineering & Technology Computer Science COMP 289 Share QuestionEmailCopy link Comments (0)