You get a summer job with a company which has an in-house operating system called sOs. sOs uses static priority scheduling, supports at most 32 concurrently-executing processes, and works only on uniprocessor machines. Describe with justification how you would modify sOs in order to: (i) support up to 50000 concurrently executing processes; (ii) reduce or eliminate the possibility of starvation; (iii) efficiently schedule processes on an 8 CPU symmetric multiprocessor (SMP) machine; (iv) support threads in addition to processes on SMP machines. (c) How would you go about reducing the time taken to boot a modern operating system?

address allquestions

(a) The following is a pattern for some legal strings in a language: [a A]{0,1} [b B]{0,1} [c C]{1,n} [d D]{1,1} where A is a finite set of characters from the alphabet, ; similarly for B, C, D. The sets A, B, C and D are disjoint. {x, y} indicates that the previous bracket must match at least x times but no more than y times. (i) Specify a Deterministic Finite Automaton, M1, that can recognise these strings only. (ii) Design a Regular Grammar, G1, which generates L(M1). [4 marks] (iii) Describe a set of strings in a natural language that could be generated by G1 given an appropriate and its subsets A, B, C and D. (b) We can hypothesise that matches of the following pattern are always valid constructions in English: [The Noun]{n,n} [V erb]{n,n} where Noun represents the coordinated members of a finite set; similarly for V erb. (i) Now consider the following English sentence which matches the pattern when n = 1: The vaccine worked Provide example sentences that extend this sentence for the case when n = 2 and n = 3.

By repeatedly dropping a knitting needle onto a floor constructed from parallelsided floor boards one may estimate the value of . Suppose the needle has unit length and the boards have unit width. After each drop the position of the needle may be specified by the values of two independent random variables: is the (acute) angle that the needle makes with the joints of the boards and it may be assumed that is distributed Uniform(0, 2 ). [It is not necessary to consider values of in the other three quadrants.] y is the distance of the centre of the needle from the nearest joint between two boards and it may be assumed that y is distributed Uniform( 1 2 , + 1 2 ). (a) Sketch sufficient of the -y plane to show the whole of the region R which corresponds to the needle crossing a joint. Deem such a crossing to be a hit and show that the probability of a hit is 2/ and, therefore, the value of may be estimated experimentally by the formula 2 drops/hits. [8 marks] (b) Suppose the needle is dropped n times. Let X be a random variable whose value is the number of hits. X is distributed Binomial(n, 2/). Give expressions for the Expectation E(X) and the Variance V(X).

(a) Recall that the (local) rendering equation is given as Lo(x, ~o) = Le(x, ~o) + R H2 fr(x, ~i , ~o)Li(x, ~i) cos id~i . Simplify this expression progressively as much as possible after each of the following assumptions. [5 marks] (i) There is no light emitted from this surface point x. (ii) Diffuse reflection. (iii) Reflection is constant at all surface points. (iv) The incoming light is the same for all incident angles but there can be occluders. (v) There is a single object and we ignore self-occlusions. (b) Under certain assumptions, we can simplify the rendering equation to the following: Lo(x, ~o) = fr R H2 Li(~i) cos id~i . Assume we have a single known geometry for which we can compute surface normals n(x). Given three measurements from the surface ck = Lo(xk, ~o) at known points xk, compute the reflected radiance Lo(x, ~o) at an arbitrary point x on the surface. [Hint: If you encounter a linear system Ax = b, assume A1 is known.]

Write program that reads a user inputted number of hours that one person works in a week and his/her hourly pay. Calculate the total pay and print it. Write program that insert number from the keyboard, and find out the number is prime or not? Write complete C++ program to ask the user to enter 4 integers. The program must use a function to find the LARGEST integer among them and print it on the screen.

(a) Given a random variable X distributed Geometric(p) one has: P(X = r) = q r p where p + q = 1 By using a suitable generating function, derive expressions for the expectation and variance of X. [6 marks] (b) A computer game proceeds in a sequence of steps and, at each step, the contents of a two-bit random number generator are inspected. Each bit is 1 with probability p and 0 with probability q where p + q = 1. The two bits are independent. If the two bits differ (as 01 or 10) the game ends but if the two bits are the same (as 00 or 11) the game proceeds to another step. Accordingly, the game could be as short as a single step but it could last many steps. Let X be a random variable whose value r is the length of a game measured in steps. The game cannot end at step 0 so P(X = 0) = 0. (i) Derive an expression for P(X = r). [5 marks] (ii) Show that X r=0 P(X = r) = 1.

(a) static void fastFilter(ArrayList a, Predicate p) { int j = 0; for (int i = 0; i < a.size(); i++) { if (p.test(a.get(i).key)) a.set(j++, a.get(i)); } a.removeRange(j, a.size()); } The above method fastFilter operating on ArrayList was written by a Java programmer, perhaps misguidedly in the interests of speed. It uses method removeRange to remove the final a.size()-j elements from a. We wish to enable fastFilter also to operate on ArrayList where DatumDash inherits from Datum. (i) Give code for a modified version using subtype polymorphism, justifying any changes and highlighting any unresolvable difficulties. [5 marks] (ii) Similarly, what changes, if any, would be required if the original fastFilter instead used Java classic [] arrays? Again justify your answer. [3 marks] (iii) Give a definition of fastFilterInner which uses generic polymorphism, along with a subtype-polymorphic wrapper whose signature matches that used in Part (a)(i). [Hint: consider moving the use of .key.] [4 marks] (b) class Myst { // A Mystery? private Supplier act; // Java's name for void->Int private Myst(Supplier a) { act = a; } static Myst R(Int x) { return new Myst(()->x); } Myst B(Function f) { return f.apply(act.get()); } static Myst primIn = new Myst( () -> SystemIO.readInt()) ); static Myst primOut(Int x) { return new Myst(() -> { SystemIO.println(x); return x;} ); } static void exec(Myst x) { x.act.get(); } } The class Myst is coded in a language resembling Java. What concept does it model and what does the code below conceptually do if executed in its scope? Myst one = primIn.B(x -> primOut(x+1)); Myst two = R(2).B(y -> primIn.B(x -> primOut(x+y))); Myst three = one.B(x -> two).B(x -> one); exec(three);

(a) A one megabyte memory bank with 64-bit data bus is to be constructed from SRAM chips of individual capacity 32K8. Sketch out a design for the bank showing clearly how the SRAM chips are arranged. [4 marks] (b) Describe, in 30-40 words each, three ways in which an underlying theory can help to improve the quality of software systems. [4 marks] (c) Acoustic couplers used to connect modems to telephone handsets present an audio interface from the telephone network to computer equipment. Name one advantage and one disadvantage of using such an interface. [4 marks] (d) Show that for any two regular expressions r and s, the regular expressions r(sr) and (rs) r determine the same regular language.

Predictive text entry systems are familiar on touch screens and mobile phones. This question asks you to consider how the same principles might be used in a programming editor for creating Java code. (a) Explain using Bayes' Theorem how such an editor might update its expectation about which identifier will appear next, as the programmer is typing a line of code. Your answer should include a short extract of Java code preceding this line, in order to illustrate the context in which the expectation is being calculated. [5 marks] (b) Describe how you could obtain an empirical measurement of the actual improvement in efficiency that results from using this predictive editor in practice. [5 marks] (c) Consider the four possible combinations of a) small versus large variance, and b) small versus large effect size, in repeating this measurement. For each combination, explain the practical interpretation of that data for future development of the programming editor. [5 marks] (d) If programmers have the option of whether or not to turn on this new function in the editor, describe some of the factors that might influence their decision-making process, with specific reference to the cognitive processes and sources of information that they would use

The new Master of (fictional) Porterhouse would like to modernise the college. They bring the following proposals to the College Council, of which you are a member. (a) Proposal 1: Change the way students are admitted to the college for all subjects. Rather than having humans interview candidates, or at least read their references and personal statements, an algorithm would make all admission decisions. (i) Use an ethical perspective to make a persuasive argument for or against Proposal 1, defining and explaining relevant concepts. (ii) If Proposal 1 is accepted, what changes would the college need to implement to comply with GDPR? (b) Proposal 2: The college is buying apartments in the next phase of the North West Cambridge development for use by graduate students and students with dependents. The options are to buy a) a range of apartments, from utilitarian to luxurious, which would be rented out at different amounts; or b) a block of apartments all of the same size, which would be rented out at the same price. (i) Use an economic perspective to make a persuasive argument for option a) or b), defining and explaining relevant concepts.