Write an interface, ECS, defining opaque object types EventCount and Sequencer. EventCount should have methods advance, read and await, with appropriate signatures, and Sequencer should have a ticket method. [8 marks] Sketch an implementation of the ECS module giving concrete revelations of the types and providing appropriate default methods. [12 marks] 3 [TURN OVER CST.94.10.4 4 Formal Languages and Automata What is meant by the language accepted by a finite deterministic automaton M = (Q, ?, ?, i, F)? [2 marks] Show that it is possible to associate with M a regular expression r over ? denoting the same language as that accepted by M. [12 marks] Illustrate your answer by constructing such a regular expression r when M is the finite deterministic automaton with Q = {q1, q2, q3} ? = {0, 1} i = q1 F = {q3} and with transition function ? defined by the table q1 q2 q3 0 q2 q3 q3 1 q3 q2 q2 [6 marks] 5 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. [15 marks] 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 An operating system supports multi-threaded processes. Within a given user-level address-space two threads cooperate by means of a shared, circular, N-slot buffer. Semaphores are supported by the language system. Outline pgrams 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.

A zoologist wants to record the echo-location sounds emitted by a bat. The species of bat to be recorded emits only sounds in the frequency range 40 kHz to 80 kHz and the microphone used includes an analog filter with that passband. (a) Explain for each of the following sampling techniques how it can be used to convert a continuous ultrasonic microphone signal x(t) into a discrete-time sequence {xn} and state for each technique the lowest sampling frequency fs that enables the exact reconstruction of x(t) from {xn}: (i) Passband sampling [3 marks] (ii) IQ downconversion [5 marks] (b) Using a 32-bit floating-point data type, how many bytes per second are required to store each of the two resulting discrete sequences from part (a)? [2 marks] (c) Compare your answers to part (b) with the memory required for storing x(t) sampled at the Nyquist rate of 160 kHz and explain the difference in terms of redundancy in the acquired spectrum. [2 marks] (d) If the sampling techniques from part (a) are applied to a test signal x(t) = cos(2?f t) with f = 45 kHz, what does the discrete-time Fourier transform of the resulting discrete sequence {xn} look like (over the normalized frequency range ?? < ?? ? ?) for each technique?

Examine the following statements and indicate which are true and which are false. In most cases a simple one-word answer "true" or "false" will suffice, but, if you feel the need to make assumptions about circumstances or otherwise elaborate a little, please keep your notes as short as possible. (a) All methods in an abstract superclass must be declared abstract. (b) A class declared final cannot be subclassed. Every method of a final class is implicitly final. (c) A redefinition of a superclass method in a subclass need not have the same signature as the superclass method. Such a redefinition is not method overriding but is simply an example of method overloading. (d) A constructor is a special method with the same name as the class that is used to initialise the members of a class object. Constructors are called when objects of their classes are instantiated. (e) A method declared static cannot access non-static class members. A static method has no this reference because static class variables and static methods exist independent of any objects of a class. (f ) An array subscript may be an integer or an integer expression. If a program uses an expression as a subscript, then the expression is evaluated to determine the particular element of the array. (g) To pass one row of a double-subscripted array to a method that receives a single-subscripted array, simply pass the name of the array followed by the row subscript. (h) Overloaded methods can have different return values, and must have different parameter lists. Two methods differing only by return type will result in a compilation error. (i) The applet's paint method is called after the init method completes execution and the start method method has started executing to draw on the applet. It is also called automatically every time the applet needs to be repainted. (j) Any block of Java code may contain variable declarations. [1 mark each] 3 [TURN OVER CST.2003.1.4 4 Operating Systems For each of the following, indicate whether the statement is true or false, and explain why this is the case (no marks will be awarded for an answer with no explanation). (a) Preemptive schedulers require hardware support. (b) The Unix shell supports redirection to the buffer cache. (c) A context switch can be implemented by a flip-flop stored in the translation lookaside buffer (TLB). (d) Non-blocking I/O is possible even when using a block device. (e) Shortest job first (SJF) is an optimal scheduling algorithm. [2 marks each] SECTION B 5 Foundations of Computer Science (a) Describe how lazy lists can be implemented using ML. [2 marks] (b) Code a function to concatenate two lazy lists, by analogy to the 'append' function for ordinary ML lists. Describe what happens if your function is applied to a pair of infinite lists. [3 marks]

13. (a) (b) Generate the output for the following java applet code. import java.applet. Applet; import java.awt.Color; import java.awt.Graphics; public class MyApplet extends Applet { } @Override public void paint (Graphics g) { g.setColor (Color.red); } g. drawstring ("This is rectangle shape fill with red color!", 0, 10); g.drawRect (0, 20, 130, 50); g.fillRect (0, 20, 130, 50); Write a Java Applet program that will read 2 integers from user input. Then, calculate the total number and display whether the remainder of this number will be 0 if divide by 5. (4 marks) (11 marks)