The Loop and Butterfly subdivision schemes can both operate on triangular meshes, in which all of the polygons have three sides. Both schemes subdivide the mesh by introducing new vertices at the midpoints of edges, splitting every original triangle into four smaller triangles, as shown below. Each scheme has rules for calculating the locations of the new "edge" and "vertex" vertices based on the locations of the old vertices. These rules are shown below. All weights should be multiplied by 1 16 . (i) Which of the two schemes produces a limit surface which interpolates the original data points? (ii) Which of the four rules must be modified when there is an extraordinary vertex? For each of the four rules either explain why it must be modified or explain why it does not need to be modified. (iii) Suggest appropriate modifications where necessary to accommodate extraordinary vertices. [9 marks] 4 CST.2004.7.5 5 Computer Systems Modelling (a) Consider an interactive system with average system response time R and system throughput X. Derive the interactive response time law when there are M users present, each with an average think time Z. [6 marks] (b) Consider an interactive timesharing system with M users, one CPU and two disks labelled A and B respectively. Suppose that measurements of the system have determined that: the average user think time Z is 5 seconds; the average time spent by a job in the CPU is 40 ms per request; the average time spent by a job at the individual disks per request is 30 ms for disk A and 25 ms for disk B; the visit counts per job are 25 requests for the CPU, 20 requests for disk A and 4 requests for disk B. (i) For each of the devices: CPU, disk A and disk B, determine the service demands. [4 marks] (ii) If disk A has a utilisation of 60%, what is the utilisation of the CPU and of disk B? [5 marks] (iii) If the utilisation of disk B is 10%, what is the average response time when there are 20 users present? [5 marks] 6 Specification and Verification I Write short notes (approximately one paragraph) explaining the similarities and differences between each of the following: (a) Annotations and verification conditions. [5 marks] (b) Partial and total correctness. [5 marks] (c) Deep and shallow embedding. [5 marks] (d) First order and higher order logic. [5 marks] 5 [TURN OVER CST.2004.7.6 7 Specification and Verification II (a) Explain how combinational and sequential devices can be modelled in higher order logic in a uniform way (i.e. so that combinational and sequential devices can be connected). [3 marks] (b) Illustrate your explanation by showing how to define combinational devices NOT and AND that perform negation and conjunction, respectively, and a sequential unit-delay device DEL such that the output of DEL at time t+1 is the value input at t. [3 marks] (c) Define in higher order logic a predicate Rose such that if t > 0 then Rose f t is true if and only if f has a rising edge at time t (i.e. f is true at t but false at t1). [2 marks] (d) Draw a diagram showing how to connect instances of NOT, AND and DEL to implement a device RoseImp, with one input and one output, such that the output is true at time t, where t > 0, if and only if there is a rising edge on the input at time t. [6 marks] (e) Represent your diagram in higher order logic by defining a predicate RoseImp, and then outline how to show that: in out. RoseImp(in, out) t. out(t+1) = Rose in (t+1) You need not give a detailed proof, just an overview of how such a proof could be performed. [6 marks] 6 CST.2004.7.7 8 Information Theory and Coding (a) Consider an alphabet of 8 symbols whose probabilities are as follows: A B C D E F G H 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1 128 (i) If someone has selected one of these symbols and you need to discover which symbol it is by asking "yes/no" questions that will be truthfully answered, what would be the most efficient sequence of such questions that you could ask in order to discover the selected symbol? [2 marks] (ii) By what principle can you claim that each of your proposed questions is maximally informative? [2 marks] (iii) On average, how many such questions will need to be asked before the selected symbol is discovered? [2 marks] (iv) What is the entropy of the above symbol set? [2 marks] (v) Construct a uniquely decodable prefix code for the symbol set, and explain why it is uniquely decodable and why it has the prefix property. [2 marks] (vi) Relate the bits in your prefix code to the "yes/no" questions that you proposed in (i). [2 marks]

An interpreter for a string processing language is written in C. Describe four storage and efficiency-related considerations when designing the module for storing strings for the interpreter

Describe the characteristic features of a VLIW (Very Long Instruction Word) processor architecture. [3 marks] pointing out the advantages and disadvantages of each strategy in achieving this goal. You may wish to consider the following issues: instruction issue logic cache sizes compiler code generation execution unit utilisation [9 marks] Why have VLIW architectures traditionally been used only for special-purpose applications such as Digital Signal Processors? [3 marks] What techniques have been developed to make VLIW-like architectures more suitable for general-purpose use? You work for a large company where there are many meetings, both of internal staff and between staff and external clients. Meetings are recorded in formal minutes. so that company staff can locate minutes on a particular topic. Because of the legal implications that past discussions and decisions may have, the company is particularly concerned that the new retrieval system will be reliable and effective. Outline the design of your system, indicating the particular features it will have that are intended to meet the company's requirements (you can assume that minutes are always clearly dated and have explicit lists of participants). [10 marks] The company is willing to allow the installation of a pilot system so your approach can be evaluated under realistic conditions. Describe, in detail, your design for the evaluation: what data, operational conditions and aspects of your system would you consider, and why? What performance measures would you apply, and why?

In a proposed, next-generation banking system a number of transactions are to be scheduled to run concurrently: Debit (D) transactions to make payments from customer accounts to a credit card company. Interest (I) transactions to add daily interest to customer account balances. Transfer (T) transactions which first check whether the source account contains sufficient funds then either abort or continue the transfer from source to destination accounts. Customer x is running a T to transfer 1000 from A to B. Customer y is running a T to transfer 200 from B to A. (a) Discuss the potential for interference between any of these transactions. [7 marks] (b) Demonstrate the effect of concurrency control based on strict two-phase locking in relation to the discussion in (a). [8 marks] (c) Comment on the scope of concurrency control in relation to the discussion in (a). [5 marks] [Hint: you may assume that operations on bank account objects, such as debit, credit and add-interest are atomic.] 1 [TURN OVER CST.2000.4.2 2 Continuous Mathematics (a) In his formulation of the calculus, Newton captured only the notion of integer-order differentiation considering first-, second- and third-order derivatives, and so on. In scientific computing, however, we sometimes need fractional-order derivatives, as for example in fluid mechanics. Explain how Fractional Differentiation (derivatives of non-integer order) can be given precise quantitative meaning through Fourier analysis.

In this question, where appropriate, you may use a short fragment of code to complement your explanation. (a) What is the difference between declaration and definition? (b) Describe the layout of the memory components: Dynamic Memory Allocation, Data Segment, Code Segment and Stack. You may use an illustration as part of your explanation. (c) Using an example, explain what stack unwinding is in C++. (d) How may I use template meta programming to inline recursive functions? (e) Why did the designers of the C++ language decide to make an empty class 1 byte in length? [4 marks each] 4 Compiler Construction (a) In a stack-based runtime system, what problem does the static link method attempt to solve, and how does it work? [4 marks] (b) Can static linking be used to implement a language with first-class functions? If yes, then explain how. If no, give an example and explain how static linking fails. [6 marks] (c) Explain how exceptions (ML-like raise and handle) could be implemented with a stack-oriented machine. [5 marks] (d) A program may evaluate to an exception that has been raised all the way to the top-level and never handled. Discuss how you might modify your implementation in part (c) to dump debugging information when such toplevel exceptions are raised. The debugging information should include some description of the state of the computation just before the top-level exception was raised. [5 marks] 4 CST.2011.3.5 5 Compiler Construction Consider a simple grammar for arithmetic expressions: E ::= n | x | E | E + E | ( E ) with n ranging over integer constants and x ranging over variables. We want to compile expressions to code for a simple stack-based machine with the following instruction set. instruction meaning pushvar k push the value of the k-th variable on top of stack push n push n on top of stack add replace the top two stack items with their sum neg replace the top stack item with its negation For this problem, we will not worry about how variables are bound to values nor how abstract syntax trees are produced. (a) How will your compiler generate code from expressions of the form E? [4 marks] (b) How will your compiler generate code from expressions of the form E1 + E2? [4 marks] (c) What code will your compiler generate for the expression -(-x + (17 + y))? [4 marks] (d) Suppose we now want to extend the language of integer expressions with multiplication E ::= | E E but we cannot extend the machine with an instruction for multiplication. Can you implement this extended language directly with the machine instruction set presented above? If not, suggest a minimal extension to the instruction set that allows for the implementation of multiplication using the addition from the instruction set. Explain the semantics of your extensions and how you would use them to implement multiplication. [8 marks] 5 (TURN OVER) CST.2011.3.6 6 Concepts in Programming Languages (a) Give one difference and one similarity between the programming languages: (i) Algol and SIMULA [2 marks] (ii) LISP and Smalltalk [2 marks] (b) What is the type of the expression fn f => fn x => f(f(x)) inferred by the SML interpreter? Explain your answer. [6 marks] (c) Give an example in the SML Modules language of two distinct signatures, say IN and OUT, and of a functor that takes structures matching IN to produce structures matching OUT. [6 marks] (d) Comment on the mechanism for parameter-passing in the programming language Scala. [4 marks] You may wish to consider the following two code samples. def whileLoop( cond: => Boolean )( comm: => Unit ) { if( cond ) comm; whileLoop( cond )( comm ) } def qsort[T]( xs: Array[T] )( implicit o: Ord[T] ): Array[T] = if( xs.length <= 1 ) xs else { val pivot = xs( xs.length/2 ) Array.concat ( qsort( xs filter (x => x.lt(x,pivot)) ) , xs filter (x => x == pivot ) , qsort( xs filter (x => x.lt(pivot,x)) ) ) } 6 CST.2011.3.7 7 Further Java In this question you will need to fill in missing parts of a Java program. You may ignore any exception handling and will not be penalised for minor syntactic errors. You are provided with a class Eval: public class Eval { public static int f(Record r) { ... } } (a) Add another method Integer maxf(Iterator it) to the class Eval. Your method should return the maximum value computed by f for every Record returned by the iterator or null if there are no records available. The relevant portion of the Iterator interface is as follows: interface Iterator { // return true if there are more values available public boolean hasNext(); // return the available value and advance to the next one public T next(); } [5 marks] (b) Complete the methods run() and join() in the following abstract class. You may add additional fields or methods if you wish. abstract class Joinable implements Runnable { abstract void exec(); final public void run() { // ... call the exec() method ... } void join() throws InterruptedException { // block the calling thread until exec() completes in run() } } [7 marks] (c) Provide a method Integer parmaxf(Iterator it, int n) which is functionally equivalent to Eval.maxf, except that it should create n parallel threads of execution to speed up the calculation of the result. You may assume that Iterator is thread-safe. You may find it helpful to subclass the Joinable class.

converting the java class into a python class

class Library:

def __init__(self):

def addAuthor(self, Author):

def addPublisher(self, Publisher):

def addBook(self, Book):

(b) Explain the meaning of "self-Fourier", and cite at least two examples of mathematical objects having this property. [3 marks] (c) Explain briefly: (i) sensation limit; [1 mark] (ii) critical band; [1 mark] (iii) Bark scale. [1 mark] (d) Which different aspects of perception do Weber's law and Steven's law model? [2 marks] 7 [TURN OVER CST.2004.7.8 9 Quantum Computing (a) You are given a qubit that is in one of two states: either |i = |0i or |i = cos |0i + sin |1i. If you measure the qubit in the computational basis, what is the probability that your measurement correctly identifies the state? [3 marks] (b) Draw a labelled schematic circuit diagram for: (i) the phase estimation algorithm; [4 marks] (ii) Grover's algorithm.