Consider Hoare triples of the form {T} V := E {V = E} where T is the atomic formula 'true' and V and E range over variables and expressions, respectively. (i) Write down an instance of such a triple that cannot be proved using Hoare logic and explain why not. [2 marks] (ii) Write down conditions on V and E such that {T} V := E {V = E} can be proved and give a proof of this assuming your conditions. [2 marks] (b) Write down and explain the weakest liberal precondition wlp(V := E, Q) and strongest postcondition sp(V := E, P). Comment on the relationship of these to the Hoare triple {P} V := E {Q}. [4 marks] (c) Explain briefly how both weakest preconditions and strongest postconditions are used in mechanised program verification. [4 marks] (d) Write down the Hoare assignment axiom and the Floyd assignment axiom. Explain carefully why each is true. (e) Show how the Floyd assignment axiom can be derived from the Hoare assignment axiom and the other standard rules of Hoare logic.

What relation should hold between two of these quantities to provide sensible behaviour and why? [5 marks] Comment on the possibility and desirability of negative hold times. [2 marks] Each of the following boolean functions is a function of the four variables w, x, y, z. The functions are not totally specified and may take on any value for certain inputs. fn indicates where the function must be true, while gn is true where the value of the function is not constrained. Draw maps and provide a minimum sum of products form for each of the functions. (a) f1 = wxyz + wxyz + wxyz + wxyz + wxyz + wxyz g1 = wxy z + wxyz (b) f2 = wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz g2 = wxy z + wxyz [5 marks] Let f(x0, x1, . . . , xn1) be equal to 1 if and only if exactly k of the variables have the value 1. How many prime implicants does this function have? [5 marks] 4 CST.99.2.5 SECTION C 4 Probability A B Each of the five switches in the above circuit is closed with probability p, independently of all the other switches. What is the probability of there being a connection from A to B? Express the answer as a polynomial in p. [7 marks] The circuit is then modified to the version shown below, the five switches still being independent. What is the probability of there being a connection from A to B now? Again express the answer as a polynomial in p. [13 marks] A B 5 Probability A solitaire game is played with two coins. One coin is fair, so that P(heads) = 1 2 , and the other is biased so that P(heads) = p. At the first turn the player tosses the fair coin. At all subsequent turns the biased coin is used if the toss at the previous turn resulted in heads and the fair coin is used if the toss at the previous turn resulted in tails. Suppose un is the probability of obtaining heads at turn n. Show that, for n > 1: 2un + (1 2p)un1 = 1 [4 marks] Demonstrate that this difference equation also holds for the case n = 1 provided u0 is suitably defined. [2 marks] Solve the difference equation, expressing un in terms of n and p. [14 marks] 5 [TURN OVER CST.99.2.6 SECTION D 6 Professional Practice and Ethics What is the nature of privacy and how do EU guidelines and/or British legislation serve to protect privacy? [20 marks] 7 Regular Languages and Finite Automata Suppose that L is a language over the alphabet {0, 1}. Let L 0 consist of all strings u 0 over {0, 1} with the property that there is some string u L with the same length as u 0 and differing from u 0 in at most one position in the string. Show that if L is regular, then so is L 0 . [Hint: if Q is the set of states of some finite automaton accepting L, construct a non-deterministic automaton accepting L 0 with states Q {0, 1}, where the second component counts how many differences have been seen so far.] [10 marks] If a deterministic finite automaton M accepts any string at all, it accepts one whose length is less than the number of states in M. Explain why. [5 marks] State Kleene's theorem about regular expressions and deterministic finite automata. [2 marks] Describe how to decide for any given regular expression whether or not there is a string that matches it. [3 marks] 8 Software Engineering I State the advantages of the waterfall model. [10 marks] State the disadvantages of the waterfall model. [4 marks] What is the main criterion for deciding whether or not to use the waterfall model in a software development project? [3 marks] Explain whether there would be any difference for a hardware development project. [3 marks] 6 CST.99.2.7 9 Software Engineering II A Web browser is a complicated program. It must deal with many types of data (images, sound, etc.), support various network services and handle the many constructs of HTML (the language in which Web pages are written). Your manager asks you to lead a small group of programmers in implementing a Web browser. Describe top-down refinement; is it appropriate for your task? Your manager further states that it is essential that your browser should almost never crash. How would you go about meeting this requirement? [6 marks] Consider the following two ML functions: fun sumfiv [] = 0 | sumfiv (x::xs) = 5*x + sumfiv xs; fun summing z [] = z | summing z (x::xs) = summing (z + x) xs; Use structural induction to prove that sumfiv xs can be replaced by 5 * summing 0 xs. [8 marks] 10 Structured Hardware Design A design is required for an electronic system to collect votes from the audience in a television game show. Each of up to 1000 seats in the audience will have an audience station and there will be a master station for the floor manager. Output from the system will be video and this will feed monitor displays in the studio and be included in the broadcast programme. (a) Sketch a block diagram of the overall system, showing clearly the various units and the signals which make up the cables which run between them. [5 marks] (b) Specify the controls and indicators on the front panel of the two types of station. Give a pair of state diagrams of the system, one as seen by the audience and the other as seen by the floor manager. [5 marks] (c) Given that a profitable return on the sale of three complete systems is required, describe the components and technology that should be used in the units. [5 marks] (d) Discuss the advantages and disadvantages of including a PC inside the floor manager's station, in terms of cost, ease of use and whether a custom or standard operating system should be used.

The RSA cryptosystem can be tuned to make the workload asymmetric: with d = 3, encryption (cubing modulo n) becomes very cheap and almost all the computational expense shifts to decryption (extracting cubic roots modulo n). The following public-key protocol uses the above property to allow two principals A and B to establish a common secret key Nb (invented by B) without incurring a high computational load, thanks to the help of a server S who computes all the cubic roots in the protocol. Attackers are assumed to be able to overhear, but not alter, the messages between A, B and S. A S : B, N3 a mod n. S B : A. B S : A, N3 b mod n. S A : B, Na Nb. (a) What is the purpose of Na? [3 marks] (b) Describe in detail a protocol attack that will allow two colluding attackers C and D to recover Nb. Assume that S is stateless. [7 marks] (c) Stop the attack you described in (b) by making S stateful. [3 marks] (d) Describe in detail a more sophisticated protocol attack whereby the colluding attackers will recover Nb even if S adopts the precaution you described in (c). [4 marks] (e) Fix the protocol to defeat the attack you described in (d). [3 marks] 13 (TURN OVER) CST.2012.7.14 13 Temporal Logic and Model Checking In the following program, called INC, (*) is a Boolean expression that evaluates non-deterministically to either true or false each time it is evaluated (different evaluations may yield different results). N := 1; WHILE (*) DO N := N+1; N := 0; (a) Devise and carefully describe a state space and transition relation to model this program. [8 marks] (b) Devise temporal logic formulae that express properties (i), (ii) and (iii) below. In each case state which temporal logic you are using and explain whether the property is true in your model. (i) Every execution of INC terminates. [4 marks] (ii) Some execution of INC terminates. [4 marks] (iii) If INC terminates, then N = 0 holds in the terminating state. [4 marks] 14 CST.2012.7.15 14 Topical Issues (a) Describe the operating principles of RFID systems based on capacitive, inductive and backscatter coupling. Give typical operating ranges and at least one example application for each. [9 marks] (b) Electronic passports contain RFID chips to permit electronic transfer of biometric data to a reader. The systems in use today use remote-coupling with an operating frequency of 13.56 MHz. The full communication protocol varies, but every transmission from the passport is prefaced with a numeric identifier (UID). (i) The first implementations used a static UID unique to each passport, whilst later implementations generated a new pseudo-random UID for each round of communications. Outline the risks and practicalities of each approach. [3 marks] (ii) Biometric data are usually encrypted when sent between reader and tag using a protocol known as Basic Access Control (BAC). The shared session key is generated solely from the owner's passport number (9 digits), passport expiry date and date of birth. These data must be read optically by swiping the passport through a desktop device before proceeding. Comment on the security of this system and the choice of 13.56 MHz RFID in such a context. [4 marks] (iii) Most authorities now line the passport sleeve with metal foil. Explain how this increases security and discuss the extent to which it does so.

A permutation of a list is any list that can be derived from it by re-arranging the elements. Write an ML function that returns the list of all the permutations of its argument. Explain your code clearly and carefully. For example, applied to the list [1,2,3], your function should return the list whose elements are [1,2,3], [2,1,3], [2,3,1], [1,3,2], [3,1,2] and [3,2,1]. You may assume that the elements of the argument are distinct. The elements of the result may appear in any order. [10 marks] 2 Discrete Mathematics Let Mn = 2n 1 be the n th Mersenne number. Show that Mn can be prime only if n is. [5 marks] Let m = m(m + 1)/2 be the mth triangular number and recall that a perfect number is one equal to the sum of its factors (including 1 but excluding the number itself). Suppose that p = Mn is prime. Show that p is a perfect number.

In a large project it is possible that two programmers, working on different parts of the code, happen to select the same name for something that they define. If this accident leads to some third programmer accessing the wrong one of these two versions the results could be unsatisfactory. Explain the steps that the designers of the Java language have taken to reduce the probability of such clashes. [10 marks] 4 Operating Systems An operating system uses a single queue round-robin scheduling algorithm for all processes. You are told that a quantum of three time units is used. What can you infer about the scheduling algorithm? [1 mark] Why is this sort of algorithm suitable for a multi-user operating system? [1 mark] The following processes are to be scheduled by the operating system. Required Process Creation Time Computing Time P1 0 9 P2 1 4 P3 7 2 None of the processes ever blocks. New processes are added to the tail of the queue and do not disrupt the currently running process. Assuming context switches are instantaneous, determine the response time for each process. [6 marks] Give one advantage and one disadvantage of using a small quantum. [2 marks]

Write program that will read data from a file. The program will allow the user to specify the filename. Use a loop that will check if the file is opened correctly, otherwise display an error message and allow the user to re-enter a filename until successful.

In the Discrete Mathematics course you learned that RSA encryption involved having a public key (N, e) where N is the product of two secret primes P and Q and e is an exponent. To encrypt a message that is represented by a number m you just compute me mod N. The Java BigInteger class contains (among others) methods called add, subtract, multiply, divide and remainder. The class String has a method charAt that allows you to extract a character at a given position, and length to tell you how long the string is. Casting a character to an integer yields its character code. Supposing you are given a BigInteger that represents N and an integer for e, and not using any built-in Java methods for raising numbers to powers, write code that (a) takes a string and encodes it as an integer; if the string contains characters c0, c1 . . . the integer required will be c0 + Kc1 + K2 c2 + with the constant K set to 216 so that the full Unicode character set can be accommodated; [7 marks] (b) encodes this number (assuming it is less than N) using the RSA method;

Programming languages are usually compiled into the machine code of the target computer, but sometimes an interpretive system is used. Discuss the relative merits of these two approaches. [7 marks] Outline the key features of the design of an interpretive code that would be suitable for an implementation of the C programming language and describe the overall structure of an interpreter for it. [7 marks] What techniques could be used to improve (a) the space efficiency, and (b) the time efficiency of interpretive codes? [6 marks] 8 Prolog for Artificial Intelligence Describe how lists that are represented by difference lists may be concatenated (or "appended") in constant time. [6 marks] Define a procedure rotate(X,Y) where both X and Y are represented by difference lists, and Y is formed by rotating X to the left by one element. [14 marks] 3 [TURN OVER CST.96.13.4 9 Databases The international conference Extending Data Base Technology has arranged its next meeting in Avignon at the end of March, to coincide with the spring migration through the Camargue. Birders expect to add significant new sightings to the list of birds seen during a major database conference. Delegates have been arguing for over a decade about the best relational model for the data. It is agreed that the following information should be recorded: the names of the major avifaunal regions: nearctic, western palarctic, Australasia etc. for each birding delegate, a level of competence on a scale [1..5] within each avifaunal region good bird sites within each region (including all those visited during conferences), specifying the various habitat types occurring within each site observations made - by an observer, on a date, in a habitat type at some site, of a species belonging to a particular family of birds Advise the delegates on a suitable relational schema for this database. [16 marks] Explain what would be involved in processing the following queries in SQL. (a) What species of the kingfisher family have been observed both in a waterside habitat and in arid grassland? [2 marks] (b) Which delegate is recorded as having observed the greatest number of distinct species? [2 marks] 10 Natural Language Processing Describe three significant differences between programming languages and natural languages. [8 marks] What problems do these differences pose for attempts to construct programs that "understand" a natural language? [12 marks] 4 CST.96.13.5 11 Introduction to Functional Programming Give a short explanation (illustrated with examples) of each of the following features of ML: (a) higher order functions [4 marks] (b) polymorphism [4 marks] (c) datatypes [4 marks] (d) pattern matching [4 marks] (e) exceptions [4 marks] 12 Computer Vision Using appropriate mathematical expressions, define the following operations commonly used in computer vision and briefly explain their function and applications: (a) convolution [4 marks] (b) correlation [4 marks] (c) bandpass filtering [4 marks] (d) edge detection by second-derivative zero-crossings [4 marks] (e) invariant transform [4 marks] 13 Complexity Theory One version of the algorithm that uses discrete Fourier Transforms when multiplying integers uses modular arithmetic for much of its internal working. The modulus involved will be chosen to be one greater than a power of two. Explain why this is the case, what power of two is involved, how this relates to the number of digits in the numbers being multiplied and how the basic operations of modular arithmetic are performed. Does it matter that the modulus used is usually not a prime number?

kindly answer all the questions