Computer Systems Modelling A distributed database is organised as…
Question Answered step-by-step Computer Systems Modelling A distributed database is organised as… Computer Systems Modelling A distributed database is organised as four servers with 100 terminals attached via 10 terminal concentrators. The concentrators and the servers are connected by a 100 Mbps network. Each server has a single disk. A typical query generates the following load on the system: terminal concentrator 70 ms server CPU 60 ms disk 25 ms network 1 Kbyte transfer Give estimates and bounds of average system response time when each terminal generates (a) a query every minute (b) a query every 10 seconds [20 marks] 5 Information Theory and Coding Define the mutual information and channel capacity of a discrete memoryless channel. [10 marks] 0 1 1 0 p p 1-p 1-p X Y For the binary symmetric channel with transition probability p, derive the channel capacity. Sketch a graph of the channel capacity against the transition probability. [10 marks] 3 [TURN OVER CST.94.9.4 6 Designing Interactive Applications Define in one sentence the role of requirements in system design. Explain the difference in purpose between performance requirements and functional requirements for interactive systems. [2 marks] The rules enforced in the City for dealings in equities require that deals (buying and selling stock) are to be recorded within 60 seconds of agreeing each deal. In one particular bank this is currently done by having the dealer write the details of the deal on a paper “ticket” and place it in a pot for collection by a deal-input clerk who enters the deal into an on-line system. Six items of information must be written on the ticket (average lengths shown in parentheses): 1. the customer’s account number (four digits) 2. the name of the buyer/seller (six characters) 3. the name of the stock (six characters) 4. the number of shares bought or sold (four digits) 5. the price agreed (five characters; for example, 72 3/8 or 167.5) 6. whether this is a buy or a sell Each dealer handles only a limited range of stocks, at most thirty (i.e., thirty companies such as ICI, Wellcome, Hanson, etc.). During busy periods, dealers may make deals every 30 seconds. It is proposed that, in the future, dealers input their deals themselves. (a) Using the Keystroke-level model, calculate how long it would take dealers to record deals by typing the details on an alphanumeric keyboard. [4 marks] (b) Suppose all of the names of stocks were displayed on the dealer’s interactive workstation, together with their current prices. Sketch out a design to allow the dealer to input some of the details of the deal graphically with a mouse and some with the keyboard. Again using the Keystroke-level model, calculate the speed of entry of deals. Using this result and the result from (a), write a performance requirement for a system to support dealers in entering deals. [8 marks] Use the following times in seconds for operators: K (key-press) = 0.30, P (point at target) = 1.10, H (home hands to another device) = 0.40, M (mentally prepare) = 1.35. (c) Discuss the benefits of these two alternatives to the current method, and the feasibility of meeting the performance requirements derived in (b) by using other styles of interaction. [6 marks] 4 CST.94.9.5 7 Algebraic Manipulation Explain how polynomials can be represented within an algebra system using (a) recursive, and (b) distributed data structures. For each, illustrate your answer by showing what structure will be generated for the polynomial a1a2 . . . a10(1 + x + · · · + x 10) first when the 11 variables a1, . . . a10 and x are sorted in alphabetic order, and then when they are kept in inverse alphabetic order. [16 marks] Does the ordering used make any difference to the amount of space consumed? [4 marks] 8 Artificial Intelligence II Explain how genetic algorithms differ from conventional mathematical methods for optimisation. [10 marks] What are the advantages and disadvantages of genetic algorithms? [10 marks] 9 Database Topics The Relational Model of Data and its associated Data Manipulation Languages contained no provision for handling sets of tuples. Discuss the extent to which the SQL GROUP BY clause overcomes this weakness. [4 marks] The Nested Relational Model attacks the problem by extending the Data Definition Language that specifies a relational schema. Describe the extension, and explain with the aid of examples how it enables both sets and compound values to be represented. [7 marks] Explain how aggregates are handled in the Functional Data Model and the Data Language DAPLEX. [6 marks] In what way can the purging of duplicates cause problems when evaluating functions defined over sets? How does DAPLEX allow the programmer to retain duplicates when they are needed? [3 marks] 5 [TURN OVER CST.94.9.6 10 Numerical Analysis II Apply the Newton-Raphson formula xn+1 = xn ? f(xn) f 0 (xn) for solving the equation f(x) = 0 using f(x) = x ? 1 2 e 1?x 2 . Simplify your formula so that the exponential function need be called only once per iteration. [4 marks] This function has a zero at approximately 0.76. Use x0 = 1 and perform one Newton-Raphson iteration to calculate x1 and verify that this is a good starting value. Now use x0 = ?1/ ? 2 and re-calculate x1. (You may assume for this purpose: ? 2 ‘ 1.4, 1/ ? 2 ‘ 0.71, ? e ‘ 1.6, 1/ ? e ‘ 0.61.) [3 marks] By sketching the graph of f(x), or otherwise, explain these results. [4 marks] Perform two Newton-Raphson iterations (in exact arithmetic) for the function f(x) = x ? 1/(x + 1), with x0 = 1. Suppose that the second iteration is modified as follows: x2 = x1 ? f(x1) f 0 (x0) . Examine |x2 ? x2|/|x2| to estimate the relative loss of accuracy if the modified method is used. [5 marks] Although x2 is obviously less accurate than x2 in general, explain briefly why this modified Newton method is more useful for an n-dimensional problem. [4 marks] 11 Specification and Verification of Hardware Discuss the problems of providing tractable models of transistors suitable for hardware verification by formal proof. Compare and contrast at least two different models. Illustrate your discussion with concrete examples of transistor circuits. [20 marks] 6 CST.94.9.7 12 Semantics of Programming Languages State the Tarski-Knaster fixed-point theorem. Give a brief justification for the importance of the fixed-point theorem in denotational semantics. [8 marks] Prove that the least fixed-point operator fix is a continuous function. You may assume the following result: Let hD, vi be a complete partial order. Every doubly-increasing chain hdij ii,j?? in D (i.e. for any i, j, i0 , j0 in ?, if i 6 i 0 and j 6 j 0 then dij v di 0j 0 ) has a least upper bound l. Further, l = G i?? G j?? dij = G j?? G i?? dij = G k?? dkk [12 marks] 13 Types Describe the types and terms of the second-order lambda calculus (?2) and define the type assignment relation for ?2. [5 marks] Are the following expressions typeable in ?2? Justify your answer in each case. L = ??.??.?x : ?.??.?f : ? ? ?.?g : ? ? ?.fx R = ??.??.?y : ?.??.?f : ? ? ?.?g : ? ? ?.gy S = ??.?x : ?.x(x?) [5 marks] Find a type ? that makes the following expression typeable in ?2 and give, with justification, the type of C. C = ??.??.??.?f : ? ? ?.?g : ? ? ?.?z : ?.(z?f)g [5 marks] Explain what is meant by ?-reduction and ?-normal form for ?2 terms. Calculate the ?-normal form of the term C???fg(L??M) where C and L are as above, ?, ?, ? are type variables, f, g are identifiers, and M is a term in ?-normal form with no free identifiers or free type variables. [5 marks] 14 Computational Number Theory Describe the elliptic curve method for factorising integers. [7 marks] Derive an estimate, using a heuristic argument, for the expected running time of this method. [13 marks]Write short notes explaining the following: (a) hard-wired control of a CPU [6 marks] (b) asynchronous operation of a bus [7 marks] (c) delayed branching in a pipelined RISC processor [7 marks] 3 Digital Communication I Define the term flow control. [5 marks] How does it differ from congestion control? [3 marks] What is meant by the terms entry level, hop by hop and end to end flow control? When is each appropriate? [8 marks] Sketch the design of a simple flow control protocol. [4 marks] 1 [TURN OVER CST.94.13.2 4 Graphics Discuss transformations applied to 3D wireframe objects. [12 marks] Discuss the use of homogeneous coordinate representations (a) for presenting concepts [4 marks] (b) within programs [4 marks] 5 Programming in C Write a program in C which can solve cryptarithmetic puzzles in the format of the sum of two words. For example, given the input SEND +MORE MONEY the program would output 9567 +1085 10652 N.B. Each letter represents a different digit. [20 marks] 6 Programming Language Compilation Discuss two possible strategies that you might use to translate the abstract syntax tree corresponding to an integer expression composed of simple variables, integer constants and the usual integer operators +, ?, ? and / into reasonable quality code for a machine with eight general-purpose registers. You should pay particular attention to how you would control the allocation of registers and anonymous store locations, and you should outline what optimisations are convenient to perform. [20 marks] 7 Artificial Intelligence II Explain how genetic algorithms differ from conventional mathematical methods for optimisation. [10 marks] What are the advantages and disadvantages of genetic algorithms? [10 marks] 2 CST.94.13.3 8 Databases Describe how a data model is represented in a relational database, and explain how one might specify a relational database schema. [5 marks] What is meant by a referential integrity constraint in a relational database? [3 marks] Each year the number of tourists coming to Cambridge increases by 10%. Most of the pressure falls on a limited number of identified sites in the city centre. The Tourist Board has restricted the size of any group visiting such a site to 20, and requires a group of ten people or more to get a permit in advance. Most bookings are made either by tour operators or directly by independent guides: the Tourist Board will arrange guides for groups if asked to do so. A database is being installed to coordinate bookings and to provide information about the opening times of sites. Each site has separate opening times for summer and winter (owing to college autonomy, changes of season differ from site to site). Permits are issued to start on the hour or on the half-hour: they are valid either for 1 hour or for 2 hours, the duration being fixed for each site. The final permits of each day are timed to expire at the site’s closing time. Each site has a fixed capacity, and no booking can be accepted that would cause it to be exceeded. The charge for a permit depends only on the site and the season. (Occasionally sites are closed for several hours during the normal opening period, for example when recording is taking place in King’s College Chapel. The protocol is to inform the Tourist Board at least 6 months in advance.) The Tourist Board issues permits to visit an identified site at a given time on a given day, specifying the booking agent and the number in the group. Bookings can be made up to 6 months beforehand. Permits are issued to registered tour operators and guides on account, but in all other cases payment must be made in advance. The data held for registered guides includes not only account details but also their working hours and charges. Design a schema for the relational database that is to record this information for the Tourist Board. You may find it helpful to use domain types DATE, TIME and MONEY in addition to standard programming language datatypes. You do not need to specify the transactions that maintain the database, but you should state clearly any assumptions that influence the schema design. [12 marks] 3 [TURN OVER CST.94.13.4 9 Specification and Verification of Hardware Discuss the problems of providing tractable models of transistors suitable for hardware verification by formal proof. Compare and contrast at least two different models. Illustrate your discussion with concrete examples of transistor circuits. [20 marks] 10 Complexity For each of the following statements state whether the claim made is true, false or if more information is needed before a judgement can be made. Give one-sentence justifications of your assertions. (a) Sorting a list of numbers into ascending order is an NP problem. (b) Sorting a collection of programs into order so that the ones that finish quickly come before those that run for a long time is an NP-complete problem. (c) To be NP-complete is to be as difficult as any solvable problem can be. (d) Any NP problem can be solved (on an ordinary computer) in polynomial space and exponential time. (e) The problem of determining whether a k-clique is present in a graph is known to be NP-complete. Therefore for large graphs and large values of k it will always be impossible (in practice) to find such a clique even if it is known that one exists. (f ) For the purposes of complexity theory each of the cost functions n log n, n 1.573 and n! counts as polynomial growth. [20 marks] 11 Computation Theory Explain Turing’s Thesis. [5 marks] (a) What is meant by saying that a Turing machine has searching states? Show that any Turing machine computation can be effected by a machine with searching states, equivalent in the sense that the head movements are identical and the same symbols are written to the tape. [5 marks] (b) Show that, subject to suitable encoding, any computation can be carried out by a Turing machine having only two states. [10 marks] 4 CST.94.13.5 12 Professional Practice and Ethics Discuss the relations among the following concepts: (a) secrecy (b) confidentiality (c) anonymity (d) control of personal information (e) privacySemiconductor technology has made impressive progress in recent years. Write short notes about (a) the factors contributing to this progress [10 marks] (b) the prospects for its continuation for, say, a further 10 years [5 marks] Are there signs that devices in the near future could/should exploit different principles from those of today? [5 marks] 2 Additional Topics I and II Define a Hamming Code and show how it can correct a single error. [3+3 marks] Show how, by using an extra parity bit, it can detect a double error. [3 marks] Give an example of a convolutional code. [5 marks] Given a BCH code (1023, 983), which errors can it correct? [2 marks] Give an example where a run length code is better than a Huffman Code. [4 marks] 1 [TURN OVER CST.94.7.2 3 Computer Systems Modelling Consider a system with two independent server devices, which have FIFO queues, and two distinct customers. All service times are exponentially distributed but the service time distributions for the customers and devices differ; that is, there are four distinct service rates, one for each customer at each device. (a) Draw the state diagram of a Markov chain representing the system. [8 marks] (b) If all the service rates are equal then the system corresponds to our notion of a balanced system. Show that under these conditions the utilisation of each device is given by U = N N + K ? 1 where N is the number of customers and K is the number of devices. [6 marks] (c) Show that this expression also holds in a system with three indistinguishable customers and two devices with identically exponentially distributed service times. [6 marks] 4 Digital Communication II Two Ethernets can be interconnected using a bridge, which forwards packets between the networks at the OSI Datalink layer. Describe the operation of an Ethernet bridge. [7 marks] In a network composed of several bridged Ethernets joined in an arbitrary topology, describe how the problem posed by multiple alternative paths is solved. [8 marks] As the number of connected systems gets large, how can the performance of the packet forwarding in such a network be improved by use of suitable hardware and/or software? [5 marks] 5 Philosophy Discuss the relation between mind and body. [20 marks] 2 CST.94.7.3 6 Algebraic Manipulation Write short notes on the use of remainder sequences in each of the following contexts: (a) finding the GCD of two polynomials (b) eliminating a variable between two polynomial equations (c) counting and isolating the roots of a univariate polynomial equation (d) solving the equation Ax + By = C to find x and y (where A, B, C, x and y are integers) [20 marks] 7 Natural Language Processing Discuss some of the methods used by current NLP systems to carry out (a) morphological analysis [6 marks] (b) parsing [6 marks] (c) semantic interpretation [8 marks] Illustrate your answer by suggesting appropriate representations, and how to construct them, for the following sentence: Every borrower repaid his loan from Cambank. 8 Computational Neuroscience Explain the following methods for updating the weights in associative networks: (a) the Hebbian rule [5 marks] (b) the Delta Rule (or LMS or Widrow-Hoff rule) [5 marks] (c) the rule used by Kohonen feature maps [5 marks] What are the advantages and disadvantages of each? [5 marks] 3 [TURN OVER CST.94.7.4 9 Optimising Compilers Consider the following ANSI C routine: struct List { int hd; struct List *tl; }; struct List *readlist() { int i; struct List *p, *q, *t; l1: p = 0; l2: while (scanf(“%d”, &i) == 1) { l3: t = malloc(sizeof(List)); if (t == 0) abort(); t->hd = i; l4: t->tl = 0; if (p == 0) p = q = t; else q->tl = t, q = t; } l5: return p; } Summarise its function. [4 marks] Sketch an algorithm which computes liveness of variables. [6 marks] Calculate the sets of (local) variables which are live at l1, l2, l3, l4 and l5. [4 marks] Do any of p, q, t and i have dataflow anomalies? Briefly justify your answer indicating which anomalies may represent potential faults. [6 marks] 4 CST.94.7.5 10 Numerical Analysis II Explain the terms Riemann integral and Riemann sum. [3 marks] Let R be a quadrature rule that integrates constants exactly. If a function f is bounded and Riemann-integrable over the interval [a, b] then prove that limn?? (n × R)f = Z b a f(x)dx. [6 marks] Consider two quadrature rules for the interval [??, ?]: Sf = ? 3 {f(??) + 4f(0) + f(?)} ? ? 5 90 f (4)(?) Tf = ?{f(??) + f(?)} ? 2 3 ? 3 f 00(?) If S were used in the composite form (n × S)f, what order of convergence would you expect? [2 marks] Suppose the rule 1 3 {F(?1, ?1) + 4F(?1, 0) + F(?1, 1) + F(1, ?1) + 4F(1, 0) + F(1, 1)} is applied to Z 1 ?1 Z 1 ?1 F(x, y) dxdy. Describe the 2-variable polynomials that are integrated exactly by this rule. [6 marks] Why is the product form of Sf unsuitable for integrating over a hypercube in 20 dimensions? Name a better method for 20 dimensions on a sequential machine, given that high accuracy is not required. [3 marks] 5 [TURN OVER CST.94.7.6 11 Proving Programs Correct Describe the role of first-order predicate calculus in Floyd-Hoare logic. [5 marks] Give an outline of a deductive system for predicate calculus, covering at least the following topics: (a) terms, formulae and sequents [5 marks] (b) introduction versus elimination rules [5 marks] (c) side conditions and variable capture [5 marks] Illustrate your explanations with examples. 12 Computational Number Theory Describe how the set of composite numbers can be recognised in Random Polynomial time. [12 marks] Describe how the set of prime numbers can be recognised in Non-deterministic Polynomial time. [8 marks] 6 CST.94.7.7 13 Semantics of Programming Languages Dijkstra proposed the language of guarded commands with the following syntax. Commands take the form c ::= skip | abort | X := e | c; c | if gc fi | do gc od where e is an arithmetic expression and gc stands for a guarded command of the form b1 ? c1 [] b2 ? c2 for boolean expressions b1 and b2, called guards, and commands c1 and c2. Execution of the command skip does not result in a change of state. Following Dijkstra’s intentions, if no guard evaluates to true at a state, then the guarded command is said to fail, in which case, the guarded command does not yield a final state. Otherwise, the guarded command executes as one of the commands ci whose associated guard bi evaluates to true. The execution of the command abort does not yield a final state from any initial state. The command if gc fi executes as the guarded command gc, if gc does not fail, otherwise, it acts like abort. The command do gc od executes repeatedly as the guarded command gc, while gc continues not to fail, and terminates when gc fails. (a) Assume that boolean and arithmetic expressions have no side effects and always terminate, and that the rules for their evaluation are given. Write down a collection of rules for an inductively defined evaluation relation of the form c, S ? S 0 whose sense is “starting from the initial state S, the evaluation of the command c terminates at the final state S 0 .” [10 marks] (b) Give the commands in Dijkstra’s guarded language which simulate the standard imperative programming commands if b then c1 else c2 and while b do c respectively. You may assume that if b is a boolean expression, then so is ¬b, the negation of b. [2 marks] (c) Give an appropriate definition of semantic equivalence of commands with respect to the evaluation relation defined in (a). Prove that for any boolean expression b and any command c, the command do b ? c [] b ? c od is semantically equivalent to the command if b ? (c; do b ? c [] b ? c od) [] ¬b ? skip fi [8 marks] 7 [TURN OVER CST.94.7.8 14 Concurrency Define what is meant by observational equivalence of CCS agents. [5 marks] A transmitter T, transmission medium M, and receiver R are modelled by CCS agents with the following definitions: T def = in.i.T0 T 0 def = r.i.T0 + a.T M def = i.M0 M0 def = o.M + ?.r.M R def = o.out.a.R M is an unreliable medium: having received an input message from T (action i) it either outputs the message to R (action o), or loses it (represented by the ? action) and then sends a request for retransmission (action r). If R does receive the message, after broadcasting it (action out) it sends an acknowledgement directly to T (action a).Describe in detail the use of the bilinear transformation s ? 2 T z ? 1 z + 1 for the design of digital filters from analogue filters. Discuss the advantages and disadvantages of the method. [8 marks] It is required to design a second order maximally flat digital low-pass filter having a 3dB cut-off frequency of 0.2fs where fs is the sampling frequency. The design is to be based on the analogue Butterworth filter defined by: |H(j?)| 2 = 1 1 + ? ?c 2N where N is the filter order and ?c is the 3dB cut-off frequency. It can be shown that the s-domain transfer function for the second order Butterworth filter is given by: H(s) = 1 1 + ? 2 s ?c + s ?c 2 Calculate the coefficient values for the corresponding digital low-pass filter and draw its block diagram. [12 marks] 1 [TURN OVER CST.93.9.2 2 Digital Communication II Describe the Asynchronous Transfer Mode (ATM). [5 marks] What are the benefits and drawbacks of the choice of ATM over normal packet switching? [5 marks] An ATM switch can be built with a set of buffering input and output ports and an unbuffered interconnection network. Describe with examples the desirable attributes of such a network. [10 marks] 3 Computer System Modelling Consider a transaction system with 20 workstations and 4 fileservers, each with 2 discs. The system is monitored and it is found that, for each transaction, on average: 40 ms of workstation CPU is consumed 6 ms of fileserver CPU is consumed 10 ms of fileserver disc is consumed. The system is arranged so that asymmetry in disc access is limited to 3 : 2 from highest to lowest, as is fileserver-usage asymmetry. Workstation usage is balanced. Perform a bottleneck analysis of the system for throughput and response time. State any assumptions made. [10 marks] Give an estimate of the response time when the system is handling (a) 10 (b) 100 (c) 1000 transactions per second. Note: a balanced system with K devices and N customers has a utilisation U = N N + K ? 1 [10 marks] 2 CST.93.9.3 4 Graphics II Compare object-space and image-space visibility tests in synthesising an image for display. [12 marks] Describe one visibility test in detail. [8 marks] SECTION B 5 Designing Interactive Applications Explain the term user’s conceptual model. How is the user’s conceptual model formed? [4 marks] Describe Fitts’ law and Hick’s law and explain how each might influence the design of an information display. [4 marks] The receptionist at a small research laboratory is required to field incoming messages and make sure that they reach the recipient in a timely manner. Some messages arrive by word of mouth, others by phone, courier, e-mail or FAX. There are about 100 recipients, most of whom are researchers. They spend a large proportion of their time in meetings of one sort or another, some of which are held in offices, the remainder in conference rooms. The receptionist endeavours to avoid interrupting important meetings unnecessarily. It is proposed to build a system based upon Active Badge technology to improve message handling activities in the laboratory. Each member of staff wears an active badge. An existing Location Server provides client applications with up-to-date information about the location and movements of each active badge. Imagine you have to develop a requirements specification that might reasonably arise from your own investigations. Write down three or four key requirements. [2 marks] On one side of paper, draw up the screen layout for your proposed application and annotate it with the rationale for each key design decision. [10 marks] 3 [TURN OVER CST.93.9.4 6 Optimising Compilers Consider a flowgraph, containing 3-address instructions, which represents a sourcelevel routine. Let e be an expression (e may be considered to be a right-hand side 3-address instruction, i.e. either x or x op y where x and y are variables). We say that e is very busy at a node n if all paths from n compute the expression e at least once and each such computation yields the same value as evaluating e at n would (i.e. no modification of its variables occurs between n and the first occurrence of e on any path from n). Let V B(n) be the set of very busy expressions at n. (a) Give data flow equations for V B(n). [4 marks] (b) Give the relationship, if any, to the set Avail(n) of expressions available at n including the direction (forwards/backwards) of the analyses. Indicate whether either inclusion V B(n) ? Avail(n) or Avail(n) ? V B(n) holds. [4 marks] (c) Sketch an algorithm to compute V B(n), briefly commenting on any initialisation. [4 marks] Suppose now that we compile a program in a call-by-need functional language into 3-address code using closures (i.e. ?().e0 ) to represent laziness. Given a functional definition f(x, y, z) = e we have notions of f being strict in, or needing, its second parameter y. Point out similarities and differences between these notions and that of y (or y()) being very busy at some, to be determined, point in the 3-address code form of e. [8 marks] Hint: you may find it helpful to consider separately (a) a case where e uses only the conditional function and strict primitive functions such as + (b) a case such as f(x, y) = g(x, y + 1) 7 Artificial Intelligence II Discuss any two methods for computing information about the three-dimensional layout of surfaces in a scene, given one or more images of the scene. Illustrate your answer with appropriate mathematical relationships and fragments of computer programs. [20 marks] 4 CST.93.9.5 8 Database Topics Describe the differences between navigational and algebraic data manipulation. [6 marks] What problems would arise when incorporating an algebraic style of data manipulation into a persistent programming language such as PS-ALGOL? How might they be solved? [14 marks] SECTION C 9 Natural Language Processing Write on four of the following topics, describing the problems they raise and their significance for natural language processing. [5 marks each] (a) Worst-case (exponential) syntactic ambiguity (b) Semantic interpretation of embedded propositions (such as John thinks the prime minister is a grey man) (c) Focus and anaphoric reference (d) Unification as a technique for expressing syntactic rules (e) Defeasible reasoning for interpreting utterances (f ) Natural prosody for speech synthesis from text 5 [TURN OVER CST.93.9.6 10 Semantics Explain what is a well-founded binary relation, and state the principle of wellfounded induction. [3 marks] Show that the binary relation C on the integers which is given by m C n if and only if n < m 6 100 is well-founded. [2 marks] Consider the ML declarations fun f(x) = if x > 100 then (x ? 10) else f(f(x + 11)); fun g(x) = if x > 100 then (x ? 10) else 91; Prove, by induction on the well-founded relation C, that f and g determine equal integer-valued functions. Hint: for the induction step you may find it helpful to consider separately the cases x > 100, x = 100, 90 6 x < 100 and x < 90. [15 marks] 6 CST.93.9.7 11 Types Describe the relation of ?-reduction between expressions in the second order lambda calculus ?2. Explain the Church-Rosser and strong normalisation properties of this relation. How do they lead to a procedure for deciding whether two closed, typable ?2 expressionsWhat is meant by a load-store architecture? [2 marks] Show how a load-store architecture can be used as the basis for the design of a high performance processor by discussing the MIPS R2000/R3000. [18 marks] 2 Computer Structures Sketch the basic hardware components of a personal computer (PC). [4 marks] Describe how these components operate to maximise the performance of the machine. [10 marks] How would you expect the design to change as the CPU power, the memory size and the input/output bandwidth increase over the next few years? [6 marks] 3 Digital Communication I Describe briefly both Synchronous and Asynchronous Time Division Multiplexing (TDM). [4 marks] Describe four solutions to the problem of contention resolution in Asynchronous TDM. [12 marks] Which solution is adopted by Ethernet and what measures are taken to ensure stability in circumstances of high load? [4 marks] 1 [TURN OVER CST.93.5.2 4 Graphics I A certain image contains a number Q of differently coloured pixels. There are not enough different pixel values available to represent these and so a method of approximation is needed. Describe an approach and comment on its performance. [15+5 marks] SECTION B 5 Programming in C You have a C compiler which is ANSI conforming in all respects except that it has no facility for the definition, declaration or use of standard C structures. Outline a set of routines written in this language to provide a mechanism for handling structures. Your solution should contain the following: (a) function prototypes for each of the routines [10 marks] (b) a few sentences describing the behaviour of each function [10 marks] Note: no code other than the prototypes is required. 6 Programming Language Compilation Discuss the issues that must be considered when designing the calling sequence to be used for recursive procedures on a machine with several general-purpose central registers. Assume that the language allows procedures to be declared within other procedures and that procedures may be passed as arguments in calls. Pay particular attention to how arguments, local variables and free variables are accessed. [20 marks] 2 CST.93.5.3 7 Concurrent Systems Main Memory Persistent Memory type operations data object data object operation 1 operation 2 operation n The figure illustrates an object model which is used in a concurrent software system. We are concerned with how to implement atomic operations in the presence of concurrency and crashes. In the descriptions given below, the term client indicates an external user of the system. A single-machine multiprocessor implementation should be assumed. (a) A data object exists in main memory only. Invocations of its type operations involve no writes to persistent memory and no output to clients. Concurrent processes may invoke the object. How can the operations be made atomic? [8 marks] (b) A data object exists in persistent memory. (i) A single operation is invoked on it in response to a request from a client. The result of the invocation is output to the client. How can the operation be made atomic? [4 marks] (ii) A cl
