A certain program has to maintain an array, count, of N counters which are all initialised to zero. The value of counter i can be incremented by one by the call: increment(i), and this is the only way the program changes counter values. Two variables, mincount and maxcount, must always hold the smallest and largest of the counter values whenever the point of execution is not within the function increment. You may assume that increment is called about 1000N times when the program is run and that its argument is typically uniformly randomly distributed between 1 and N, but on some runs it cycles through the numbers 1 to N in order 1000 times. (a) Describe, in detail, an efficient data structure and algorithm to use when N is expected to be about 10. (b) Describe, in detail, an alternative data structure and algorithm to use when N is about a million. (c) Suppose your algorithm for (a) above were used when N = 106 , estimate how much slower it would be compared with your algorithm for (b). [5 marks] 2 Computer Design (a) What is a data cache and why is it vital for high performance processors? (b) What is a cache line and how big is it likely to be? (c) What is a page and how big is it likely to be? (d) What is a snoopy cache and in what system is it likely to be used? (e) A computer system has the following memory parameters: memory level access time in clock cycles first level cache 1 second level cache 3 main memory 100 If the probability of a hit in the first level cache is 80%, what hit rate do we need in the second level cache if the mean access time is to be two clock cycles? For this part, use the approximation that the cache line length is just one machine word

(a) Sets containing integers can be represented as int list values. Consider two such representations called unordered and ordered. In the former elements can appear in any order; in the latter elements are required to be in ascending order. In both representations elements must not be repeated. (i) Using the unordered representation give ML functions corresponding to set intersection and set union. (ii) For your answers to Part (a)(i) give the associated time complexities, assuming both input sets have at most n elements. (iii) Now, using the ordered representation, give ML functions corresponding to set intersection and set union along with their time complexities, noting reasons for any differences in complexity compared to those for the unordered representations. [4 marks] (iv) Without giving any ML code, suggest a technique whereby set intersection for unordered can be implemented in O(n log n) time. [1 mark] (b) One often hears "in ML, all functions take exactly one argument". Explain two techniques which enable us to circumvent this rule, illustrating your answer by giving ML definitions for the standard map and a variant which "takes the same arguments in the same order". Call the variant map'. [3 marks] (c) For each of the five following ML expressions give definitions of f, g, h, xs ys and zs (as appropriate) which cause the expression to evaluate to true, or explain, giving reasons, why this is impossible. (The functions map and map' are as discussed in Part (b).) (i) map f [1,2] = [[1,2],[3,4]] (ii) map g [1,2,3,4] = [[1,2],[3,4]] (iii) map (map h) xs = [[1,2],[3,4]] (iv) map map' ys = [[1,2],[3,4]] (v) map map zs = [[1,2],[3,4]]

1. Consider the following code snippet, where a voting service is accessed through two RPC calls:

is_vote_cast(voter_id): returns if the voter specified by the 'voter_id' has already cast her vote ('YES ' or 'NO)

cast_vote(cand_id, voter_id): casts the vote for the specified candidate by the specifier voter

voter_id = '243545'

cand_id = '90888'

if (proxy.is_vote_cast(voter_id) == 'NO') {

proxy.cast_vote(cand_id, voter_id)

}

Describe the ramification of three RPC call semantics: (i) Maybe, (ii) at-least-once, and (iii) at-most-once, on these two calls. Which semantic is best fit for which functions?

(a) Describe on-off flow control. In what circumstances is it appropriate? [4 marks] (b) Describe the operation of window-based flow control. [4 marks] (c) What happens if window-based flow control is used on a flow passing through a highly loaded resource (e.g. router) that is not participating in the flow control protocol? [4 marks] (d) How is this addressed in the Internet? [4 marks] (e) What are the advantages and disadvantages of having Internet routers participate in window-based flow control of every TCP connection? [4 marks] 4 Concurrent Systems and Applications (a) Transactions provide a means of grouping together a collection of separate operations to form a single logical operation. Explain the difference between implementations that enforce strict isolation and non-strict isolation. What are dirty reads and cascading aborts? [8 marks] (b) Optimistic Concurrency Control (OCC) is a mechanism used to enforce isolation of transactions. (i) Explain the OCC algorithm. [4 marks] (ii) Is deadlock possible? Are cascading aborts possible? [2 marks] (iii) Under what circumstances might this mechanism yield poor performance? [1 mark] (c) Explain how to use a write-ahead log to provide persistence by detailing what information must be written to the log and how it can be used to recover from a fail-stop catastrophe. What are checkpoints and why are they useful?

(a) Give a program which gives different results according to whether dynamic or static binding is used. [3 marks] (b) Summarise two different methods of implementing functions which have free variables statically bound in an outer nested function, paying particular attention to (i) the lifetime of any storage used and (ii) any language restrictions which the implementation requires. Note also, for each case, what the effect is of assignment to such free variables, e.g. when calls to g() and h() are interleaved in f(int x) { int a = x+7; int g() { a++; } int h(int y) { return a+y; } ... } [8 marks] (c) Give a program in which a function is called recursively without any value or function being defined recursively. [3 marks] (d) Give a program which produces three distinct results according to whether parameters are passed by value, by reference, or by value-result. [3 marks] (e) Explain the likely storage layouts for Java objects p and q respectively of classes P and Q defined by class P { int a,b; int f() { } } class Q extends P { int c; int f() { } int g() { } }

Write program that reads a set of integers and then finds and prints the sum of the even and odd integers 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 Write program that prompts the user to read two integers and displays their sum. Your program should prompt the user to read the number again if the input is incorrect

We have a 2-player game in which players A and B take turns to remove either the leftmost or rightmost coin from of a row of coins of varying values. When no coins are left, the player with the higher total value wins. Example: For a row of coins with values given by the list [20, 40, 30, 15], player A must select the rightmost coin (with value 15) in order to win with a total amount of 55, leaving player B with a total amount of 50. (a) You are given three helper functions. The first function, poplast, takes a list and returns the list without its last element. The second function, last, takes a list of integers and returns the last value of that list. The third function, max, takes two integers and returns the larger of the two values. Using these helper functions, write a recursive function winning diff that takes a list of integers (representing the row of coins), and that returns the final difference of amounts between players A and B, assuming that player A goes first, and that player B plays optimally. If the difference is positive, player A wins, if it is negative, B wins. [8 marks] (b) We are interested in implementing a functional deque that computes poplast and last in amortised constant time and that also enables access to the first element in amortised constant time. Write the code for the data type, and functions poplast and last. You may also need to code a function norm that guarantees amortised constant time in all circumstances. [8 marks] (c) Consider the complexity of your algorithm for winning diff for Part (a). For this question, assume that the three helper functions compute in constant time. (i) Give the recurrence relation T(n) for the running time of your algorithm, where n is the number of coins in the row.

(a) When defining space-complexity we use two-tape Turing Machines, with a read-only tape for input data and a read-write working tape. We count only the space used on the work tape. What difference would be made if we worked with standard one-tape Turing machines, loaded the input data onto the tape to start with and measured space in terms of total tape cells touched by the end of the computation? [4 marks] (b) Comment on the following: "The problem of finding a factor of a number N is NP, because if we have a factor P of N we can do a simple trial division and check it in time related to log(N). Thus finding factors of numbers of the form 2p 1 (these are known as Mersenne Numbers) is a problem in the class NP". [2 marks] (c) Define the class co-NP. State an example of a problem that lies in it. [2 marks] (d) What is a witness function for an NP problem? Why might some problem such as 3-SAT have many different witness functions associated with it? [2 marks] (e) Give and justify a relation between NTIME(f(n)) and SPACE(f(n)). [4 marks] (f ) Matchings on bi-partite graphs can be found in polynomial time. The matching problem on tri-partite graphs is known to be NP-complete. Does this suggest that the corresponding problem with a graph whose nodes are partitioned into four sets ("quad-partite" matching) is liable to be exponential in complexity?

(a) Many computer scientists believe that languages with strong compile-time type checking are better than those that are typeless, dynamically typed, or are weakly type checked. Discuss the reasons for this view. [7 marks] (b) If strictly-checked data types are seen as good, discuss whether augmenting a language with many more primitive data types is better. Consider, in particular, the possibility of incorporating into a language such as Java many new numerical types such as packed decimal of various precisions, scaled arithmetic, and new types to hold values representing distance, mass and time. How would these additions affect the readability and reliability of programs? [7 marks] (c) Some languages allow different modes of calling of function arguments, such as call by value, call by reference and call by name. Discuss the advantages and disadvantages of incorporating the argument calling modes into the data types of functions.

(a) OLAP and OLTP. (i) What is on-line transaction processing (OLTP)? [2 marks] (ii) What is on-line analytic processing (OLAP)? [2 marks] (iii) If you were designing a relational database system, how would your approach to schema design differ for OLTP and OLAP systems? [3 marks] (iv) In OLAP, what is the meaning of the terms drill down, roll up, and slice? [3 marks] (v) What is a star schema? [1 mark] (b) Suppose we have the following relational schema, Supplier(sid:integer, name:string, postcode:string) Parts(pid:integer, name:string, description:string) SuppliedBy(sid:integer, pid:integer, weight:integer) where the underlined attributes represent the primary keys of the associated relation. The table SuppliedBy implements a relationship between suppliers and parts indicating which parts are supplied by which supplier using foreign keys pointing into the Parts and Supplier tables. The weight attribute is the parts weight in grams. Write an SQL query that will return a list, without duplicates, of all postcodes associated with suppliers of parts less than one kilogram in weight. [5 marks] (c) Define and explain the ACID properties of database transactions. [

) Explain as simple a procedure as possible that converts lambda expressions into terms that use only these combinators. At this stage you are not expected to be concerned with efficiency, but you should make it clear why your combinator forms relate to the lambda expressions that you start with. [5 marks] (c) Illustrate the scheme you have given above by applying it to the lambda expression x.y.((y x) y) and explain why in practical reduction to combinators at least additional symbols B and C are normally introduced. [5 marks] (d) Suppose that you have primitive functions available that can represent integers, booleans, arithmetic and an "if . . . then" operation (and so on, as necessary). Show how to convert the following ML-like code first into raw lambda calculus and then into combinator form: fun f n = if (iszero n) 1 (double (f (subtract1from n))); Note that the code has been presented in a way intended to show the functions used to perform arithmetic. You may assume the availability of a Y operator if that helps. [6 marks] 11 Semantics of Programming Languages (a) Discuss the operational semantics and type rules for subsumption and downcasting in a language with record subtyping. Identify clearly what is guaranteed by type-checking and run-time checks. [8 marks] (b) Explain, with examples, the subtype rule for function types T1 T2. [4 marks] (c) Explain, with examples, how a language with record subtyping, functions, and ML-style references can be used to express simple object idioms.

(a) A programmer plans to replace single-precision floating-point arithmetic in a subroutine with a fixed-point implementation that is guaranteed to have at least the same range and precision. Roughly how many bits must the fixed-point representation have? (b) The designers of a new computer architecture provide an instruction that uses the fixed-point implementation of Part (a) to sum long lists of single-precision floating-point numbers. This implements the rounding and re-normalisation only once at the end of the operation. What are the benefits of such an instruction compared with folding the standard two-argument addition operator over the list? (c) A tri-diagonal square matrix has all entries zero except for the leading diagonal and the two diagonals on either side of the leading diagonal. (i) What is the execution cost, in terms of the number of operations, of Gaussian Elimination without pivoting, both for 'school method' and for L/U decomposition? (ii) Without any pivoting, the L/U decomposition of a tri-diagonal matrix results in L having ones on its leading diagonal and another partial diagonal of non-zero coefficients and U also being largely all zeros. Write out the equations or pseudocode that determine L and U. What is the cost of solving a tri-diagonal set of simultaneous equations?

answer every question