Graphics Describe a quad-tree encoding method for greyscale images. [6 marks] Given the following greyscale image, draw a diagram showing how it would be encoded using your method from the previous part. 33 39 43 72 34 54 64 81 42 54 71 83 60 64 77 89 An image processing package allows the user to design 3 3 convolution filters. Design 3 3 filters to perform the following tasks: (a) blurring (b) edge detection of vertical edges [2 marks] Choose one of the two filters (a) or (b) from the previous part. Explain how it works, using the following image as an example (you may round off any calculated values to the nearest integer). 100 100 100 0 0 0 100 100 100 0 0 0 100 100 100 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 [6 marks] 12 Digital Electronics Design a synchronous sequential circuit with one input and one output which produces an output X = 1 whenever any of the following input sequences occur: 1100, 1010 or 1001. The circuit resets to its initial state after a 1 output has been generated. (a) Draw a state diagram and provide a transition table. (b) Choose an assignment and show the control factors for JK flip flops.

Operating System Functions Describe the use of an inverted page table for the implementation of virtual addressing and a paging virtual memory system. Give details of the operation of the page table and its associated data structures. What can be done to overcome the thrashing problem encountered with a direct mapped inverted page table? [5 marks] 4 CST.94.10.5 6 Operating Systems two threads cooperate by means of a shared, circular, N-slot buffer. Semaphores are supported by the language system. Outline programs that may be executed by the thread which writes data into the buffer and the thread which reads data from it. [8 marks] How would you ensure that several threads could write to, and read from, the buffer? [4 marks] Explain how the semaphore implementation in the language system uses the thread implementation in the operating system. [8 marks] 5 [TURN OVER CST.94.10.6 7 Data Structures and Algorithms For the following, n is a positive integer and G is a graph of N nodes (vertices) and E arcs (edges) each with a given weight (or cost). For seven of the following indicate, with a short justification, whether the statement is true or false. (a) All functions f of the form f(n) = Ank (with A and k being

constants) are in the class O(2n). (b) All sorting methods for an array of n elements take time O(n 5 ). (c) It is possible to sort an array of n elements using binary comparisons in ?(n log n) time. (d) It is possible to sort an array of n elements using binary comparisons using O(1) (i.e. constant independent of n) additional space. (e) Radix sorting can sort any set of integers in linear time. (f ) All straight lines from the inside of a polygon to the outside intersect the points on the edges forming its boundary an odd number of times. (g) It is always cheaper to find the shortest distance between two given nodes u, v of G than to find all N shortest distances from u to every other node. (h) It is possible to find the shortest paths between all N2 pairs of nodes of G in O(N3 ) time. (i) If G is connected then the minimal spanning subtree of G contains the N ? 1 edges whose weights are smallest. (j) Given n points (xi , yi), 1 6 i 6 n in a plane, then the four points (xa, ya), (xb, yb), (xc, yc), (xd, yd) such that xa is minimal of the xi , xb is maximal of the xi , yc is minimal of the yi , yd is maximal of the yi form a quadrilateral Q which can be used to speed up a convex hull algorithm by preprocessing to remove points which lie inside Q. Marks will be awarded for overall succinctness, attention to detail and absence of random guesses lacking justification.

Find expressions for (a) the absolute error in representing x1 + x2 (b) the relative error in representing x1.x2 (where "." denotes multiplication) Assume that the numbers 1 and 2 are represented exactly. Find an expression for the absolute error in calculating 2x + 1. [2 marks] In an iterative calculation the number y is an improved value of x, derived from the assignments p := x/2 + 1 q := x ? 2 y := p + 1/q If ?x is the absolute error in representing x, find an expression for the absolute error ?y in representing y. What is the approximate relative error ?y in representing y when x = 2.01?

editor to logic e and fix x and ogram to rea on the compile and in Checks ed tests te a grade. ur results, ecord your DebugBoat java DebugElevent java 1 public class Debugloubout extends Debugboat ( 4 public Debagoubat () ( 6 7 W " 10 11 12 34 15 17 10.) 20 super("rou"); setpower(); setPassengers(); } public void setPassengers() ( } super passengers 21 } public void setpower() { super power "ears"; Debugowboat java + > Terminal Debugowboat.Save:1: error: Debugt owboat is not abstract and does no t override abstract method set Powe public class DebugRewbeat extends DebugBoat 1 error Exception in thread "main" java.le ng. NoclassDefFoundError: Debugowb oot at DebugElevent.main(Debug Elevens-Jave:7) Caused by: Java. Lang. ClasallotFound Exception: Debugowboat at java.net. URLClassLoader findClass(URLClassLoader.java: 382 at jave.lang.classLoader.1 oadClass(ClassLoader.java:424) at sun.nic.LaunchersAppCt assLoader.loadClass(Launcher.java: at java.lang.ClassLoader. L oodClass(ClassLoader.java:357) ... 1 more 349)