Describe the structure of a discrete event simulator. What is the principal data structure involved? [5 marks] (c) A queueing network is characterised by a set of visit counts, Vi , and per-visit service requirements, Si , for each of N devices. Derive upper bounds on the system throughput (i) when the load is very low and (ii) as the load tends to infinity. [5 marks] Systems involving hundreds of millions of lines of code can thus be expected to contain tens of thousands of potentially catastrophic errors. (a) List several kinds of programming errors that can appear in programs and discuss their relative importance in relation to the long-term reliability of a large application program. [7 marks] (b) Suggest potential ways by which programmers may reduce the number of programming errors they make, paying particular attention to language features that might help, extra features in program development systems and possible changes in overall system architecture. [8 marks] (c) In what ways would you expect languages 25 years from now to differ from those that are currently popular? [5 marks] 8 Databases (a) Define the core operators of the relational algebra. [5 marks] (b) Describe two differences and two similarities between the relational algebra and SQL. [4 marks] (c) Suppose that S(a, b, . . .) and R(a, . . .) are relations (the notation indicates that attribute a is in the schema of both S and R, while attribute b is only in the schema of S). Suppose that v is a value; is the following equation always valid? (a=v or b=v) (R ./ S) = (a=v(R)) ./ (b=v(S)) If yes, provide a short proof. If no, provide a counter-example. [2 marks] (d) Various normal forms are important in relational schema design. (i) Define Third Normal Form (3NF). [3 marks] (ii) Define Boyce-Codd Normal Form (BCNF). [3 marks] (iii) For databases with many concurrent update transactions, explain why schemas in normal form are important for good performance. (a) In order to prove the following formula by resolution, what set of clauses should be submitted to the prover? Justify your answer briefly. x [P(x) Q R(x)] x [(Q S(x)) (P(x) R(x))] x S(x) [7 marks] (b) Derive the empty clause using resolution with the following set of clauses, or give convincing reasons why it cannot be derived. {P(x, x)} {P(x, f(x))} {P(x, y), P(y, z), P(x, z)} [6 marks] If a continuous signal is discretely sampled by multiplying it with a sequence of uniformly-spaced Dirac delta functions, having frequency fs, what happens to the Fourier spectrum of the signal? [3 marks] (b) What is the conditional probability p(x|y), the probability of event x given that event y has occurred, provided that we know the following? p(x), the unconditional probability of event x p(y), the unconditional probability of event y p(y|x), the probability of event y given that event x has occurred [3 marks] (c) Consider a binary symmetric communication channel, whose input source is the alphabet X = {0, 1} with probabilities {0.5, 0.5}; whose output alphabet is Y = {0, 1}; and whose channel matrix is 1 1 where is the probability of transmission error. (i) What is the entropy of the source, H(X)? [1 mark]