Consider the task of normalising sum expressions. For example, the sums (a + b) + (c + d) and (a + (b + (c + d))) may be normalised into a standard form that is left associative: a+b+c+d or equivalently ((a+b) +c) +d. Write a Prolog procedure to define predicate normsum such that the goal normsum(X,Y) succeeds when the sum expression X normalises to Y. Procedures not using the technique of difference structures will not receive full marks. [20 marks] 9 Running a Business Explain the difference between a profit and loss account and a cash-flow statement. Under what circumstances would they show the same figures? [5 marks] A small software company is offered a development contract, valued at 100,000 (excluding VAT), with 10% to be paid at the start of the contract, 30% invoiced at the first milestone (estimated after 3 months), 50% invoiced on completion, with 10% to be retained for 3 months after completion, as a guarantee against errors. The company estimates that the project will require 6 months' work from each of two staff, whose annual salary costs are 36,000 and 24,000 respectively. Other overheads are approximately 120% of salary costs. Draw up an outline monthly profit and loss account and cash-flow statement for the project, ignoring VAT and bank interest. Salary and overheads are charged to the project only while the programmers are actually working on it. [5 marks] What is the eventual profit the company expects to make, if it undertakes the project, and how much working capital will the project require? The effort in the project turns out to be underestimated, and the company delivers the first milestone 1 month late, and completes 2 months late compared with the original schedule, requiring both programmers to work for the extra 2 months. How has this affected the profitability and working capital requirement? [5 marks] 5 [TURN OVER CST.95.9.6 10 Natural Language Processing Imagine you were to construct a natural language processing system for solving syllogisms expressed in English, behaving approximately as indicated: User: All men are mortal. System: OK User: Socrates is a man. System: OK User: Is Socrates mortal? System: Yes Describe the components of such a system and how they would fit together. [20 marks] 11 Computer Systems Modelling In queueing networks, what is meant by a closed system? [4 marks] Consider two closed systems. One has two devices, A and B, and three customers, the other three devices, A, B and C, and two customers. Both have exponentially distributed service times which are device dependent but customer independent. In the first system a customer completing service at a device always moves to the other device. In the second system a customer completing service moves to one of the other two devices with equal probability. Draw state diagrams for the Markov chains representing these systems. Choose one system to solve for device utilisation in terms of service rates. [10 marks] For the chosen system, when the service rates are equal does the utilisation of each device correspond to that for a balanced system (U = N N+K1 where N is the number of customers and K the number of devices)? [3 marks] Describe the state space for a Markov chain for one of the systems if the service rates were both customer and server dependent. [3 marks] 6 CST.95.9.7 12 Types Consider the following datatype and function declarations in Standard ML: datatype tree = Leaf | Node of tree * tree ; fun iter x f Leaf = x | iter x f (Node(y,z)) = f(iter x f y)(iter x f z) ; You are required to encode the datatype tree as a closed type in the second-order lambda calculus, 2. Find a suitable type and closed 2 terms in -normal form, L, N, and I say, corresponding to Leaf, Node and iter respectively. You should demonstrate for your choices that ` L : ` N : ` I : . ( ) are derivable typing assertions, and that IxfL and Ixf(Nyz) are -convertible to the 2 terms corresponding respectively to the right-hand sides of the clauses in the declaration of iter. [14 marks] Now add to the above Standard ML declarations the function declarations fun rev Leaf = Leaf | rev (Node(y,z)) = Node(rev z, rev y) ; fun div Leaf = Leaf | div (Node(y,z)) = div(Node(z,y)) ; Using I, or otherwise, show that there is a closed 2 term of type , R say, for which RL and R(Nyz) are -convertible to the 2 terms corresponding respectively to the right-hand sides of the clauses in the declaration of rev. Is there a closed 2 term D with similar properties for the declaration of div?