The operating system typically provides each process with the illusion that it runs in a contiguous piece of memory. State the problem of external fragmentation in memory where processes have variably sized memory partitions. Describe how paged virtual memory solves this problem, and any time and space costs it introduces. (b) Consider a 64 bit machine architecture providing 48 bit virtual addressing where the operating system uses a 4-level page table structure where a page is 4096 bytes and each page table entry is 8 bytes in size. (i) Show how the virtual address 0x00be.efc0.ffee is mapped to a physical address using the 4-level page table. You should give the size of each level in the page table in terms of both bytes and entries, as well as the size of a page table. (ii) Assume a memory access takes 40 ns, and the machine provides a Translation Lookaside Buffer (TLB) with a hit rate of 90% and a search time of 10 ns. What is the effective memory access time?

answer all qustions

You are commissioned by a customer to design a toy robot that children will be able to control using a smartphone app. This app will also enable them to program the robot using a simple scripting language. To simplify the networking, all communications between the app and the robot flow over wifi via your server. (a) Discuss the ethical and legal implications. [4 marks] (b) Your customer decides to incorporate a microphone so that the robot can also recognise spoken commands. To save battery life, the speech recognition will be done in the server. What effect does this have on the ethical and legal situation? [4 marks] (c) What practical advice can you give your customer about mitigating the legal risks? [4 marks] (d) Your customer now wants to include a camera so that the robot can recognise gestures as well. Does this create any further ethical or legal risks, and if so, what might be done about them? [4 marks] (e) How might the situation be affected by Brexit?

A one-person game (such as Rubik's cube, or peg solitaire) has a finite number of possible states, some of which count as winning. A move is a step from one state to another. From each given state, the player can choose from a set of (zero or more) possible next moves. We call a state winnable if a winning state can be reached from it in zero or more moves. For simplicity, assume that states are coded as integers. Also assume that we are given functions winning(x) returning true or false and next(x) returning the list of states that can be reached in one move from state x. (a) The following code is an attempt to implement the notion of winnable: fun exists p [] = false | exists p (x::xs) = p x orelse exists p xs; fun winnable x = winning x orelse exists winnable (next x); Briefly explain how this code works. Also describe its main limitation: how it can fail to find a winning state that is only a few moves away. Illustrate this point by giving specific definitions of winning and next. [5 marks] (b) Modify the code above to yield the function winpath x, which returns the list of states from x to the winning state found or, alternatively, the empty list to indicate that no winning state was found. [4 marks] (c) Sometimes we are only interested in a winnable state if it is only a few moves away from the current state. Modify your solution from part (b) to obtain the function bounded_winpath n x, which looks for winning states that are at most n moves away from x. [3 marks] (d) Use your solution from part (c) to obtain the function new_winpath x, which has the same objective as winpath x, but without the limitation mentioned in part (a). Briefly explain why the limitation no longer applies and the price that has been paid for this. [5 marks] (e) Briefly outline an alternative approach to correcting the limitation mentioned in part (a), using the notion of a queue. What are the advantages and drawbacks of this approach? [3 marks] For full credit, code should be concise and clear. Exceptions may be useful in this but are not required. 2 CST0.2017.1.3 2 Foundations of Computer Science (a) Define an ML datatype for infinite lists, without the possibility of finite lists. Briefly illustrate programming techniques for your datatype by declaring (i) a recursive functional (analogous to map for ordinary lists) that applies a given function to every element of an infinite list. (ii) a function for generating infinite lists of the form x, f(x), f(f(x)), . . . for any given f and x. [6 marks] (b) Briefly explain why the function analogous to append (@) for ordinary lists is of no value for your infinite list data type. Code a function to combine two arbitrary infinite lists, yielding a result that includes the elements of both lists. [3 marks] (c) Use the functions declared in your previous solutions to express an infinite list consisting of all numbers of the form 5i 7 j 9 k for integers i, j, k 0. [3 marks] (d) The list [1, 5, 7, 25, 9, 35, 35, . . .] is a legitimate solution to part (c) above, but note that the integers are out of order. Code a function to merge two ordered infinite lists, and use that to modify your previous solution to yield the same set of numbers but in strictly increasing order. Briefly comment, with justification, on whether merge sort for ordinary lists can be generalised to infinite lists. [8 marks] For full credit, code should be concise and clear. 3 (TURN OVER) CST0.2017.1.4 SECTION B 3 Object-Oriented Programming An online retailer uses custom Java software to manage their inventory and sales. (a) Each product sold is represented using an immutable Product object. Explain what is meant by immutable, how immutability is typically achieved in Java and the advantages of using immutable objects in general. [4 marks] (b) Product objects are requested through a Product getProduct(long code) method, which returns a reference to a Product object given a valid product code. Product information is often re-requested as customers make their selections so the 10,000 most recently accessed Product objects are cached in memory. Uncached Product objects are created with information retrieved from a database when requested. (i) The cache uses a java.util.HashMap and a custom implementation of a doubly-linked list. The list keeps an ordering over the Product objects where more recently used objects are at the front. The HashMap provides fast lookup into the list. Show that this scheme gives a constant (O(1)) running cost for getProduct(), ignoring the cost of the database lookup. [3 marks] (ii) Create a class Store that implements the cache as described. You need only define getProduct and any state or definitions it needs. All other state and methods can be ignored. You may assume the existence of a method loadFromDatabase(long code) that will create a Product object for product code code or return null if the code is invalid, and that a Product object has a long getProductCode() method that returns its product code. [10 marks] (c) A customer's basket of items, represented by a class Basket, can be viewed as a list of products. Therefore Basket might extend LinkedList. Compare this approach to a Basket that contains ("has-a") LinkedList instead. [3 marks] 4 CST0.2017.1.5 4 Object-Oriented Programming (a) Give four advantages of Java's checked exceptions over return values for error indication. [4 marks] (b) Comment on the appropriate use of Java's checked exceptions within public, protected and private methods. [6 marks] (c) Consider a method that can encounter at least two errors (Error1 and Error2 ). Compare and contrast the following approaches to providing exceptions for these errors. (i) throw new MethodError(), where MethodError is a direct subclass of Exception. (ii) throw new Exception() for both errors. (iii) throw new MethodError(errortype), where MethodError directly subclasses Exception and contains state recording which error occurred (initialised by parameter errortype). (iv) throw new Error1() and throw new Error2(), where Error1 and Error2 directly subclass MethodException, which directly subclasses Exception. (v) throw new Exception("Error1") and throw new Exception("Error2"). (vi) throw new Error1() and throw new Error2(), where the classes Error1 and Error2 directly subclass Exception.

Consider display technologies for hand-held devices. (a) Explain the principles of operation of each of the following. Note: You may illustrate your answers with a diagram. (i) Liquid crystal displays [5 marks] (ii) Electrophoretic (electronic paper) displays [5 marks] (b) Compare and contrast their characteristics. [6 marks] (c) Explain how liquid crystal and electrophoretic displays can show coloured images. [4 marks] 4 CST0.2017.3.5 4 Graphics Consider rendering a triangular mesh using OpenGL. A uniform material is used for the entire mesh and the reflection model of the material consists of ambient, diffuse and specular components. There are two point light sources in the scene. Given these assumptions, answer the following questions: (a) Gourand and Phong shading are two different methods of interpolating colours between vertices. Explain how each method interpolates colours. [5 marks] (b) Discuss the trade-offs in terms of quality and computational costs for Phong and Gourand shading. Assume that the number of rendered pixels is much larger than the number of vertices. What kind of artefacts can one of the methods produce and what is the reason for those artefacts? [7 marks] (c) For each of Gourand and Phong shading, explain how you would implement each shading method using vertex and fragment shaders in OpenGL. Complete the diagram shown below by listing all inputs, outputs and uniforms for each shader. Then, explain what is computed in each shader in the case of both shading methods. There is no need to write equations or code, but you may include them if it helps your explanation. Vertex Shader Fragment shader in: in/out: out: uniforms: uniforms: Your company has been asked to design and implement an interface called GestureDriver which is envisioned to be a remote driving interface based on visual gesturing and speech. Hand motions will be tracked based on colour vision, and the system will classify the gestures using a simple geometric model. The gestures will be mapped into six motion commands: start, right, left, forward, reverse, and stop. These commands can also be provided via speech and transmitted to the remote vehicle. The major requirements are that the system displays the current location of the vehicle to the user, monitors location change, captures the motion and vocal command of the user in real time, and moves the vehicle based on the received command. (a) One of the Principles of Good Design is to 'balance automated and human control'. Give four examples and explain how this can be achieved for the context provided above. [4 marks] (b) Describe, with an example, each of the five different interaction spaces beyond the desktop as classified by Winograd. Briefly discuss which one(s) would be more appropriate to use for creating this application, and why. [6 marks] (c) Assuming that the initial system status is OFF, draw a task model for the user using the GestureDriver interface with the goal of reversing the vehicle they are operating remotely. The task model should capture activities at multiple levels starting with at least three activities. Explain any sequential dependencies you identify. [8 marks] (d) Describe one generic problem that task analysis can help identify, and give an example of how this can be done. [2 marks] 6 CST0.2017.3.7 6 Interaction Design (a) Describe three problems that affect the data and requirements gathering process, and provide one solution for each problem. [3 marks] (b) State and briefly describe each of the six principles of Gestalt psychology that have implications for user interface design. Explain how each of the six principles of Gestalt psychology have been employed in the design of the interface given in the figure below. [12 marks] (c) A company has just completed the heuristic evaluation of a digital music player, and identified the problem areas provided in the list below. Indicate which usability principle or principles each problem violates for five of the following problems. [Note: it is possible that each problem violates more than one usability principle, and that the same principle is violated multiple times for different problems.] P1. Inconsistencies between menus and buttons. P2. Some language does not correspond with user terminology. P3. There are buttons that the user may not realize are buttons. P4. Not all buttons have tooltips. P5. There are inconsistencies with Windows operating system standards. P6. Undo commands basically unsupported. P7. Help content uses different terminology from application. P8. System does not always provide user with enough information about the task being performed. [5 marks] 7 (TURN OVER) CST0.2017.3.8 SECTION D 7 Machine Learning and Real-world Data Suppose that a very large collection of documents describing the University of Cambridge has been collected. Your task is to build a classifier which assigns sentiment to each document, using the classes: positive, negative and neutral. (a) There is no ground truth sentiment associated with the documents, but 200 have been manually classified by three human annotators. Fleiss' Kappa is 0.65 for this set. Explain what Kappa is and outline how it is calculated. You do not need to state the full formula for Kappa. [4 marks] (b) Given the limited amount of annotated data, you decide to classify the documents using a standard sentiment lexicon. Explain how you would perform an experiment to do this.