What is an operating system kernel, and what runtime services does an executable binary program expect from a typical time-sharing kernel? How may transfer of control (program flow) between the loaded application and the resident kernel be achieved? Describe anules; (b) using an interpreter. Include examples of each, showing when one method is preferable to the other. Is there an absolute distinction between the two methods or is there a spectrum of approaches? 12 Outline the data protection principles set down in the Data Protection Act, and discuss the possible justifications for them.

Flow and error control are performed on a hop by hop basis [5 marks] (b) Switch C fails. Describe the events that follow to recover when (i) the network is a datagram network [5 marks] (ii) the network is connection oriented [5 marks] 2 CST.96.5.3 4 Graphics Consider the control of detail in a curve represented as a sequence of straight line segments. Describe Douglas and Peucker's algorithm for removing superfluous points. [10 marks] Describe how Overhauser interpolation can be used to introduce additional points. [10 marks] SECTION B 5 Programming in C and C++ For five of the following C or C++ features write very short fragment of code (perhaps 2 or 3 lines will suffice in most cases) that illustrates the syntax involved. In each case explain very briefly what your example achieves. (a) preprocessor macros and conditional compilation (b) casts that convert from one pointer type to another (c) C and C++ style comments (d) the declaration of a simple C++ class (e) overloading the operator '+' (f ) the C setjmp function (g) the switch statement, including a default label [4 marks eaer Construction Outline the key features of the design of the part of a compiler that will translate the abstract syntax tree representation of a program into a stack-based intermediate code. Concentrate on those features used in the translation of the following fragment: ... LET i = k LET j = k WHILE (i>0) AND (j<100) DO { i := i-1; j := j+2 } ... In particular, concentrate on the mechanism you would choose to deal with (a) the scopes of identifiers [6 marks] (b) the compilation of boolean expressions involving the operators NOT, AND and OR [6 marks] (c) the translation of the WHILE command [4 marks] (d) the translation of the two assignments.

An ordered integer binary search tree (or OIBS tree) is either empty or a tuple (T, N, U), where T and U are also OIBS trees and N is an integer. Every node in T has a value less than N, which in turn is less than the value of every node in U. (a) Give two Prolog terms which are suitable for representing an empty OIBS tree and a node in the OIBS tree respectively. [2 marks] (b) Define a Prolog procedure insert(Item, T, NT), where Item is an integer being inserted into OIBS tree T, producing an OIBS tree NT. If Item is already present in T, then NT equals T. [9 marks] (c) Define a Prolog procedure lookup(Item, T), where Item is to be looked for in OIBS tree T. A lookup goal will succeed if Item is found, or fail otherwise. [9 marks] 4 CST.96.5.5 8 Databases Describe the essentials of the ODMG-93 standard for Object Database Management. [7 marks] To what extent do these proposals conform to the ANSI/SPARC architecture for database management? [3 marks] Describe how binary relationships can be modelled directly within the ODMG-93 standard. [4 marks] In what way is it possible to create a representation for n-ary relationships that is similar to that of the relational model? [2 marks] Explain how these alternative approaches allow a navigational style of data manipulation as well as supporting an extension of SQL. [4 marks] 5 [TURN OVER CST.96.5.6 SECTION C 9 Foundations of Functional Programming Consider binary trees that are either empty (written Lf) or have the form Br x t1 t2 where t1 and t2 are themselves binary trees. Give an encoding of binary trees in the -calculus, including functions isLeaf, label , left and right satisfying isLeaf Lf true isLeaf(Br x t1 t2) false label(Br x t1 t2) x left (Br x t1 t2) t1 right (Br x t1 t2) t2 If you use encodings of other data structures, state the properties assumed. [6 marks] Consider the ML functions f and g defined to satisfy f([], ys) = ys f(x :: xs, ys) = f(xs, x :: ys) g([], ys) = ys g(x :: xs, ys) = x :: g(xs, ys) Using list induction, prove f(f(xs, []), []) = xs. [14 marks] [Hint: generalize this formula, making use of g. You may assume the equation g(xs, []) = xs.] 10 Logic and Proof For each of the following formul, construct a proof in the tableau calculus or show that no proof exists. ((A B) A) A [4 marks] z x y ((P(y) Q(z)) (P(x) Q(x))) [12 marks] tu(A B) tu(B A) [4 marks] Assume S4 modal logic for the last one. 6 CST.96.5.7 11 Complexity Theory (a) Show that the problem 3-SAT is at least as hard to solve as n-SAT. [5 marks] (b) Show that the task of finding a minimum cost closed circuit in a weighted directed graph (a Travelling Salesman Problem of the minimization variety) is at least as hard as the Hamiltonian Circuit Problem. [5 marks] (c) Show that the class NP-complete is contained in the class P-space. [5 marks] (d) Show that the class P-space is contained in the class EXP-time. [5 marks] In each case ensure that your answer makes it clear what the problems and classes involved are. Standard results do not need to be proved provided they are clearly stated.

Describe and justify Dijkstra's algorithm for finding the shortest path between two vertices in a directed graph with non-negative lengths associated with its edges. [8 marks] How can this algorithm be extended to consider graphs with some negative lengths? [6 marks] By considering the graph on {A, B, C} with A B having length 2, B A having length 1 and A C having length 1, or otherwise, show that the "shortest path" is not always well defined if there are negative lengths. When is it well defined? [6 marks] 6 Data Structures and Algorithms Describe and justify the Graham scan algorithm for finding the convex hull of a set of points in the plane. [8 marks] How does its cost depend on the number of points? [4 marks] Give a technique for heuristically eliminating a number of points before doing the scan. In what circumstances can the heuristic fail to help and what would you do about it? [8 marks] 7 Operating System Foundations What is meant by memory-mapped I/O? How might devices be protected from uncontrolled access? [3 marks]

Software Design

Software systems often incorporate structural representations of the application

domain in which they operate. For example, a vehicle control system should be

aware of the fact that the car has precisely four wheels. This kind of information

must be captured, encoded and tested at each stage of the software design process.

Using the number of wheels in a car as a simple example, describe relevant design

activities and products at each of the following phases of a software project:

(a) inception; [4 marks]

(b) elaboration; [4 marks]

(c) construction; [4 marks]

(d) transition; [4 marks]

(e) system operation. [4 marks]

8 Regular Languages and Finite Automata

(a) Explain what is a context-free grammar and the language it generates.

[4 marks]

(b) What does it mean for a context-free grammar to be regular? Given any

deterministic fifinite automaton M, describe a regular context-free grammar

that generates the language of strings accepted by M. [4 marks]

(c) Construct a non-deterministic fifinite automaton with -transitions whose

language of accepted strings is equal to the language over the alphabet {a, b, c}

generated by the context-free grammar with non-terminals q0 and q1, whose

start symbol is q0 and whose productions are q0 abq1, q1 , q1 q0 and

q1 abc. [4 marks]

(d) Is every language generated by a context-free grammar equal to the

set of strings accepted by some non-deterministic fifinite automaton with

-transitions? Justify your answer. (Any standard results about regular

languages you use should be carefully stated, but need not be proved.)

[8 marks]?

Answer rating: 100% (QA)

Certainly Lets go through the first four questions 1 What is an operating system kernel and what runtime services does an executable binary program expect from a typical timesharing kernel How may tra... View the full answer