A suite of Modula-3 procedures is being developed to handle arbitrarily large nonnegative integers. A test program for handling such numbers includes the following TYPE declaration: TYPE Digit = [0..9]; RefBigNo = REF BigNo; BigNo = RECORD dig:Digit:=0; rest: RefBigNo:= NIL10 digits stored in reverse order. The chosen data structure is a record which consists of the last digit of the number and a reference to the remaining digits. Write a procedure Add which will add two of these large numbers and a procedure Print which will convert one such number to type TEXT. The following signatures might be appropriate for the two procedures: PROCEDURE Add(a, b: RefBigNo; carry:=0): RefBigNo = and PROCEDURE Print(N:RefBigNo; first:= TRUE): TEXT = 4 CST.93.1.5 10 Distinguish between TRY-EXCEPT and TRY-FINALLY and provide program fragments to illustrate uses of these Modula-3 clauses.

 

A Modula-3 program includes the following declarations: TYPE ArrCard = ARRAY OF CARDINAL; RefArrCard = REF ArrCard; EXCEPTION TooMuch; PROCEDURE Read(VAR a: RefArrCard) : CARDINAL = . . END Read; VAR buffer:= NEW(RefArrCard, 10); count:= Read(buffer); The data for the program are arranged in lines with strictly one CARDINAL value on each line so that a loop incorporating Scan.Int(Rd.GetLine(Stdio.stdin)) will input successive values. As indicated, the variable buffer initially refers to an array of 10 CARDINALs and this is handed to the procedure Read whose task is to read values from the data and assign them to successive elements of the array. Should there be more values in the data than can be accommodated in the array, the procedure Read will raise the Too Much exception. The exception handler will create new array which is larger by 20%, transfer values from the full array to the new one, and then continue reading from the data. This enlargement process will be repeated as necessary until all the data have been read. It may be assumed that there is unlimited memory. When the reading is complete, buffer will refer to the most recently created array and the procedure read will return, for assignment to the variable count, the number of values that have been read from the data. Complete the procedure Read.

11 What is a hierarchical file structure? Discuss the good and bad points about such a file structure. Give an example of the use of a hierarchical file structure in a UNIX system by presenting a diagram, and use your example to describe the following terms: (a) home directory; (b) current directory; (c) full pathname; (d) relative pathname. Imagine that you have created a UNIX file structure in which your leaf nodes are very deep. How can you arrange to get to specific leaf nodes quickly?

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 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] (c) Code a function to combine two lazy lists, interleaving the elements of each. [3 marks] (d) Code the lazy list whose elements are all ordinary lists of zeroes and ones, namely [], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], . . . . [6 marks] (e) A palindrome is a list that equals its own reverse. Code the lazy list whose elements are all palindromes of 0s and 1s, namely [], [0], [1], [0, 0], [0, 0, 0], [0, 1, 0], [1, 1], [1, 0, 1], [1, 1, 1], [0, 0, 0, 0], . . . . You may take the reversal function rev as given. [6 marks] 4 CST.2003.1.5 6 Foundations of Computer Science (a) Explain in detail how a binary search tree represents a dictionary. If reference types are not used, what is the average-case cost of an update operation? [8 marks] (b) A mutable binary tree is either a leaf or a branch node containing a label and references to two other mutable binary trees. Present the ML datatype declaration for mutable binary trees. [2 marks] (c) Describe how to use this datatype to implement (mutable) binary search trees. Give ML code for the lookup and update operations. The update operation must never copy existing tree nodes. (a) Define the terms injective, surjective and bijective, and state the Schroder- Bernstein theorem concerning the existence of a bijection between two sets. [4 marks] (b) What is a countable set? [2 marks] (c) Prove the following assertions: (i) If C is a countable set and f : A C is an injection, then A is countable. [2 marks] (ii) If A and B are countable sets, then A B is countable. [2 marks] (iii) Z and Q, the sets of integer and rational numbers, are both countable. [4 marks] (iv) P(N), the set of all subsets of the natural numbers, is not countable. [2 marks] (v) If U is an uncountable set and f : U V is an injection, then V is not countable.

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 a 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) You are to design a component of a distributed system which takes action on the arrival of an alarm event from another component. Discuss the design issues, relating to the characteristics of distributed systems, of the component and its communication. [4 marks] (b) You are to design a service that takes in streams of messages from distributed sources and notifies its clients when certain specified patterns of messages occur. Discuss the design issues associated with supporting the following operators for constructing message patterns, where A and B represent messages: (i) A OR B; (ii) A AND B (unordered pairs); (iii) A BEFORE B (ordered pairs). [16 marks] 5 Advanced Systems Topics (a) Considerable recent operating system research has focused on extensibility. (i) What is the motivation for this work? [1 mark] (ii) Describe with the aid of examples three different techniques for providing extensibility. In each case comment on the granularity of extensibility provided, and discuss the issues of performance and safety. [5 marks each] (b) Some researchers claim that programming language virtual machines such as the JVM should be extensible. (i) Why might this be desirable? [1 mark] (ii) How could this be safely achieved? Comment on how your solution might differ from those used in the case of operating system extensibility.

(a) The Digital Signature Standard is computed using the following equations: r = (g k mod p) (mod q) s = (h(M) xr)/k (mod q) Describe what the various symbols represent. [4 marks] (b) Write down the equation(s) used to verify a signature. [4 marks] (c) The standard specifies that r must lie strictly between 0 and q. What might go wrong if an implementation does not check this? [4 marks] (d) A designer decides to on code size by omitting the hash function computation, that is, replacing h(M) by M. What are the consequences of this optimisation?

(a) Explain in one sentence what is meant by the "phase order problem". [2 marks] For the rest of the question, it is recommended that you restrict attention to a single basic block containing only unary and binary arithmetic instructions, e.g. add#4 dst,src or mul dst,src1,src2 and with no variable written to after being read (SSA form). Consider all such instructions to execute in one cycle. (b) Describe how a directed acyclic graph expressing instruction dependencies suitable for instruction scheduling can be obtained from such a basic block. [4 marks] (c) Briefly describe how a (register interference) graph can be obtained from such a basic block. Also state a requirement for colouring this graph with registers. [4 marks] (d) Consider the two programs (where the first four lines are the same): add t1,a,b add t1,a,b add#2 t2,c add#2 t2,c add#3 t3,c add#3 t3,c mul t4,t2,t3 mul t4,t2,t3 sub z,t1,t4 sub t5,t1,t4 xor t6,t5,a xor z,t6,b In each case consider scheduling the add t1,a,b to appear as early as possible or as late as possible. Determine the number of registers required to colour the program in all four resulting cases. (Assume that only z, allocated to r1, is live on exit and that a,b,c are allocated registers r1,r2,r3.) [10 marks] [Remark: you might note that doing add t1,a,b in the left-hand program decreases the number of live registers by one, while it increases the number by one on the right-hand program.]21

Question: Early programming languages had relatively poor facilities for type checking, data abstraction, data hiding and encapsulation. Explain the meaning of these terms and discuss their importance. [6 marks] Outline the key features that a language must have to be called object-oriented and briefly discuss to what extent C++, Java and Smalltalk have them. [7 marks] Briefly discuss some of the reasons why C++ programs typically run faster than equivalent programs written in Java or Smalltalk. [7 marks] 6 Compiler Construction It is desired to obtain an unambiguous context-free grammar G0 which generates the same strings as the following grammar G with start symbol S. S -> E E -> ( E ) | [ E ] | E * E | a | b | c ( E ) -> ( + E ) [ E ] -> [ - E ] Define a suitable G0 or explain why G already satisfies the criterion. [6 marks] Write context-free (Type 2) grammar which describes floating-point numbers of the form []dd [.d ][e[]dd ] where d stands for decimal digit and d stands for zero or more decimal digits. [ ] means that the enclosed item is optionally present in the floating-point number. [7 marks] Sketch a recursive descent parser for the following grammar H with start symbol S. You should assume the existence of a routine lex() which sets variable token to one of '1', '2', '(', ')', '-' or eof. P -> 1 | 2 | (E) E -> P | E - P S -> E eof

Windows implements static inheritance for the access-control lists of NTFS files and folders. (i) What does static inheritance mean here and how does it differ from dynamic inheritance? [4 marks] (ii) Five flag bits (ci,oi,np,io,i) in each NTFS access-control entry (ACE) manage how it is inherited. Briefly describe the purpose of each bit. [5 marks] (iii) User mike gives his folder project the following access-control list: project AllowAccess mike: full-access (oi,ci) AllowAccess alice: read-execute (ci,np) AllowAccess bob: read-only (oi) It contains one folder and two text files, none of which have any noninherited access-control entries: project\doc.txt project\src project\src\main.c For each of these three objects, list all inherited access-control entries, showing in parentheses the inheritance-control flag bits that are set (using the same notation as above). [5 marks] (b) Describe the purpose and four typical functions of a root kit.

Given a sequence of points (Vi) n i=0 on a plane, consider the problem of interpolating a smooth curve through all of the points in order by constructing a sequence of polynomial parametric functions, one for each interval [Vi , Vi+1] n1 i=0 . (a) What is meant by Ck continuity at the junction between two curve segments? [2 marks] (b) Explain how the degree of the polynomial function for a curve segment constrains the continuity at its two ends. What continuity can be achieved at each end of a cubic segment? [4 marks] (c) Derive a cubic parametric function for the interval [Vi , Vi+1] where 0 < i < n1 Momentarily clarify the job of the attest articulation and why this program will trigger a state disappointment when executed. Supply two altered adaptations of the program that change the trade work definition and, assuming fundamental, its calls, to stay away from this state disappointment. One rendition should be in C, and the other should utilize C++ language highlights. [4 marks] (c) Describe the location space format (featuring four areas of memory) of a ordinary incorporated x86 C program, and how every one of these areas are utilized by C builds. [8 marks] (d) Briefly clarify what indistinct conduct is in the C norm. Under what circumstance(s) would calling the accompanying C capacity result in unclear conduct? int32_t divide(int32_t a, int32_t b) { return a/b; }