kindly answer urgently ) side conditions and variable capture [5…

Question Answered step-by-step kindly answer urgently ) side conditions and variable capture [5… kindly answer urgently ) side conditions and variable capture [5 marks] Illustrate your explanations with examples. 12 Computational Number Theory Describe how the set of composite numbers can be recognised in Random Polynomial time. [12 marks] Describe how the set of prime numbers can be recognised in Non-deterministic Polynomial time. [8 marks] 6 CST.94.7.7 13 Semantics of Programming Languages Dijkstra proposed the language of guarded commands with the following syntax. Commands take the form c ::= skip | abort | X := e | c; c | if gc fi | do gc od where e is an arithmetic expression and gc stands for a guarded command of the form b1 ? c1 [] b2 ? c2 for boolean expressions b1 and b2, called guards, and commands c1 and c2. Execution of the command skip does not result in a change of state. Following Dijkstra’s intentions, if no guard evaluates to true at a state, then the guarded command is said to fail, in which case, the guarded command does not yield a final state. Otherwise, the guarded command executes as one of the commands ci whose associated guard bi evaluates to true. The execution of the command abort does not yield a final state from any initial state. The command if gc fi executes as the guarded command gc, if gc does not fail, otherwise, it acts like abort. The command do gc od executes repeatedly as the guarded command gc, while gc continues not to fail, and terminates when gc fails. (a) Assume that boolean and arithmetic expressions have no side effects and always terminate, and that the rules for their evaluation are given. Write down a collection of rules for an inductively defined evaluation relation of the form c, S ? S 0 whose sense is “starting from the initial state S, the evaluation of the command c terminates at the final state S 0 .” [10 marks] (b) Give the commands in Dijkstra’s guarded language which simulate the standard imperative programming commands if b then c1 else c2 and while b do c respectively. You may assume that if b is a boolean expression, then so is ¬b, the negation of b. [2 marks] (c) Give an appropriate definition of semantic equivalence of commands with respect to the evaluation relation defined in (a). Prove that for any boolean expression b and any [] ¬b ? skip fi [8 marks] 7 [TURN OVER CST.94.7.8 14 Concurrency Define what is meant by observational equivalence of CCS agents. [5 marks] A transmitter T, transmission medium M, and receiver R are modelled by CCS agents with the following definitions: T def = in.i.T0 T 0 def = r.i.T0 + a.T M def = i.M0 M0 def = o.M + ?.r.M R def = o.out.a.R M is an unreliable medium: having received an input message from T (action i) it either outputs the message to R (action o), or loses it (represented by the ? action) and then sends a request for retransmission (action r). If R does receive the message, after broadcasting it (action out) it sends an acknowledgement directly to T (action a). Calculate the transition graph of (T|M|R) {i, o, r, a} and hence show that this agent is observationally equivalent to a simple buffer B with definition B def = in.out.B [10 marks] Are (T|M|R) {i, o, r, a} and B observationally congruent? [3 marks] Do the two agents have the same behaviour with respect to divergence, that is, the ability to perform a series of actions ending in an infinite sequence of ? -actions? Consider the following clauses: a(1). a(a). b(3). b(a). c(A,B) :- b(B),!,a(A). c(X,_) :- a(X),b(X). (i) List all the solutions to the query c(A,B) in order, giving any binding of variables that occurs. [2 marks] (ii) List all the solutions to the query c(X,1) in order, giving any binding of variables that occurs. [2 marks] (c) A binary tree has nodes whose values are non-empty lists. A tree node is represented using a term that takes the form Left-SomeList+Right or nil (note that parentheses can be used to enforce precedence). For example, the following term would be a valid tree: nil-[root,1,2]+(nil-[child,4]+nil) (i) Write a predicate preorder(+Tree,-ValueList) that unifies ValueList with a list containing all of the tree nodes’ values from a pre-order tree walk (i.e. emit node value, then left subtree, then right subtree). The predicate should fail if any of the tree nodes’ values are not of the correct form. For the above example tree, preorder/2 would unify ValueList with [[root,1,2],[child,4]]. You may assume that append/3 has been defined already. [6 marks] (ii) Now write a predicate preorderdl/2 that behaves exactly like your preorder/2 predicate, but in its implementation makes use of difference lists, instead of querying append/3. [6 marks] 8 CST.2011.3.9 9 Software Engineering (a) Describe the ks] (b) When discussing system development Fred Brooks says, “plan to throw one away – you will anyway”. What disadvantages of the waterfall model is he referring to? Outline an alternative software development model that deals with these disadvantages. [7 marks] (c) You work for a large “social networking” company which has recently introduced a one-to-one chat mechanism, promising that they will never censor conversations. Users are now reporting that their friends’ computers are being compromised by malicious software. When users click on links within messages sent by this malicious software, their machine is also compromised, and spreads the infection still further. A crisis meeting has decided that the chat software must be modified to block this “worm” behaviour. As manager of this project, how will you approach the development, how will you estimate how long the task will take, and how will you establish that your solution is safe to deploy (a) Consider packet switching and circuit switching. In simple terms, packetswitching may allow more users to use the network.We have N users sharing a 1 Mbit/s link. Each user consumes 100 kbit/s whentransmitting but only transmits for 10% of the time, on average.(i) How many users would a circuit-switching system support? State yourassumptions. [1 mark](ii) For N = 40 users, the probability that more than 10 users are active at thesame time is approximately 0.0015.Show how to compute this probability. You are not required to calculatethe actual figures. [6 marks](iii) State two assumptions that you made in Part (a)(ii) about the networkusers. In each case describe why the assumption may fail for currentInternet traffic. [4 marks](b) The formulae below are used in TCP implementations to compute a value forthe retransmission time-out T. R is an estimate of the round-trip time (RTT),D is an estimate of variance, M is the most recently measured round-tripmeasurement, ? = 0.875 and h = 0.25.D ? D + h(|M ? R| ? D)R ? ?R + (1 ? ?)MT = R + 4D(i) Give an example of how the retransmission time-out T is used within TCP.[1 mark](ii) Describe why the computation of the retransmission time-out T incorporates a correction for deviation in the estimate of the RTT. [2 marks](iii) For each assumption you stated in Part (a)(iii), describe the impact on theestimate of the retransmission time-out T. [3 marks each]7 (TURN OVER)CST.2016.5.87 Concurrent and Distributed SystemsThis question is with respect to an operating system that supports multi-threadedprocesses using the POSIX threads (pthreads) API. Assume that each call to printfprints its output atomically, that thread scheduling is non-deterministic, and thatthreads are allocated unique and sequential integer IDs starting with 0.(a) Some program state is per-process, and some is per-thread. How many instancesof each of the following will a 2-thread process have: virtual address space,executable program, register file, scheduling state (e.g., RUN, SLEEP), and stack?[5 marks](b) A programmer adds printfs to a concurrent program to debug a race condition,but the symptoms vanish. Explain why this might have happened. [2 marks](c) thrprint accepts as arguments the current thread’s unique ID and a debugmessage to print. If each thread calls thrprint exactly once on start, howmany possible interleavings are there with n threads? [2 marks]void thrprint(int threadid, char *message) {printf(“Thread %d: %sn”, threadid, message);}(d) ordered thrprint attempts to print debug messages ordered by thread ID.Describe three ways in which the synchronisation in this implementation isincorrect, and provide a corrected pseudocode implementation. [6 marks]int next_thread_id = 0; // Next ID to printpthread_mtx_t ordering_mtx; // Lock protecting next IDpthread_cond_t ordering_cv; // next_thread_id has changedvoid ordered_thrprint(int thread_id, char *message) {pthread_mtx_lock(ordering_mtx);if (thread_id != next_thread_id) {pthread_cond_wait(ordering_cv, ordering_mtx);}next_thread_id = next_thread_id + 1;pthread_mtx_unlock(ordering_mtx);printf(“Thread %d: %sn”, thread_id, message);}(e) This approach to implementing ordered thrprint suffers a substantial performance problem: if lower-numbered threads are slow in starting, thenhigher-numbered threads will also be delayed. Describe an alternative strategy,paying particular attention to synchronisation, that maintains ordered outputwhile allowing greater concurrency. [5 marks]8CST.2016.5.98 Concurrent and Distributed SystemsHistory graphs record dependencies between individual atomic operations withinsequences of events associated with specific schedules of more complex transactions.(a) (i) What do edges in a history graph represent? [1 mark](ii) What graph property holds if a bad schedule is present? [1 mark](iii) Which ACID properties may be violated by a bad schedule? [2 marks](iv) Define serial and serialisable executions. Explain whether (and if so, how)one is a superset of the other. [3 marks](b) Two transactions, T1 and T2, consist of operations on two objects, A and B:T1: { T2 (v): {a = A.getbalance(); A.debit(v);b = B.getbalance(); B.credit(v);return (a + b); }}(i) Explain how a dirty read might be experienced through concurrentexecutions of T1 and T2. [2 marks](ii) Draw and label a history graph illustrating this bad schedule. [2 marks](c) A programmer designs a transaction system that uses history graphs to detectbad schedules. After an operation is performed, and before its containingtransaction is allowed to commit, the history graph is updated and a graphanalysis is run. If a bad schedule is detected, affected transactions will be abortedand rolled back.(i) Will this scheme always make progress? Explain your answer. [2 marks](ii) Time Stamp Ordering (TSO) will sometimes reject good schedules, whichcould lead to unnecessary transaction aborts. Does the scheme describedhere accept or reject more schedules than TSO? Explain why. [3 marks](iii) Explain one way in which this scheme may perform better than TSO.Explain one way in which it may perform worse. [4 marks]9 (TURN OVER)CST.2016.5.109 Concurrent and Distributed SystemsRemote Procedure Call (RPC) allows procedures (functions, methods) to beforwarded over the network, and is a fundamental building block of distributedsystems such as the Network File System (NFS).(a) Explain, with respect to a client, what it means for an RPC call to be:(i) Synchronous [1 mark](ii) Asynchronous [1 mark](iii) Idempotent [1 mark](b) Distributed-filesystem clients utilize different tradeoffs between performance andconsistency for operations on the directory namespace (e.g., file or directorycreation) versus those on file data itself. The following program creates andopens a file foo, writes some data to it, and closes it, via NFSv3:fd = open(“foo”, O_CREAT | O_RDWR, 0755);// POINT Awrite(fd, data, sizeof(data));// POINT Bclose(fd);// POINT CFor each of points A, B, and C in the program, discuss whether or not anotherNFSv3 client is guaranteed to be able to see the results of each of open and (ifit has been called) write.(a) Consider unspecified behaviour in C.(i) Define what unspecified behaviour means in the C standard and give twoexamples of such behaviour. [3 marks](ii) Briefly explain why it is important to have unspecified behaviour in thedefinition of the C language. [1 mark](b) Compare and contrast the struct and union keywords in C, supplying anexample of a situation where it would be more appropriate to use a unionrather than a struct. [4 marks](c) Explain the following C or C++ language concepts. You may find it helpful touse short code fragments or diagrams to illustrate your answer.(i) The virtual keyword used to qualify a C++ member function and itsimpact on generated code. [4 marks](ii) The role of the C preprocessor in the source-code compilation cycle, andwhy it is a useful tool for debugging. [4 marks](iii) Templated functions in C++, giving one benefit and one drawback of usingthem compared with using a void* function in C. [4 marks]3 (TURN OVER)CST.2016.3.43 Compiler ConstructionProgramming answers should be written in some notation approximating SML orOCaml.(a) Describe what is meant by tail recursion. [4 marks](b) Eliminate tail recursion from foldl given below. Explain your answer.(*foldl : (‘a -> ‘b -> ‘a) -> ‘a -> ‘b list -> ‘a*)let rec foldl f accu l =match l with[] -> accu| a::l -> foldl f (f accu a) l[8 marks](c) Eliminate tail recursion from the following mutually tail-recursive functions.Explain your answer.let rec is_even n =if n = 0then trueelse is_odd (n – 1)and is_odd n =if n = 0then falseelse is_even(n – 1)[8 marks]4CST.2016.3.54 Compiler ConstructionConsider writing a compiler for a simple language of expressions given by the followinggrammar,e ::= n (integer)| ? (read integer input from user)| e + e (addition)| e ? e (subtraction)| e ? e (multiplication)| (e, e) (pair)| fst e (first projection)| snd e (second projection)(a) Describe the tasks that should be carried in implementing a front end for thislanguage and any difficulties that might be encountered. [5 marks](b) Suppose that the target virtual machine is stack-oriented and that the stackelements are integer values, and addresses can be stored as integers. Explainwhich other features are required in such a virtual machine. Invent a simplelanguage of instructions for such a machine and show how it would be used toimplement each of the expressions. [10 marks](c) Suppose that the following rules are proposed as possible optimizations to beimplemented in your compiler.expression simplifies to expression(fst e, snd e) ? efst (e1, e2) ? e1snd (e1, e2) ? e2Describe how you could implement these rules so that the simpliCST.2016.3.6fications aremade only when the program’s semantics is correctly preserved.  a C++ program to sort the elements of the array in ascendingorder.a C++ program using for-loop to print the following output, 105 205 305 405 505 605.2. Write  C++ program using do-while to take a number less than 100 as input from keyboard.(a) Explain what is meant by a monad in a programming language, giving the twofundamental operations of a monad along with their types. [3 marks](b) Consider the use of a monad for input-output. For the purposes of this question,take the IO monad as including two operations readint and writeint whichrespectively read integers from stdin and write integers to stdout. Give the typesof these operators. [2 marks](c) Assume MLreadint and MLwriteint are primitives with side effects for inputoutput and consider the ML expression add1 of type int:                      let val x = MLreadint() in MLwriteint(x+1); x end(i) Give an equivalent expression which uses the IO monad instead ofside-effects, and state its type. [3 marks](ii) Give a function run2diff which can be applied to your answer topart (c)(i). When so applied it should give a value in the IO monad whichcorresponds to ML code that runs add1 twice and returns the differencebetween the values read. [4 marks](d) State what happens when attempting to compile and execute the following Javafragment (explaining the origin of any error messages or exceptions which mightarise).Object n = new Integer(42), o = new String(“Whoops”);Object [] v;Integer [] w = new Integer[10];v = w;v[4] = n;v[5] = o; [4 marks](e) Consider the Java code:Object n = new Integer(42);ArrayList v1;ArrayList