answer the question clearly

Implement a videogame called JavaConk, a computerised version of the game of conkers. Two round conkers should be displayed on the screen. One conker is controlled by the computer, and constantly travels around the screen, bouncing off the sides if necessary. The other conker is controlled by the player, using the mouse. If the two collide, and if the sum of kinetic energies is less than a threshold set for this game, the computer conker will rebound at a new velocity determined by the collision speed. If the kinetic energy is larger than the threshold, one of the two will be smashed. The conker that will smash is determined by chance, but with probability weighted so that the one travelling more slowly is proportionally more likely to smash. The classes BasicGame, Ball, and OutOfBoundsException have already been coded. Relevant method signatures for these classes (and standard library class MouseEvent) are as follows: class Ball public Ball(int diameter, int xPos, int yPos, String colour) public int getX() public int getY() public void moveTo(int x, int y) throws OutOfBoundsException public boolean collidesWith(Ball other) public void smash() protected void draw() abstract class BasicGame implements MouseMotionListener public void mouseMoved(MouseEvent e) class OutOfBoundsException extends Exception public boolean overHorizontalBoundary() public int getXboundary() public int getYboundary() class MouseEvent extends Event public int getX() public int getY() Provide all necessary code to implement the required behaviour. [Hint: Kinetic Energy EK = 1 2mv2 .] [20 marksConsider the design of a Java application for the automated marking of exam questions on Java. The answer to each question consists of Java source code. Your application should read the text of each answer from a file, and check that actual lines of code expected by the examiner are included at any point in the answer. The examiners will want to calculate the average mark (out of 20) for each question, and also the total mark (out of 100) achieved by each candidate in a paper consisting of 5 questions. Model answers should take the form of an executable Java class, for example a class called question1model might contain the following method: protected void defineAnswer() { expectedLines.add("import java.io.*;"); expectedLines.add("public class helloWorld"); expectedLines.add("system.out.println(\"hello world\");"); } Provide a UML diagram showing the classes in the application, and write the basic code for each class, in order to achieve the above functionality. You may ignore error processing, and indicate repetitive passages of code by an ellipsis ". . .". [20 marI What is a hierarchical address space? Give an example of an address space which is hierarchical and one which is not. [3 marks] What is the Address Resolution Protocol? Describe its operation when used to resolve IP addresses to Ethernet addresses. Pay particular attention to the freshness of information. [7 marks] Information is transferred via a long, error-prone communication link. The link has a data rate of 10 Mbps and a constant delay. The bit error rate on the link is 1 bit in 104 . A forward error correcting coder is available which can act in the following settings: Data rate Error rate Code rate 10 Mbps 104 unity (no coding) 5 Mbps 105 half A simple ARQ protocol is used over the link. Packets have 32-bit CRCs. You may assume that the undetected error rate is less than 1 in 1020, that is, effectively zero. Information is sent in 1000-bit packets, with a window of one packet. At what link delay would it be beneficial to use the FEC coder?

ensure to answer all questions

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() { } } [3 marks] 4 CST.2005.13.5 6 Computer Graphics and Image Processing (a) In ray tracing, once we have determined where a ray strikes an object, the illumination at the intersection point can be calculated using the formula: I = Iaka + X i Iikd(Li N) +X i Iiks(Ri V) n . Explain what real effect each of the three terms is trying to model, how accurately it models the real effect, and explain what each of the following symbols means, within the context of this formula: I, Ia, i, Ii , ka, kd, ks,Li , N, Ri , V, n. [12 marks] (b) Compare and contrast the ray tracing and z-buffer algorithms. [8 marks] 7 Comparative Programming Languages (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. [6 marks] 5 [TURN OVER CST.2005.13.6 8 Databases (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

(O0) concepts with the aid of code examples (either C++or Java): Inheritance Over-riding.Over-loading Describe any differences between C++ and Java in how these O0 concepts are implemented? 3(0) 17 Marks] Describe C++ namespaces using a code example. Describe Java packages, again using a code example. How do C++ namespaces compare to Java packages? s(d) |5 Marks] What are inline methods in C+*/Java? Explain the terms accessor and mutator.

(a) Describe in detail an algorithm that returns the minimum distance from a point to a line segment in two dimensions. Ensure that you include all of your assumptions and all necessary mathematical calculations. [7 marks] (b) A quadratic Bezier curve is defined by three points, P1, P2, P3, and a parameter, t: P(t) = (1 t) 2 P1 + 2t(1 t)P2 + t 2 P3, 0 t 1 Describe an algorithm that draws the quadratic Bezier curve, using straight lines only, to within a tolerance . You may use the algorithm from part (a) and you may assume that you already have an algorithm for drawing a straight line. [8 marks] (c) Consider the control of detail in a curve that is represented by a sequence of many straight line segments. Describe how Douglas and Pucker's algorithm can be used to remove superfluous points. You may use the algorithm from part (a). [5 marks]

Consider the following grammar for expressions (where Id is a terminal symbol representing an identifier resulting from lexical analysis): Expr ::= 1 | 2 | Id | Expr + Expr | Expr / Expr | Expr ^ Expr | (Expr) (a) Explain in what principal respect this grammar is unsatisfactory. [1 mark] (b) Assuming further that + is to be left-associative, ^ is to be right-associative and / is to be non-associative (i.e. 2/2/2 is forbidden but (2/2)/2 and 2/(2/2) are allowed), re-write the grammar to reflect this. [4 marks] (c) List the terminal symbols and non-terminal symbols, and count the production rules both in the original grammar and in the grammar in your answer to part (b). Indicate the start symbol in both grammars. [2 marks] (d) Define a type or types (in C, Java, or ML) suitable for holding an abstract syntax tree resulting from your answer to part (b). [2 marks] (e) Give a brief and elementary explanation of the principles of how the grammar resulting from part (b) might be used to cre a syntax analyser taking a token stream as input (via calls to function lex()) and giving as output an abstract syntax tree corresponding to part (d). Mention both hand-written and automatically-generated syntax analysers. [8 marks] (f ) Summarise any issues related to left- or right-associative operators in the two techniques (in implementing the parser and in constructing the tool) you outlined in part (e). [3 marks]

(a) Wte a procedure and a call to it in block-structured pseudocode such that the execution of the procedure under pass-by-reference and under pass-by-value/result yields different outcomes. Justify your answer. [7 marks] (b) Explain the meaning of static (i.e. compile-time) and dynamic (i.e. run-time) type checking. Compare the advantages and disadvantages of these two approaches to type checking from the point of view of the language designer, the language implementer, and the programmer. [6 marks] (c) Explain how objects can be simulated in SML, giving an example. Does it follow that SML, together with its module system, is an object-oriented programming language? Why? [7 marks] 8 Databases (a) What is the difference between a key and a functional dependency? [3 marks] (b) The schema R(A, B, C, D, E) has the following functional dependencies. A, B C B, C D C, D E D, E A (i) What are all of the keys of R? [3 marks] (ii) Which functional dependencies violate Boyce-Codd Normal form (BCNF)? [3 marks] (iii) Which functional dependencies violate Third Normal form (3NF)? [3 marks] (iv) Find a lossless-join decomposition of R into BCNF relations. [8 marks]

(a) Define the translation of the call-by-name -calculus into continuation passing style. [9 marks] (b) How does the translation differ for the call-by-value -calculus? [2 marks] (c) Now consider extending the call-by-name -calculus with exceptions: M ::== try M catch M | raise | x. M | M M | x where it reduces in the following way: try raise catch M M try x.M1 catch M2 x.M1 raise M raise Show how to translate this language into pure -calculus using continuations. [Hint: Use two continuations: one for the exceptional case, and one for the normal case.] [9 marks]

Decrease weight (DW): Decrease the weight on an existing edge in the graph by the given amount. Delete vertex (DV): Delete the given vertex from the graph and all its incident edges. Delete edge (DE): Delete the given edge from the graph. Increase weight (IW): Increase the weight on an existing edge by the given amount. (extra credit) Path (PA): Given two vertex identifiers, compute and print the weight and path between them in the MST using Dijkstra's algorithm. If the vertices are not in the same tree, then print a message stating this. Here is a summary of the update directives: Print-graph Print the graph print-mst Print the MST(s) insert-vertex u Insert vertex u in the graph insert-edge u v w Insert edge (u,v) with weight w in the graph decrease-weight u v w Decrease the weight of edge (u,v) by w units delete-vertex u Delete vertex u from the graph delete-edge u v Delete edge (u,v) from the graph increase-weight u v w Increase the weight of edge (u,v) by w units (extra credit) path u v Print the weight and path from u to v in the MST

Define a resource in a digital communication system as anything whose use by one instance of communication prevents simultaneous use by another. Channel capacity is one example. (a) Give two more examples of resource in digital communication systems. [4 marks] (b) For the three resources, indicate how the amount of total resource can be increased. [6 marks] (c) How are allocations of each of these resources to instances of communication performed? [10 marks] 4 Concurrent Systems and Applications A system is to support abortable transactions that operate on a data structure held only in main memory. (a) Define and distinguish the properties of isolation and strict isolation. [2 marks] (b) Describe strict two-phase locking (S-2PL) and how it enforces strict isolation. [4 marks] (c) What impact would changing from S-2PL to ordinary 2PL have (i) during a transaction's execution, (ii) when a transaction attempts to commit and (iii) when a transaction aborts? [6 marks] (d) You discover that the system does not perform as well as intended using S-2PL (measured in terms of the mean number of transactions that commit each second). Suggest why this may be in the following situations and describe an enhancement or alternative mechanism for concurrency control for each: (i) The workload generates frequent contention for locks. The commit rate sometimes drops to (and then remains at) zero. [2 marks] (ii) Some transactions update several objects, then perform private computation for a long period of time before making one final update. [2 marks] (iii) Contention is extremely rare. [4 marks] 3 [TURN OVER CST.2002.6.4 SECTION B 5 Comparative Programming Languages (a) Briefly discuss the compromises that must be made when standardising a programming language. [8 marks] (b) Discuss the relative merits to (1) the application programmers and (2) compiler writer of the following ways of specifying a programming language. (i) A concise readable user manual for the language in English containing many useful programming examples. (ii) A very long and highly detailed description, in English, of every feature of the language. This manual contains no programming examples. (iii) A concise but rigorous description using a formal grammar to describe the language syntax and making extensive use of mathematical notations taken from set theory, -calculus, predicate calculus and logic to describe the semantics of the language. (iv) The source code for a clean and elegant machine-independent interpretive implementation of the language. [12 marks] 4 CST.2002.6.5 6 Compiler Construction Explain a possible implementation technology for Java classes and objects. Your answer should focus on storage layout for objects and on how class variables and methods are accessedit is not necessary to explain access qualifiers such as public and private. Illustrate your answer with the following program; in particular indicate its eventual output. class test { public int n; public static int s = 100; public void f(int x) { System.out.println("f1 " + (x+n)); } public static void main(String args[]) { test p = new test(); test2 q = new test2(); test r = q; p.n = 4; q.n = 5; q.m = 6; r.n = 7; p.f(p.s); q.f(p.s); r.f(q.s); } } class test2 extends test { public int n, m; public static int s = 200; public void f(int x)