WL advance increments the count and returns its new value, read…

Question Answered step-by-step WL advance increments the count and returns its new value, read… WLadvance increments the count and returns its new value, read returns the current value of the count, and await (value) suspends the calling thread until the count is at least as large as the value given as an argument. A sequencer is an integer, initially zero, equipped with a single atomic operation: ticket increments the count and returns its previous value. Given an eventcount, guard, and a sequencer, turn, a critical region can then be coded as follows: myturn := turn.ticket (); guard.await (myturn); . . protected code . EVAL guard.advance (); Write an interface, ECS, defining opaque object types EventCount and Sequencer. EventCount should have methods advance, read and await, with appropriate signatures, and Sequencer should have a ticket method. [8 marks] Sketch an implementation of the ECS module giving concrete revelations of the types and providing appropriate default methods. [12 marks] 3 [TURN OVER CST.94.10.4 4 Formal Languages and Automata What is meant by the language accepted by a finite deterministic automaton M = (Q, Σ, δ, i, F)? [2 marks] Show that it is possible to associate with M a regular? expression r over Σ denoting the same language as that accepted by M. [12 marks] Illustrate your answer by constructing such a regular expression r when M is the finite deterministic automaton with Q = {q1, q2, q3} Σ = {0, 1} i = q1 F = {q3} and with transition function δ defined by the table q1 q2 q3 0 q2 q3 q3 1 q3 q2 q2 [6 marks] 5 Operating System Functions Describe the use of an inverted page table for the implementation of virtual addressing and a paging virtual memory? system. Give details of the operation of the page table and its associated data structures. [15 marks] What can be done to overcome the thrashing problem encountered with a direct mapped inverted page table? [5 marks] 4 CST.94.10.5 6 Operating Systems An operating system supports multi-threaded processes. Within a given user-level address-space two threads cooperate by means of a shared, circular, N-slot buffer. Semaphores are supported by the language system. Outline programs that may be executed by the thread which writes data into the buffer and the thread which reads data from it. [8 marks] How would you ensure that several threads could write to, and read from, the buffer? [4 marks] Explain how the semaphore implementation in the language system uses the thread implementation in the operating system. [8 marks] 5 [TURN OVER CST.94.10.6 7 Data Structures and Algorithms For the following, n is a positive integer and G is a graph of N nodes (vertices) and E arcs (edges) each with a given weight (or cost). For seven of the following indicate, with a short justification, whether the statement is true or false. (a) All functions f of the form f(n) = Ank (with A and k being constants) are in the class O(2n). (b) All sorting methods for an array of n elements take time O(n 5 ). (c) It is possible to sort an array of n elements using binary comparisons in Θ(n log n) time. (d) It is possible to sort an array of n elements using binary comparisons using O(1) (i.e. constant independent of n) additional space. (e) Radix sorting can sort any set of integers in linear time. (f ) All straight lines from the inside of a? polygon to the outside intersect the points on the edges forming its boundary an odd number of times. (g) It is always cheaper to find the shortest distance between two given nodes u, v of G than to find all N shortest distances from u to every other node. (h) It is possible to find the shortest? paths between all N2 pairs of nodes of G in O(N3 ) time Programming Describe how the λ-calculus models the operations of addition, test for zero and successor, representing the natural numbers by Church numerals. [4 marks] The Fibonacci sequence is defined by F0 = 0, F1 = 1 and Fk = Fk−1 + Fk−2 for k > 2. Present a λ-term fib that computes the Church numeral for Fk given the Church numeral for k, for all k > 0. Do not use Y or any other fixed point combinator. You may take as primitive the λ-calculus encodings of standard data structures. [6 marks] Describe how to assign G¨odel numbers to λ-terms and explain the notation pMq. Describe an application of these techniques. [3 marks] Present a λ-term iszero, such that iszeropMq = true if M = 0 false if M 6= 0 or prove that no such term exists. [7 marks] 4 CST.93.5.5 10 Computation Theory Show that there is no way of deciding by algorithms whether a general register machine program with code p will terminate when started with initial data of 0 in every register. [10 marks] Show that there is no way of deciding by algorithm whether the blank character will be printed during the course of a general Turing machine computation. [10 marks] Note: any standard form of the undecidability result for the general halting problem may be assumed, but should be stated clearly. 11 Complexity Theory Explain how to measure the size of a problem in complexity theory. [3 marks] What is meant by reducing one problem to another? [4 marks] Given that the Boolean Satisfiability Problem is NP-complete, show that the Hamiltonian Circuit Problem for undirected graphs is also NP-complete. [13 marks] 12 Formal Languages and Automata Explain what is meant by a regular exks] For any regular expressions r, s, t, show that if L(r) contains L(t|sr) then it also contains L(. Hint: argue by induction on the length of strings in L(r). [5 marks] Give an example to show that the above assumption ε 6∈ L(s) is necessary. [3 marks] Deduce that when ε 6∈ L(s), r and t|sr denote the same language if and only if r and s*t denote the same language. An alternative ultrasonic positioning system could use network-connected beacons positioned around a building that simultaneously emit a radio signal and an ultrasonic pulse. Describe how this would work and discuss its advantages and disadvantages over the Active Bat system. [8 marks] (c) The Active Bat system makes use of narrowband ultrasound for the propagation medium. It can be adapted to use wideband ultrasound signals. By analogy with the benefits that wideband radio signals give GPS, discuss the advantages and disadvantages of doing so.This question is on HOPLA and PCCS, a variant of pure CCS in which any output on a channel persists. Let A be a set of channel names ranged over by a, b, c and let A¯ be the set of complemented channel names, A¯ = {a¯ | a ∈ A}. The set of labels L = A ∪ A¯ is ranged over by l, to which we extend complementation  Draw the transition system of the PCCS term ¯a k a.a.¯b . [3 marks] (b) This part of the question is on HOPLA. For reference, the operational semantics of HOPLA is presented at the end of the question. (i) For u of sum type, let [u > a.x ⇒ t] abbreviate [πa(u) > .x ⇒ t]. Derive a rule for the transitions of [u > a.x ⇒ t]. [2 marks] (ii) Show that [a.u > a.x ⇒ t] ∼ t[u/x] and [a.u > b.x ⇒ t] ∼ nil if a 6= b, where nil represents the empty sum and ∼ is the bisimilarity of HOPLA. [4 marks] (c) Write into HOPLA, specifying a HOPLA term JPK for every PCCS term P. [Hint: The realisation of parallel composition should be the same as that of the encoding of pure CCS into HOPLA.]The virtual address space of a UNIX V7 process contains a text segment, a datasegment and a stack segment.(i) What is contained in the text segment? How does this change as theprocess executes? (ii) What is contained in the data segment? How does this change as theprocess executes? (iii) What is contained in the stack segment? How does this change as theprocess executes? (b) The UNIX kernel is also present in the virtual address space of every process.Describe how the operating system can ensure that this memory region isprotected from access by an executing process. Under what circumstances cana process gain access to this region of virtual memory? [2 marks](c) Compare and contrast blocking, non-blocking and asynchronous I/O.[2 marks each](d) You are asked to write a device driver for a hard-disk drive.(i) Under what circumstances will you issue requests to the drive? [2 marks](ii) What steps will you need to take when an interrupt occurs? [2 marks](iii) Given that the hard-disk drive is not really a random access device, whatsteps could you take to improve performance? In the application of interest, you believe that it is desirable to train such that the learned parameters have ||w|| ‘ 1. Suggest a modification to E(w, b) that facilitates this, and derive the corresponding gradient descent training algorithm. [5 marks] (c) Describe the components of a general heuristic search problem. [4 marks] (d) You are faced with a heuristic search problem, but the heuristics you have so far developed are less effective than desired. Suggest two ways in which supervised machine learning might be used to develop a better heuristic, mentioning if necessary any corresponding disadvantages of using the approach. You may assume that a collection of problems to be solved by the heuristic search is available.Assume that one of the other relations, which may define a partial function, does so. Show how to convert it to a partial function whose range is a set of partial functions. Illustrate your answer with suitably chosen example data. SECTION B 4 X and Y are independent random variables having Poisson distributions with parameters α and β respectively. By using probability generating functions, or otherwise, prove that X + Y has a Poisson distribution and give its parameter. Find the conditional distribution for X given that X + Y = n, and give its mean and variance. Explain your result in words. 5 A single die is repeatedly thrown, and accumulating cou. ., 6s are equal’ will ever occur. [Hint: you will need Stirling’s approximation n! ≈ (2π) 1 2 n n+ 1 2 e −ction. Of their output, 5%, 4%, and 2% respectively are rejected as faulty. What is the probability that from a collection of chips drawn at random from the output two which are faulty were made on the same machine? What is the probability that three faulty chips were all made on different machines? SECTION C 7 Discuss the requirements of an Automatic Teller Machine (ATM) service under the headings: (a) security; (b) availability of service; (c) integrity of stored data; (d) procedure for dispute resolution. ere k is an ML variable whose value is a positive integer. fun value [] = 0 | value (x::xs) = x + (k*value xs); fun carry c [] = [c] | carry c (x::xs) = ((c+x) mod k) :: carry ((c+x) div k) xs; fun sum c [] ys = carry c ys | sum c (x::xs) [] = carry c (x::xs) | sum c (x::xs) (y::ys) = ((c+x+y)mod k) :: sum ((c+x+y)div k) xs ys; (a) State and justify the rule of structural induction for lists. (b) Your client would like you to prove the correctness of sum, expressed by the property value(sum 0 xs ys) = value(xs)+value(ys). Generalize this formula so that it permits a useful structural induction proof, explaining your reasons. (c) Prove the base case of the structural induction. (d) Prove the inductive step of the structural induction. (e) What does the correctness proof say about the case where k equals 1? Discuss whether other properties are necessary to ensure correctness. Proofs may assume the analogous correctness property for carry and standard mathematical laws. State these assumptions clearly. (a) Explain how a Boolean matrix can be used to represent the edges of a finitedirected graph whose vertices are numbered 1 to n.(b) Describe Warshall’s algorithm to convert the matrix representing a graphto one that represents its transitive closure, and carefully explain why thealgorithm works.(c) Outline Floyd’s algorithm, without proof of correctness, to find the cost of thecheapest path between any two vertices of a directed graph where the edgescarry non-negative atrix R that encodes a path with the minimumnumber of edges from any vertex i to any other vertex j. Rij will be zero ifno path exists from vertex i to vertex j; otherwise, Rij will hold the vertexnumber of the next vertex of a minimal path from i to j. Suggest an algorithmto compute R from a given Boolean matrix M. It is proposed to send information across a fixed delay channel using a simple(window of 1) ARQ protocol with a transmitter timeout of T. That is, if thetransmitter does not receive an acknowledgement for a packet within time T ofsending the packet, it retransmits.The delay of the underlying channel is τ , the data rate is B and the packet size is pbits. Bit errors in the channel are independent and packets of size p have a packeterror rate of e. Errors in the small acknowledgement packets are rare enough to bediscounted in this analysis.(a) What is the expected throughput of the ARQ protocol if e is zero? [4 marks](b) What is the expected throughput if e is non-zero, but small enough that e2isnegligibly small?(c) How could a forward error code help the throughput of the ARQ scheme?[2 marks](d) What is meant by the term code rate of a forward error code? [2 marks](e) What code rate must a code which squared the error rate have in order toimprove throughput of the ARQ scheme?  In (1) and (2) below, the words in the sentences have been assigned tags from theCLAWS 5 tagset by a stochastic part-of-speech (POS) tagger:(1) Turkey NP0 will VM0 keep VVI for PRP several DT0 days NN2 in PRPa AT0 fridge NN1(2) We PNP have VHB hope VVB that CJT the AT0 next ORD year NN1will VM0 be VBI peaceful AJ0In sentence (1), Turkey is tagged as a proper noun (NP0), but should have beentagged as a singular noun (NN1). In sentence (2), hope is tagged as the base formof a verb (VVB: i.e., the present tense form other than for third person singular),but should be NN1. All other tags are correct.(a) Describe how the probabilities of the tags are estimated in a basic stochasticPOS tagger. [7 marks](b) Explain how the probability estimates from the training data could haveresulted in the tagging errors seen in (1) and (2). [6 marks](c) In what ways can better probability estimates be obtained to improve theaccuracy of the basic POS tagger you described in part (a)? For eachimprovement you mention, explain whether you might expect it to improveperformance on examples (1) and (2). (a) Explain what it means to say that a problem is(i) NP [2 marks](ii) NP-Complete [2 marks](b) Define the standard problem 3-SAT and describe how you would take aninstance of it and derive an integer n that you would use in any formulaerelating to the cost of solving that instance. [3 marks](c) What is a non-deterministic Turing Machine? Supposing that somecomputation of such a machine takes N steps, what information needs tobe reported to describe exactly how the computation proceeded? In what wayis this relevant to the problem of solving an arbitrary NP problem? [7 marks](d) Sketch a proof of Cook’s result, that the problem 3-SAT is NP complete.Justify that any transformations you introduce are polynomial. (a) Give a precise definition of each of the complexity classes NP and co-NP.[4 marks](b) Give an example each of(i) an NP-complete language; and(ii) a co-NP-complete language,in each case giving a precise statement of the decision problem involved.[4 marks](c) If A and B are the two languages identified in Part (b), give an example ofa language that is polynomial-time reducible to both A and B. Justify youranswer. [4 marks](d) Consider the following statement:There is a polynomial p such that every valid Boolean formula oflength n has a proof of length at most p(n). Moreover, there is apolynomial-time algorithm that can check the correctness of the proofs.This statement is not known to be true or false. Explain what would be theconsequences of this statement being true or false for the relationship betweenNP and co-NP, giving full justification for your answer. (a) Describe the characterists of debt and equity financing, highlighting thedifferences between them.(b) What is the difference between a loan and an overdraft?Your software company is contracted to create a new control system for chocolatebar delivery in Cambridge. The contract is for a 6 month period, with payment of£400k against milestones in months 1, 3 and 6.(c) Create an outline cashflow for the project assuming staff costs of £75k per monthand overheads of £60k per month.(d) What is your working capital requirement for the project allowing a contingencyof a two month delay to one of either the second or third delivery milestones?[5 marks](e) How would you suggest to finance this working capital requirement (a) Describe the DPLL method, explaining briefly each of its four steps. [4 marks](b) Use the DPLL method to find a model satisfying the following set of clauses, orto prove that no such model exists.{P, Q} {R} {Q, ¬S, ¬Q} {¬Q, ¬R, S} {P, ¬Q} {P, Q, ¬S} {P, ¬R, S} {¬P, ¬S}[6 marks](c) Describe briefly the procedure for constructing a BDD. Illustrate your answerby constructing the BDD (using the variable order P < Q < R < S) for:(¬P ∨ (Q ∧ S)) ∨ (S ∨ (¬R ∨ S)) : Write  full C++ program that reads an integer, a list of words, and a character. The integer signifies how many words are in the list. The output of the program is every word in the list that contains the character at least once.Write  C++ program which reads three values of types char, int, double and string from the keyboard and primis, appropriately formatted, assigned values and variable types.Write  program that reads a string and a character from the keyboard. The program should output how many times the character appears in the string.Write  menu based program implementing the following functions:   (a) Given two signed distance field functions f and g, give the formula fortheir . . .(i) Union (f∪g)(ii) Intersection (f∩g)(iii) Difference (f−g)[3 marks](b) Give clear definitions for the Virtual Reality industry's principles of immersionand presence. Compare the two concepts and explain the difference betweenthem with examples demonstrating each. [5 marks](c) The Doo-Sabin subdivision scheme has kernel (1/4)[. . . , 0, 0, 1, 3, 3, 1, 0, 0, . . .],defining a scheme in which each face is replaced by four new vertices.(i) Give an expression for computing the position of a new vertex given thepositions of the four old vertices of a face. [2 marks](ii) If the face does not have 4 vertices then you must weight each parent vertexdifferently to find the position of the child. Suggest possible weights for thevertices of faces with 3, 5, and n vertices, and justify your answer.[3 marks](d) There are several ray-tracing-friendly acceleration structures.(i) Explain the BSP tree data structure. Explain how it is constructed andtraversed. [3 marks](ii) Explain the kd-tree data structure. Explain how it is constructed andtraversed. [3 marks](iii) Which of the two data structures is best-suited to ray-tracing a game ofchess in real time? Most large programs that have been written with considerable care and thoroughlychecked still seem to contain bugs at a rate of over one per 3000 lines of sourcecode. Systems involving hundreds of millions of lines of code can thus be expectedto contain tens of thousands of potentially catastrophic errors.(a) List several kinds of programming errors that can appear in programs anddiscuss their relative importance in relation to the long-term reliability of alarge application program. [7 marks](b) Suggest potential ways by which programmers may reduce the number ofprogramming errors they make, paying particular attention to languagefeatures that might help, extra features in program development systems andpossible changes in overall system architecture. [8 marks](c) In what ways would you expect languages 25 years from now to differ fromthose 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 algebraand SQL. [4 marks](c) Suppose that S(a, b, . . .) and R(a, . . .) are relations (the notation indicatesthat attribute a is in the schema of both S and R, while attribute b is only inthe schema of S). Suppose that v is a value; is the following equation alwaysvalid?σ(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 whyschemas in normal form are important for good performance. An appropriate structure for large-scale distributed systems is as multiple,independently administered, firewall-protected, domains. Examples are a nationalhealth service, a national police service and a global company with worldwidebranches. Communication must be supported within and between domains andexternal services may be accessed. For example, health service domains may allaccess a national Electronic Health Record service; police service domains may allaccess a national Vehicle Licensing service.(a) (i) Define publish/subscribe communication.  Computer Science Engineering & Technology C++ Programming CS MISC Share QuestionEmailCopy link Comments (0)