(a) Describe how the CPU is allocated to processes if static priority scheduling is used. Be sure...

Fantastic news! We've Found the answer you've been seeking!

Question:

(a) Describe how the CPU is allocated to processes if static priority scheduling is used. Be sure to consider the various possibilities available in the case of a tie. (b) "All scheduling algorithms are essentially priority scheduling algorithms." Discuss this statement with reference to the first-come first-served (FCFS), shortest job first (SJF), shortest remaining time first (SRTF) and round-robin (RR) scheduling algorithms. (c) What is the major problem with static priority scheduling and how may it be addressed? (d) Why do many CPU scheduling algorithms try to favour I/O intensive jobs? ow this is achieved in the (i) UNIX and (ii) Windows NT operating systems. (a) From the point of view of the device driver, data may be read from an I/O device using polling, interrupt-driven programmed I/O, or direct memory access (DMA). Briefly explain each of these terms, and in each case outline using pseudo-code (or a flow chart) the flow of control in the device driver when reading data from the device. [14 marks] (b) From the point of view of the application programmer, data may be read from a device in a blocking, non-blocking or asynchronous fashion. Using a keyboard as an example device, describe the expected behaviour in each case.

address every question

(a) A context-free grammar can be formally defined as a 4-tuple. Give a precise statement of what the components are. (b) Explain the difference between a grammar and the language it generates. [2 marks] (c) Explain what makes a grammar ambiguous, with reference to the grammar which may be commonly expressed as a "rule" E ::= 1 | 2 | X | E + E | E E | E where X is an identifier. [2 marks] (d) For the "rule" in part (c), give a formal grammar containing this "rule" and adhering to your definition in part (a). [2 marks] (e) Give non-ambiguous grammars each generating the same language as your grammar in part (d) for the cases: (i) "" is most tightly binding and "+" and "" have equal binding power and associate to the left. (ii) "" is most tightly binding and "+" and "" have equal binding power and associate to the right. (iii) "" binds more tightly than "+", but less tightly than "", with "+" left-associative and "" right-associative so that "a + b c d + d" is interpreted as "((a) + ((b (c d)))) + d". [2 marks each] (f ) Give a simple recursive descent parser for your grammar in part (e)(iii) above which yields a value of type ParseTree. You may assume operations mkplus, mktimes, mkneg acting on type ParseTree. [6 marks] 2 CST.2004.4.3 2 Economics and Law (a) What is "strategy" in game theory? [5 marks] (b) Explain the difference between a dominant strategy equilibrium and a Nash equilibrium. [5 marks] (c) Participants in a peer-to-peer file-sharing system can either cooperate (share their files with others) or cheat (try to download from others without making any contribution themselves). Write down a possible payoff matrix for their behaviour, and identify the Nash equilibrium. [5 marks] (d) Is this equilibrium Pareto-efficient, and, if not, what can be done to make it so? [5 marks]

(a) State carefully the Fermat-Euler theorem, defining any terms that you use. [4 marks] (b) Explain how calculating a n1 (mod n) for various values of a can be used to show that n is composite without actually finding its factors. By considering 561 = 3 11 17 or otherwise, show that the test is not perfect and suggest an improvement to make it more selective. [6 marks] (c) Derive the RSA system for public key cryptography and explain how this can be used both to send messages that are kept secret from an interceptor and to prove the identity of a sender. [6 marks] (d) Show that knowledge of the secret key as well as the public key allows an interceptor to factor the modular base being used. [4 marks] 8 Discrete Mathematics Let (A, 6A) and (B, 6B) be partially ordered sets. (a) Define the product order on AB and prove that it is a partial order. [4 marks] The upper bound of a set S A is an element u A (but not necessarily in S) such that s S . s 6 u. The least upper bound of S is an upper bound of S that is less than every other upper bound of S. The greatest lower bound is defined similarly. A lattice is a partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound. (b) Prove that (N, |), the natural numbers under the divisibility order, form a lattice. [4 marks] (c) Given a set X, prove that (P(X), ), the power set of X under set inclusion, forms a lattice. [4 marks] (d) Does every subset of (N, |) have a least upper bound and a greatest lower bound? Justify your answer. What about (N0, |) and (P(X), )? [4 marks] (e) If (A, 6A) and (B, 6B) are lattices, show that AB is a lattice under the product order. [4 marks] 5 [TURN OVER CST.2001.1.6 SECTION D 9 Programming in Java For each of the following areas, write brief comments on the way in which Java and its libraries have been designed to try to prevent programmers from making undetected errors and to ensure that code runs on all possible brands and models of computer, yielding the same results in each case. (a) Programmers who get mildly confused about syntax or who make typing errors. [4 marks] (b) Groups of programmers working on libraries that will form part of some large project. [4 marks] (c) Numbers, characters, trig functions and so on. [4 marks] (d) Opening files, reading or writing and then closing them. [4 marks] (e) Other features of Java not falling centrally within any of the above categories. [4 marks] 10 Programming in Java For each of the following ML definitions write, explain and comment on the closest reasonable Java equivalent code-fragment that you can construct. (a) fun fact n r = if n = 0 then r else fact (n-1) (n*r); [4 marks] (b) datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree * 'a tree; [4 marks] (c) val v = [1,2,3,7]; val v2 = map (fn n=>n*n:int) v; [4 marks] (d) exception Disaster of int; raise Disaster 99; [4 marks] (e) fun recursiveLength nil = 0 | recursiveLength (a :: b) = 1 + recursiveLength b;

(a) Describe the structure of splay trees used to represent a set of key-value pairs. [5 marks] (b) Describe how new key-value pairs are added to the tree, how the value associated with a given key can be looked up, and how to delete a pair with a given key. [5 marks] (c) State without proof the attractive properties of splay trees. [4 marks] (d) Describe the ternary tree structure used to hold a dictionary of key-value pairs where the keys are variable-length strings. Illustrate the mechanism by showing the structure after items with keys MIT, SAD, MAN, APT, MUD, ADD, MAG, MINE, MIKE, MINT, AT, MATE and MINES have been added in that order to an initially empty ternary tree.

(a) Define a polymorphic datatype 'a seq for lazy sequences, and define functions head and tail to return the first element and the rest of the sequence respectively. [1 mark each] (b) Define a function pick with the following type: 'a pick : 'a list -> ('a * 'a list) seq which returns a sequence of pairs (x, xs) as in these examples: (i) pick [1,2,3,4] returns a sequence with elements (1,[2,3,4]), (2,[1,3,4]), (3,[1,2,4]), (4,[1,2,3]). (ii) pick [1,2,1,2] returns a sequence with elements (1,[2,1,2]), (2,[1,1,2]), (1,[1,2,2]), (2,[1,2,1]). [4 marks] (c) Define a function explodeseq with type explodeseq : 'a list seq -> 'a seq which creates an element in the output sequence from each element in each list of the input sequence. [6 marks] (d) Define a function implodeseq with type implodeseq : int -> 'a seq -> 'a list seq which transforms a sequence of elements into a sequence of lists whose length is specified in the int argument. The last list in the output sequence may contain fewer elements.

In c code please, write program that reads a person's first name and last name separated by spaces Write java program that asks the user to enter 2 integers, obtains them from the user, determines if they are even or odd numbers and prints their sum, product, difference, and quotient (Division).

In (1) and (2) below, the words in the sentences have been assigned tags from the CLAWS 5 tagset by a stochastic part-of-speech (POS) tagger: (1) Turkey NP0 will VM0 keep VVI for PRP several DT0 days NN2 in PRP a AT0 fridge NN1 (2) We PNP have VHB hope VVB that CJT the AT0 next ORD year NN1 will VM0 be VBI peaceful AJ0 In sentence (1), Turkey is tagged as a proper noun (NP0), but should have been tagged as a singular noun (NN1). In sentence (2), hope is tagged as the base form of 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 stochastic POS tagger. [7 marks] (b) Explain how the probability estimates from the training data could have resulted in the tagging errors seen in (1) and (2). [6 marks] (c) In what ways can better probability estimates be obtained to improve the accuracy of the basic POS tagger you described in part (a)? For each improvement you mention, explain whether you might expect it to improve performance on examples (1) and (2).

Explain how the word "protected" is used in Java, commenting about when and why a programmer might use it rather than the alternative legal words that can appear in similar places. Why will you hardly ever use "protected" in small programs that you write and run for yourself? [10 marks] 4 Operating Systems For each of the following, indicate whether the statement is true or false, and explain why this is the case (no marks will be awarded for an answer with no explanation). (a) Round-robin scheduling can suffer from the so-called "convoy effect". (b) System calls are an optional extra in modern operating systems like Windows 2000. (c) A paged virtual memory is smaller than a segmented one. (d) In UNIX, hard-links cannot span mount points. (e) Direct memory access (DMA) makes devices go faster. [2 marks each] SECTION B 5 Foundations of Computer Science (a) Write brief notes on the following: (i) Re-coding a function to make it iterative. [4 marks] (ii) The difference between depth-first and breadth-first search. [4 marks] (iii) ML's exception-handling facilities. [4 marks] (b) Code a function whose input is a list of integers and whose output is the list of all the integers that can be expressed as the sum of one or more of the supplied integers. For example, given [1,5,10] a correct output is [1,5,10,6,11,15,16]; the order of the elements in the output does not matter. [5 marks] (c) Modify the function that you coded above so that the elements of its output appear in numerical order and without repetitions

(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 an instance of it and derive an integer n that you would use in any formulae relating to the cost of solving that instance. [3 marks] (c) What is a non-deterministic Turing Machine? Supposing that some computation of such a machine takes N steps, what information needs to be reported to describe exactly how the computation proceeded? In what way is 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) Briefly describe the concept of coroutines as provided in BCPL, and outline the effect of the library functions createco(f, size), deleteco(cptr), callco(cptr, val), and cowait(val). [6 marks] (b) Discuss the relative merits of BCPL coroutines versus those of threads such as provided in Java. [6 marks] (c) Outline the overall design and organisation of a BCPL program to perform discrete event simulation using coroutines to implement the simulated activities. Concentrate on the design of the simulation event loop, the organisation of the priority queue and what functions you would provide to simplify the implementation of the activities. It would probably be sensible to adopt a programming style similar to that used in Simula 67. You should hold simulated time as a global (integer) variable. [8 marks] 5 Operating Systems II (a) Most conventional hardware translates virtual addresses to physical addresses using multi-level page tables (MPTs): (i) Describe with the aid of a diagram how translation is performed when using MPTs. [3 marks] (ii) What problem(s) with MPTs do linear page tables attempt to overcome? How is this achieved? [3 marks] (iii) What problems(s) with MPTs do inverted page tables (IPTs) attempt to overcome? How is this achieved? [3 marks] (iv) What problems(s) with IPTs do hashed page tables attempt to overcome? How is this achieved? [3 marks] (b) Operating systems often cache part of the contents of the disk(s) in main memory to speed up access. Compare and contrast.