Explain informally the difference between Godel's completeness theorem and his first incompleteness theorem. [8 marks] (b) State the meaning of Hoare triples {P} C {Q} in separation logic. [3 marks] (c) For each Hoare triple (i), (ii) and (iii) below state whether the triple is true. Explain your answer and if the triple is true give a proof using separation logic. You may assume `P if P is a true separation statement (e.g. ` X 7 0 X 7 ). Such assumed statements should be stated explicitly and informally justified. (i) {X = 0} [X] :=1 {0 7 1} (ii) {X .= 0} [X] := .= 0 X 7 0} [X] :=1 {0 7 1}

Consider the following C-like language, tinyC. It has locally-scoped mutable variables, and functions that take a single argument. Its operational semantics is defined as a transition system over configurations he, E, si where E is an environment {x1 7 n1, .. , xj 7 nj }, mapping the variable names currently in scope to their addresses, and s is a store {n1 7 v1, .. , nk 7 vk}, mapping each currently allocated address to either an integer n or undef. In this question n ranges over 0 . . . 2 631. Programs p consist of finite sets of definitions with distinct names. expression, e ::= n | x | x=e 0 | { int x ; e} | e1; e2 | f (e) | undef | kill x definition, d ::= int f (int x ){e} E(x )=n s(n)=n 0 hx , E, si hn 0 , E, si deref E(x )=n n dom (s) hkill x , E, si h0, E\x , s i kill he, E, si he 0 , E 0 , s 0 i hx=e, E, si hx=e 0 , E0 , s 0i as1 E(x )=n s(n)=v hx=n 0 , E, si hn 0 , E, s + [n 7 n 0 ]i as2 x 6 dom (E) n 6 dom (s) n 0 < n. n0 6 dom(s) h{ int x ; e}, E, si he; kill x , E + [x 7 n], s + [n 7 undef]i local he1, E, si he 0 1 , E 0 , s 0 i he1; e2, E, si he 0 1 ; int f (int x ){e} p hf (n), E, si h{ int x ; (x=n; e)}, E, si cl2 (a) For the configuration hg(3), { }, { }i and program int g(int y){{ int z; z=y}}, give the sequence of 11 configurations it transitions to. For each transition, include the list of rule names involved in its derivation, but not the derivation itself. [9 marks] (b) For each of the following, briefly explain the key points of its tinyC semantics and what it illustrates, referring to the transitions and rules, and to the relationship between tinyC and the full C language, as appropriate. (i) h{ int y; g(y)}, { }, { }i. [3 marks] (ii) h{ int y; 4}; y, { }, { }i [3 marks] (iii) hh(5), { }, { }i, with the program int h(int y){y=6; y}, [3 marks] (iv) h{ int y; (y=3; { int y; y=4}); y}, { }, { }i. [2 marks

grand debate is being planned by a society that has among its members a large number of computer professionals and working programmers. The motion to be put is "That the languages C and C++ should be consigned to outer darkness and their use banned in all serious computer projects". Prepare as your answer to this question a briefing document that could explain to people intending to attend the debate what the major points both for and against C and C++ will be, and the lines of arguments that are liable to be used to show how important they are. You are not required to come down either in favour of or against the languages (but may if you wish). [20 marks]

What varieties of information might an automatic journey agent want to represent? [5 marks] Using the automated travel agent for instance, outline 5 issues linked with knowledge representation. [10 marks] Would an expert system be a appropriate technique for imposing an automated journey agent? [5 marks] 7 Neural Computing Illustrate how stochasticity can be used in synthetic neural networks to clear up, at least in an asymptotic feel, problems that could in any other case be intractable. Name at least two such stochastic engines, describe the role of stochasticity in each, and perceive the styles of problems that such synthetic neural gadgets seem able to resolve. [10 marks] Illustrate the proof for stochasticity in natural fearful structures, and comment at the role that it'd play in neurobiological feature. What is the case helping John von Neumann's deathbed prediction that stochasticity might be a computational engine for the nervous device, instead of simply random noise? Describe at least one experiment regarding neural tissue in help of this theory. [10 marks] 8 Database Topics Describe the simple architecture of the ODMG-93 trendy for Object Database Management. [5 marks] In what manner do those proposals permit database management to be included with Object-Oriented Distributed Programming? [3 marks] Explain the houses of collection types, taking care to differentiate between literals and items. [6 marks] Describe how an SQL-compatible query language may be defined in the ODMG fashionable. What provision may be made for insertion, replace and deletion?

[2:29 PM, 4/11/2022] fridahkathambi71: Draw a FST which perceives the join - ly connected with normal verb modifiers in English. Exhibit that your FST accurately handles cases, for example, splendid splendidly, basic just, senseless sillily and fabulous breathtakingly. [9 marks] (d) regarding phonetic peculiarities, which parts of the morphology of modifiers does your FST neglect to accurately deal with? Would these issues be able to be fixed with a more elaborate FST, or would they say they are general issues with FST?

(b) Why is the JPEG2000 picture pressure convention such a great deal better compared to the unique JPEG in conveying great outcomes even at extreme pressure rates? What are the fundamental distinctions in the premise capacities or coding wavelets utilized, what remaking ... [11:07 PM, 4/11/2022] fridahkathambi71: A puzzle, or one-person recreation, can be represented in ML via two features: a subsequent-kingdom feature, which maps a state to a listing of feasible subsequent states, and

a wins characteristic, which returns genuine if the given state counts as a win. A easy instance is a puzzle that has states including advantageous integers, a nextstate feature that maps n to [n+ 2, n+ 5], and a "wins" feature that returns genuine if n = 10. We can win if we start from n = 2 but not from n = 7. (a) Code a polymorphic datatype 'a puzzle, to represent a puzzle by means of the pair of a next-kingdom feature and a wins function. [2 marks] (b) Briefly assessment intensity-first search, breadth-first search and iterative deepening as strategies for fixing such puzzles. [6 marks] (c) Write a characteristic intensity that accepts a puzzle, a kingdom and a depth limit. It have to use intensity-first seek to determine whether the puzzle can be solved from the given country in the given depth restrict. [6 marks] (d) Write a characteristic breadth that accepts a puzzle and a kingdom. It ought to use breadth-first search to determine whether the puzzle can be solved from the given nation. [6 marks] All code ought to be defined certainly. You may count on that any essential ML information structures or capabilities are to be had. 4 CST.2008.1.Five SECTION C 7 Operating Systems (a) What is record metadata? [2 marks] (b) Explain with the aid of a diagram how document metadata is controlled in: (i) the Unix document-gadget; [4 marks] (ii) the FAT32 file-gadget; [4 marks] (iii) the NTFS file-device. [4 marks] (c) A researcher suggests the usage of non-unstable flash reminiscence to shop the NTFS log report. He believes this can enhance performance, reduce electricity intake and make the gadget greater resilient to failure. Is he proper? Briefly justify your answer in each case. [2 marks each] eight Operating Systems (a) In fashionable we will keep in mind a process to transport among 5 method states at some stage in its lifestyles. Discuss, with the aid of a diagram, the instances in which a manner will input or go away each of these states. [6 marks] (b) Both Unix and Windows NT use dynamic precedence scheduling. Compare and assessment their scheduling algorithms, with a selected attention on how dynamic priorities are controlled. [8 marks] (c) Which statistics systems might you operate if implementing a dynamic priority scheduling algorithm? Justify your solution. [2 marks] (d) Some industry predictions suggest that during less than five years we shall have chips with hundreds or maybe lots of CPUs on them. What types of scheduling algorithms do you think could be appropriate for such systems? What problems do you foresee?

Write java program that takes each n (as enter) and n integer inputs and add the given values to a defined array

(a) Show how you'll create a Java array of a thousand integer values. [1 mark] (b) The values in an array could be used to symbolize digits in the decimal representation of quite a number. For example, the number 1 7 has decimal illustration 0.142857 . . . And that might be saved in an array whose elements commenced 1, 4, 2, . . .. For various saved that manner write code that multiplies the variety by a given integer, returning the entire wide variety a part of the end result and leaving the array up to date to maintain the fractional part of the product. [5 marks] (c) To convert a fraction to a illustration base 16 (i.E. Hexadecimal) you could multiply it by means of 16, and the resulting integer element is the primary digit of the bottom-sixteen representation. Multiplying the fraction left over by way of sixteen receives the second one digit and so on. Write a method that accepts an array of digits (base 10) and creates and returns a brand new array representing the identical fraction but now base sixteen. Your code need to paintings for any duration input array, now not simply one of period one thousand, and you could make the output array have the identical length as your enter array. [6 marks] (d) Suppose the enter in your method in component (c) become of length 1000 and began off with the decimal digits of 1 7 in it. Although the initial digits within the output array are the proper hexadecimal representation of 1 7 the last few become looking ordinary. Explain. [3 marks] (e) One manner to make sure that numerical results are correct is to apply c language arithmetic. A cost is represented as a couple of arrays, one representing a wide variety less than (or identical to) the genuine fee and one a value more than it. So if using 6 decimal locations the #1 7 might be held as a pair 142857, 142858. If the two final digits range through at most 1 then the smaller of them may be considered as absolutely accurate. Using this concept, write code that accepts a fraction in decimal form and returns a vector denoting the equal fee in any other base n (now now not always sixteen) such that all the digits within the end result vector are correct. Clarity to your code is to be desired to performance, but in case you are privy to precise methods wherein the code you gift is specially inefficient, you ought to notice and give an explanation for them. [5 marks] 6 CST.2008.1.7 10 Programming in Java The following is one of the examples from the Foundations of Computer Science route: exception Change; fun alternate (until, zero trade ([], amt) = improve trade (c::until, amt) = if amt<0 then raise change else (c :: change(c::till, amt-c)) handle> change(until, amt); (a) Define a Java elegance of your own (i.E. Do no longer use any library elegance that you may be aware of) to represent related lists of integers. Provide it with methods that may be used to reverse a list and to append two lists. Comment on whether your design has led you to make the techniques for append and reverse static. [7 marks] (b) Prepare a method known as alternate that works within the identical way because the ML code shown above. Provide the elegance which you outline it in with a primary method that makes use of it to attempt to make trade for 73p using 2p, 5p and 20p cash, printing the result well. [7 marks] (c) If you have got lists of non-zero integers such that all the values in them are much less than 256 and you have at maximum 8 gadgets in any listing you could p.C. Eight eight-bit fields into a unmarried 64-bit "long". That offers a representation that a few humans would possibly assume to be quicker than using lists represented through chained up instances of a class. Re-paintings your trade-giving code primarily based at the above idea, and modelling using exceptions with the aid of making the trade characteristic go back -1L in the extremely good case.

An inertial navigation set has a mean time to failure of 1000 hours. If an aircraft is fitted with two of them to increase reliability, is the mean time to failure of both systems which is experienced in practice likely to be several thousand hours or about a million hours? Give a brief justification for your answer. (r ) Outline the key principles of loop design, considering the simple case of a while loop.

In an edge triggered flip flop, explain what is meant by (a) hold time (b) setup time (c) delay from clock edge to output [3 marks] 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]

kindly answer all the questions