You have been provided with the description of a programming language, J, intended for scripting applications. Its syntax is similar to a cut-down version of Java in that it consists of function definitions which have bodies containing if-then-else, while-do, assignments and (typed) declarations of variables. Only one statement or keyword may occur on a line so that it is sufficient to describe the start of a loop iteration with its line number. You need to explain to your boss the alternatives for implementing this so that a decision may be made as to the best implementation strategy. The choice is between: (a) compiling J to machine code; (b) compiling J to "interpreted byte code", and then interpreting this; (c) parsing J to a syntax tree representation and then interpreting this using a function which walks the tree; (d) keeping J in a text file and then interpreting it by reading each line (and acting on it) as and when the line is required. For each of (a)-(d), (i) summarise the main phases of work that are done before execution in each case, giving a brief explanation of the main actions of the main interpreter loop (if any) during execution, and (ii) for each of the following possible erroneous forms, explain whether the error would be found before or during execution: malformed syntax, undeclared variable, type error, division by zero. 

 

address every question

(a) We wish to produce two algorithms: one which draws the outline of a circle and one which draws a filled circle. (i) Describe an efficient algorithm which will draw a one-pixel wide outline of a circle of integer radius, R, centred on the origin. [10 marks] (ii) Describe the modifications required to your algorithm to make it draw a filled circle. [3 marks] (b) Given a function drawline(x1,y1,x2,y2), describe an algorithm for drawing a Bezier cubic curve to a specified level of accuracy using only straight lines. 6 Artificial Intelligence (a) Describe the way in which a problem should be represented in order to allow its solution using a heuristic search technique. [5 marks] (b) Define what it means for a search algorithm to be complete, and to be optimal. (c) Define what it means for a heuristic function to be admissible, and to be monotonic (d) Describe the operation of the A? heuristic search algorithm. [5 marks] (e) Prove that the A? heuristic search algorithm is optimal when applied in conjunction with a monotonic heuristic. State the conditions under which the algorithm is also complete, and explain why this is the case.

The language L has expression syntax e ::= n | skip | fn x:T e | e1 e2 | x | e1 := e2 |!e | refe | ` with types T ::= int | unit | T1 T2 | T ref It is intended to have a call-by-value semantics. (a) Define the set of values for L. [2 marks] (b) Give type rules and reduction rules for the store-related expressions e1 := e2 |!e | refe | `. Define clearly what the type environments and stores you are using are. [10 marks] (c) Discuss possible alternative choices for the semantics of the operations in part (b), paying particular attention to: (i) what can be stored, (ii) store initialisation, and (iii) the results of assignments. Illustrate your answer with type rules and reduction rules as appropriate, and comment on any pragmatic advantages or disadvantages. [8 marks]

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.

(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.

A seismic probe bores itself into the seabed, going as deep as it can before running out of fuel. This takes about five minutes. It rotates its spiral drill head at rate R(t) that follows a pre-programmed profile. Its downwards velocity y is proportional to R and to the square-root of the probe's weight w, and is given by y = 3.6 R(t) w. The weight of the probe is the weight of its fuel, which starts at 1500 plus its own intrinsic weight, which is fixed at 35. The fuel weight decreases at a rate of 1.2 R(t). (a) Give the state vector for a forwards FDTD simulation of this system using Euler's Method. [1 mark] (b) Assuming a function is provided that returns R(t), give a program that uses Euler's Method (a straightforward, forward finite-difference simulation) to determine the depth achieved. [4 marks] (c) Describe the errors you might expect if you chose a time step that was inordinately small or inordinately large. What is the maximum time step for Euler's method to remain stable in this system? Suggest, with justification, a suitable time step. [6 marks] (d) Recall that a backwards stencil uses the values at the end of the timestep to determine the rate of change during that timestep. When is this usable and useful in general? Is it sensible for this application? Give modified code that implements the backwards stencil method.

We wish to store a dynamic collection of records, each of the form {timestamp, value}, where value is a real number. The collection should support the operations append_newer(t,v) to add a new record (which we can assume has a larger timestamp than any existing record), pop_oldest() to remove the oldest record, and get_oldest() to inspect the oldest without removing it. (a) Define the Queue abstract data type. Describe an implementation using a linked list. Explain how to use it for this dynamic collection of records. [3 marks] The collection should also support get_max(), which returns a pointer to the record with the highest value in the collection. Ties may be broken arbitrarily. (b) A simple implementation of get_max() simply scans through the entire list. What is the worst-case cost, given the number n of items in the collection? [1 mark] (c) An engineer friend suggests keeping a pointer maxrecord to the record with the largest value so that the entire list only need be rescanned when the item pointed to by maxrecord is removed. Give an example to show that n operations could take (n 2 ) time. [3 marks] (d) Explain the terms amortized cost and potential method. Explain the relationship between aggregate true costs and aggregate amortized costs. [4 marks] (e) Devise an implementation in which all operations have O(1) amortized cost, and use the potential method to justify your answer. Illustrate what happens when we start with a list of values [5, 8, 3, 6, 2] where 5 is oldest and 2 is newest, and then append a newer record with value 7. [Hint: Where is the largest item newer than maxrecord, and the largest item newer than this, and so on?]

: 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 Write Java program that will prompt the user to input a size of an array. Create an array of type int. Ask a user to fill the array. Create functions sortArray() and mostFrequency().

Write program that first gets a list of integers from the input and adds them to an array. The input begins with an integer indicating the number of integers that follow program that first gets a list of six integers from input. The first five values are the integer list. The last value is the upper threshold. Then output all integers less than or equal to the threshold value.

(a) Consider a directed acyclic graph with V vertices and E edges. (i) What is meant by a total order on the vertices consistent with the edges? [2 marks] (ii) Describe an O(E + V ) algorithm to compute such a total order. [3 marks] (b) Consider a directed graph with non-negative edge costs and with a given start vertex s. (i) Dijkstra's algorithm computes distances from s to every other vertex. Give psuedocode for Dijkstra's algorithm. [4 marks] (ii) Dijkstra's algorithm can be implemented using a Fibonacci heap. State the complexity of using this implementation. Justify your answer carefully. [Note: Your answer should include mention of amortized costs.] [4 marks] (c) Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s. (i) Devise an algorithm to compute distances from s in O(E +V ) time. Justify why your algorithm is correct. [4 marks] (ii) Explain, with an example, why Dijkstra's algorithm might take (V log V ) time.

Recall that a simple path in a graph is a path with no repeated nodes. Consider the following two decision problems: Given a graph G = (V, E), a positive integer k, source s V and a target t V , is there a simple path from s to t of length at least k? Given a graph G = (V, E), a positive integer k, source s V and a target t V , is there a simple path from s to t of length at most k? One of these problems is known to be in P while the other one is known to be NP-complete. (a) Which of the two problems is in P and which is NP-complete? [2 marks] (b) Describe a polynomial time algorithm for the problem that is in P. [6 marks] (c) Give a proof of NP-completeness for the problem that is NP-complete. You may assume the NP-completeness of any problem, such as Hamiltonian Cycle, mentioned in the lecture course.

Assume a simple movie database with the following schema. (You may assume that producers have a unique certification number, Cert, that is also recorded in the Movie relation as attribute prodC#; and no two movies are produced with the same title.) Movie(title,year,length,prodC#) StarsIn(movieTitle,movieYear,starName) Producer(name,address,cert) MovieStar(name,gender,birthdate) (a) Write the following queries in SQL: (i) Who were the male stars in the film The Red Squirrel? [1 mark] (ii) Which movies are longer than Titanic? [2 marks] (b) SQL has a boolean-valued operator IN such that the expression s IN R is true when s is contained in the relation R (assume for simplicity that R is a single attribute relation and hence s is a simple atomic value). Consider the following nested SQL query that uses the IN operator: SELECT name FROM Producer WHERE cert IN (SELECT prodC# FROM Movie WHERE title IN (SELECT movieTitle FROM StarsIn WHERE starName='Nancho Novo')); (i) State concisely what this query is intended to mean. [1 mark] (ii) Express this nested query as a single SELECT-FROM-WHERE query. [2 marks] (iii) Is your query from part (b)(ii) always equivalent to the original query? If yes, then justify your answer; if not, then explain the difference and show how they could be made equivalent. [6 marks] (c) SQL has a boolean-valued operator EXISTS such that EXISTS R is true if and only if R is not empty. Show how EXISTS is, in fact, redundant by giving a simple SQL expression that is equivalent to EXISTS R but does not involve EXISTS or any cardinality operators, e.g. COUNT. [Hint: You may use the IN operator.]

(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

Pure lambda-calculus does not have any built-in control structures or arithmetic. It just has lambda-expressions. (a) Using an untyped pure lambda calculus, explain how to model the natural numbers 0, 1, . . . together with a test for zero and addition and multiplication operations. [7 marks] (b) How can recursive function definitions be expressed in pure lambda calculus? Give a lambda-term for any special things that you need to introduce. [4 marks] (c) Suppose you are provided with a lambda expression that works with numbers in the sense of part (a) above and which will find the predecessor of any nonzero number. Express the factorial function in terms of the primitives that you introduced in parts (a) and (b). [5 marks] (d) Explain how a typical polymorphic typing system would respond to the various lambda-expressions you have given. If there were any that would fail to type-check, explain why: if everything you have written could be given valid polymorphic types, show what those types would be for a couple of the key expressions. [4 marks] Credit will be given for clarity and conciseness of presentation, and justification of why your lambda expressions apply in the general case will be preferred to sets of examples that merely illustrate them in particular cases.

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.

This question is about hash tables. (a) Briefly explain hash functions, hash tables and collisions. [3 marks] (b) Explain the open addressing strategy of collision resolution and the term probing sequence used in that context. [3 marks] (c) Explain quadratic probing and its advantages and disadvantages. [Hint: refer to primary and secondary clustering.] [3 marks] (d) Give a general mathematical expression for the probing function p(k, i) used in quadratic probing. The expression should yield a 0-based index into the table, referencing the key k, the probe number i, the hash function h, the table size m and the constants c1 and c2. [3 marks] (e) Does the following pseudocode implement a form of quadratic probing? If so, derive values for c1 and c2 in the equation you produced for part (d). If not, prove it doesn't. In either case, clearly justify your reasoning. [8 marks] def get(k): j = h(k) i = 0 while true: if T[j].key == null: raise NotFound if T[j].key == k: return T[j].payload i = i+1 if i == m: raise NotFound j = (i+j) mod m

This question is about Binary Search Trees (BSTs) and Red-Black Trees (RBTs). (a) Using a diagram, explain what a BST rotation is and its purpose. [3 marks] (b) Consider the following buggy pseudocode. 0 def mystery ( x ): 1 y = x . r 2 x . r = y . l 3 if y . l != null : 4 y . l . p = x 5 x . p = y . p 6 if x == x . p . l : 7 x . p . l = y 8 else : 9 x . p . r = y 10 y . l = x (i) Explain what it intends to do, give it a meaningful name, describe all the identifiers used (x, y, r, l, p) and the (intended) precondition and postcondition of the routine. [4 marks] (ii) Identify, explain and fix the bugs, one by one, referring to a diagram if useful. Finally, give a fully corrected version of the code. [8 marks] (c) State, with a proof or counterexample as appropriate, whether each of the following statements is true or false. (i) In an RBT with more than one node, at least one node is red. [2 marks] (ii) In a BST with n nodes, exactly n 1 rotations are possible.