In this question assume that p and q are atomic formulae. (a) Compare and contrast path formulae and state formulae in temporal logic. [4 marks] (b) Describe and contrast the meanings of F(G p) and AF(AG p). [4 marks] (c) Describe and contrast the meanings of G(F p) and AG(AF p). [4 marks] (d) Write down and justify a temporal logic formula that expresses the property that some state satisfying q is reachable from every state satisfying p. [4 marks] (e) Write down and justify a temporal logic formula that expresses the property that no path contains a consecutive sequence of 256 states satisfying p. [4 marks]

Let A be a non-empty set. Define the identity relation A on A. [1 mark] A pre-order on A is a relation R on A such that (i) a A,(a, a) R; (ii) (a, b) R,(b, c) R (a, notation, specify additional conditions: (iii), that must be satisfied in order that R be a partial order on A; (iv), that in addition to (iii) must be satisfied in order that R be a total order on A. [2 marks] Express conditions (i)-(iv) in terms of relations only (i.e. without reference to elements of A). [3 marks] Suppose R is a pre-order on A. Let S = {(a, b) | (a, b) R and (b, a) R}. Show that S is an equivalence relation on A. [4 marks] Let A S be the set of S-equivalence classes. Write [a] for {x A | (a, x) S}. Define relation 6 on A S as follows: [a] 6 [b] iff (a, b) R. Show that A S is partially ordered by 6. [4 marks] Let Z be the set of integers. Define the relation R on Z as follows: {(x, y) Z Z | q Z s.t. y = xq}. Show that R is a pre-order on Z but not a partial order. Describe the derived partially ordered set ( Z S , 6). [4 marks] What are the maximal and minimal elements in ( Z S , 6)? [2 marks]

Let I be a non-empty subset of the natural numbers N = {1, 2, 3, }. The set S is defined to be least subset of N such that I S, and if m, n S and m < n, then (n m) S. Define h to be the least member of S. This question guides you through to a proof that h coincides with the highest common factor of I, written hcf (I), and defined to be the natural number with the properties that hcf (I) divides n for every element n I, and if k is a natural number which divides n for every n I, then k divides hcf (I). [Throughout this question you may assume elementary facts about division.] (a) The set S may also be described as the least subset of N closed under certain rules. Describe the rules. Write down a principle of rule induction appropriate for the set S. [4 marks] (b) Show by rule induction that hcf (I) divides n for every n S. [3 marks] (c) Let n S. Establish that if p.h < n then (n p.h) S for all non-negative integers p. [5 marks] (d) Show that h divides n for every n S. [Hint: suppose otherwise and derive a contradiction.] [5 marks] (e) Explain very briefly why the results of parts (b) and (d) imply that h = hcf (I). [3 marks]

In what ways has exception handling been designed to impose minimal processing overhead in the MIPS R2000/R3000? [8 marks] Describe the model of operating system structure assumed by esigners. What hardware support is provided for this structure? [12 marks] 2 Computer Structures Write short notes on the following methods of improving the performance of a computer system: (a) cache memory [6 marks] (b) pipelining [6 marks] (c) Reduced Instruction Set Computer (RISC) [8 marks] Communication I Describe the properties of a physical channel which need to be considered when the channel is used for communications. [7 marks] Describe how the properties of a digital synchronous channel are related to the properties of the underlying physical channel. [7 marks] Describe three ways in which a protocol entity can provide higher layer channels from lower layer channels. [6 marks] 4 Graphics II Compare object-space and image-space visibility tests in synthesising an image for display. [12 marks] Describe one visibility test in detail. [8 marks] SECTION B 5 Programming in C Two identical packs of ordinary playing cards (52 different cards in a pack) are shuffled and placed face downwards on a table. Two players then play a game of Snap. Each player is allocated one pack and at each turn in the game one card in each pack is turned up and the two upturned cards are compared. If the cards are the same (i.e. match in every respect) a snap-turn is declared. A game ends when all 52 pairs have been compared. Write a C program which will simulate the game for the purposes of determining the probability of there being at least one snap-turn in a game. [20 marks] Note: you may assume the existence of a random number generator but must state its properties. 2 CST.93.6.3 6 Programming Language Compilation Write notes on each of the following topics: (a) the implementation of labels and jumps in a recursive, block structured programming language [7 marks] (b) the implementation of arrays with non-constant bounds [7 marks] (c) problems in the specification and implementation of Algol own variables [6 marks] 7 Concurrent Systems Monitors are often provided in concurrent programming languages to support the interaction of processes by means of shared data. Discuss the monitor mechanism and its implementation. [10 marks] How could the monitor mechanism be adapted to allow for many shared data objects of the same type? [2 marks] What advantages, if any, could be obtained from using an active object instead of a monitor; that is, a monitor-like structure with one or more internally bound processes? [8 marks] 8 Databases Describe the ANSI-SPARC architecture for managing data, explaining how it enables data independence to be achieved. [6 marks] Outline the CODASYL/DBTG proposals for network database management, showing how they relate to the ANSI-SPARC architecture. [8 marks] In what ways do the DBTG proposals compromise data independence? [3 marks] What provision is made for data security in them? [3 marks] 3 [TURN OVER CST.93.6.4 SECTION C 9 Foundations of Functional Programming Describe David Turner's algorithm for translating -terms to combinators, using S, K, I, B and C. Demonstrate the algorithm by translating x y f.f x y. [4 marks] Prove that T x.R T y.R[y/x] holds for every combinatory term R such that y is not free in R. [6 marks] Describe the graph reduction of S I I ( S I I ). [4 marks] Describe the graph reduction of S mult I (fst ( Y ( pair 3))), taking all the constants shown as primitive combinators. [6 marks] 10 Computation Theory Explain what is meant by the following: 'F is a recursively enumerable set each of whose elements is a total recursive function f : N N.' [3 marks] In each of the following cases state with reasons whether the set is recursively enumerable: (a) the set A of all total recursive functions a : N N such that a(n + 1) > a(n) for all n N [7 marks] (b) the set D of all total recursive functions d : N N such that d(n + 1) 6 d(n) for all n N [10 marks] 11 Complexity Theory Explain the relationship between integer and polynomial multiplication. [2 marks] Show how the latter can be reduced to an interpolation problem which can be solved by matrix multiplication. [4 marks] Starting from this idea, outline an efficient algorithm for forming the product of two n-bit unsigned integers. [12 marks] What is the cost of the algorithm that you have described? [2 marks] 4 CST.93.6.5 12 Formal Languages and Automata For each of the following languages over the alphabet {a, b}, say whether or not it is regular. Justify your answers stating clearly any results that you use. (a) The set of all strings which are not palindromes (i.e. which are not equal to their own reverse) [4 marks] (b) The union of countably many regular languages L [4 marks] (c) The set of all strings in which the number of occurrences of the letter a and the number of occurrences of the letter b are both divisible by 3 [4 marks] (d) The set of all strings which are of the form ww for some string w [4 marks] (e) The set of all strings such that in each initial substring the number of occurrences of the letter a and the number of occurrences of the letter b differ by no more than 2 [4 marks]

What does it mean for a function to be an injection, a surjection, and a bijection? [4 marks] (b) For sets A and B, define without proof a bijection from P(AB) to [A P(B)] and its inverse. [4 marks] (c) For sets A, B and C, define without proof a bijection from [(A B) C] to [A (B C)] and its inverse. [4 marks] (d) Let X be a set. Prove there is no injection f : P(X) X. [Hint: Consider the set W = {f(Z) | Z X f(Z) / Z}.]

You may use standard results provided that you mention them clearly. (a) (i) State a sufficient condition on a pair of positive integers a and b so that the following holds: x, y Z. x y (mod a) x y (mod b) x y (mod ab) [2 marks] (ii) Recall that, for a positive integer m, we let Zm = {n N | 0 n < m} and that, for an integer k, we write [k]m for the unique element of Zm such that k [k]m (mod m). Let a and b be positive integers and let k and l be integers such that k a+l b = 1. Consider the functions f : Zab ZaZb and g : ZaZb Zab given by f(n) = [n]a , [n]b , g(x, y) = [k a (y x) + x]ab Prove either that g f = idZab or that f g = idZaZb . [8 marks] (b) Let T denote the reflexive-transitive closure of a relation T on a set A. For relations R and S on a set A, prove that if idA (R S) then (R S) = (R S) . Note: You may alternatively consider T to be defined as either [ nN T n , where T 0 = idA and T (n+1) = T T n or as \ { R A A | (T idA) R R R R } or as inductively given by the rules (x, y) (x, y) T (x, x) (x A) (x, y) (y, z) (x, z) (x, y, z

Define a suitable G0 or explain why G already satisfies the criterion. [6 marks] Write a 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 [7 marks] 8 Prolog for Artificial Intelligence A trinary tree is constructed from 3-ary compme that integer components are restricted to the values 0 and 1. Write a Prolog program to return a list of all the 0's and a list of all the 1's in a given tree. For example, the goal enum(n(n(0, 1, 0), 1, 0), X, Y) should instantiate X to [0, 0, 0] and Y to [1, 1]. The program should use difference lists. [10 marks] A terminal node of the trinary tree is said to be of odd parity if the number of its 1 components is an odd number. For example, n(1, 1, 1) is of odd parity, and n(1, 0, 1) is not of odd parity. Write a Prolog program to count the number of terminal nodes in a tree that have odd parity. For example, the goal odd(n(n(0, 1, 0), 1, 0), X) should instantiate X to 1.

The upper bound of a set S A is an element u A (but not necessarily in S) such that s S . s 6 u. The least upper bound of S is an upper bound of S that is less than every other upper bound of S. The greatest lower bound is defined similarly. A lattice is a partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound. (b) Prove that (N, |), the natural numbers under the divisibility order, form a lattice. [4 marks] (c) Given a set X, prove that (P(X), ), the power set of X under set inclusion, forms a lattice. [4 marks] (d) Does every subset of (N, |) have a least upper bound and a greatest lower bound? Justify your answer. What about (N0, |) and (P(X), )? [4 marks] (e) If (A, 6A) and (B, 6B) are lattices, show that AB is a lattice under the product order.

In each part you are given the result of an SQL query together with a possibly incorrect conclusion drawn from this result. In each case your task is to argue for or against the conclusion. You must clearly justify your reasoning. If the SQL query can be corrected, then do so. (a) The following query returns 1422. Conclusion: Our database contains information on 1422 directors. select count(*) from has_position where position = 'director'; [6 marks] (b) The following query returns these records:

nm0498278 Stan Lee writer 15 Conclusion: Stan Lee did not produce any of the movies in our database. select person_id, name, position, count(*) as total from has_position as hp join people as p on p.person_id = hp.person_id where position <> 'actor' and name = 'Stan Lee' group by person_id, name, position [6 marks] [continued . . . ]

Write Java program to read a file content line by line.

1 b) Write java program to read a file line by line and store it into a variable.

(c) The following query attempts to return records (role, year, total) where Jennifer Lawrence plays the same role during the year a total number of times in different movies. The query returns these records: ROLE YEAR TOTAL ---------------- ---- ----- Tiffany 2012 1 Mystique 2011 1 Raven 2011 1 Aurora Lane 2016 1 Katniss Everdeen 2012 2 Ree 2010 1 Rosalyn Rosenfeld 2013 1 Katniss Everdeen 2013 2 Conclusion: Jennifer Lawrence played Katniss Everdeen in two movies in 2012. select r1.role, m1.year, count(*) as total from plays_role as r1 join plays_role as r2 on r2.person_id = r1.person_id join movies as m1 on m1.movie_id = r1.movie_id join movies as m2 on m2.movie_id = r2.movie_id join people as p on p.person_id = r1.person_id where p.name = 'Jennifer Lawrence' and r1.role = r2.role group by r1.role, m1.year;

You are provided with a 2D triangle mesh defined by a set of vertices V [k] = (xk, yk, ak) for k = 1, . . . , N, and a triangle index table T of dimension M3, where M is the number of triangles. xk and yk are the coordinates of vertex k and ak is its scalar attribute. An example of such a triangle mesh is shown below. (a) Write down the triangle index table of the mesh shown in the figure above. Ensure that all triangles are forward-facing. [4 marks] (b) Write pseudocode for a function a = lookup a(x, y, V, T), which returns the value of the linearly interpolated attribute at the point (x, y) when the point lies on the mesh and 1 otherwise. Use square brackets to index vertex (V [i]) and triangle (T[i, j]) tables. The pseudocode should include the formulas needed to compute the interpolated attribute value and to check whether the point is inside the triangles. [10 marks] (c) Suppose that now vertices also include a depth, so that V [k] = (xk, yk, zk, ak), and triangles overlap and occlude one another. How do you need to modify the pseudocode to return the attribute of the visible triangle that has the lowest z-value at a given point? Due to memory limitations, you cannot use the Z-buffer algorithm. [6 marks] 5 CST0+CST1.2021.3.6 4 Introduction to Graphics Your task is to create a simple visualization of SARS-CoV-2 using only two primitives: a sphere of radius 1, and a cylinder of a height 2, its base of radius 1, and the main axis aligned with OZ, both centred at the origin. An example of such a visualization is shown in Fig. 1 below. (Fig. 1) (Fig. 2) x y z (r, , ) r (a) Draw a scene graph for the SARS-CoV-2 model, shown in Fig. 1, in which the main shape is a sphere and each spike consists of a cylinder and a sphere. Use the hierarchy of the primitives (sphere cylinder sphere) so that the entire object can be animated by transforming the main shape. [4 marks] (b) Provide transformation matrices for each node of the graph. You do not need to provide the results of the matrix multiplication. Assume that you have a list of N spherical coordinates (k, k), for k = 1, . . . , N, which indicate the positions of the spikes. Use the coordinates as shown in Fig. 2. The main body has a radius of 1, the cylinder of the spike has a length of 0.1, a radius of 0.025 and the sphere of the spike has a radius of 0.05 with the centre at the base of the cylinder. [10 marks] (c) How can you randomly generate the spherical coordinates (k,k) of the spikes so that they are (a) evenly distributed over the sphere and (b) not clustered together (two or more spikes are not too close to each other)? Write pseudocode for generating (k,k).

Nowadays, timepieces (such as clocks, wristwatches, etc.) have a variety of functions. They not only tell the time and date but they can speak to you, remind you when it's time to do something, and provide a light in the dark, among other things. Mostly, the interface for these devices, however, shows the time in one of two basic ways: as a digital number such as 23:40 or through an analog display with two or three hands - one to represent the hour, one for the minutes, and one for the seconds. In this question, we ask you to design a new timepiece for your own use. This could be in the form of a wristwatch, a mantelpiece clock, an electronic clock, or any other kind of timepiece you fancy. (a) Think about the interactive product you are designing: describe what you want it to do for you. Write a list of functional and non-functional requirements. [4 marks] (b) Sketch out an initial low-fidelity prototype for the timepiece and develop at least two distinct alternatives that both meet your set of requirements listed above. [8 marks] (c) Nielsen's heuristics used for Heuristic Evaluation are: (1) visibility of system status, (2) match between system and real world, (3) user control and freedom, (4) consistency and standards, (5) error prevention, (6) recognition rather than recall, (7) flexibility and efficiency of use, (8) aesthetic and minimalist design, (9) help users recognize and recover from errors, and (10) help and documentation. Evaluate the two low-fidelity prototypes using Heuristic Evaluation.

A weather app, whose main screen is shown in the figure above, has been created specifically for event organizers as primary stakeholders. (a) Evaluate the provided low-fidelity prototype using Cognitive Walkthrough and the visualised screens (if you need to, you may come up with your own assumptions regarding the primary stakeholders), for the following tasks: (i) (starting from the main screen) View details of the event called Field Day (ii) (starting from the main screen) Add a new event [continued . . . ] 8 CST0+CST1.2021.3.9 (iii) (starting from the main screen) View detailed weather forecast for Field Day (iv) (starting from the main screen) Change the units of measurement for the temperature information provided (v) (starting from the main screen) Modify the volume setting to 150 [14 marks] (b) Using the outcome of the CW you have conducted above, provide a list of suggestions for re-designing this weather app. [3 marks] (c) Considering that user-centred design is iterative, how would you go about gathering another round of data from the target user group using your findings from the CW? Explain which data gathering techniques you would use and why. [3 marks] 9 CST0+CST1.2021.3.10 SECTION D 7 Machine Learning and Real-world Data Consider the directed graph shown in the figure below, which expresses cooperation amongst individuals (A, B, . . . , H) in a fishing village. The meaning of an edge from X to Y is that X has asked Y for advice or help during fishing at least once. A E C D F G H B (a) Consider the betweenness centrality of each individual in this network, which is listed in the following table. A B C D E F G H 6 12 2 9 0 12 8 0 (i) Give a definition of the betweenness centrality of a node. [1 mark] (ii) Explain intuitively why B and F have the highest betweenness centralities and why E and H have betweenness centralities of 0. [2 marks] (b) We now look at what happens if the network is converted into an undirected network. (i) What is the diameter of this network and why? Your question should include a definition of diameter.

A Java programmer is attempting to write a class BigNo which is intended to handle integers of arbitrary size. An integer is represented as a list of single digits arranged so that the least significant digit is at the head of the list. In outline, class BigNo is declared thus: class BigNo { private int dig; private BigNo rest; public BigNo(int n) { this.dig = n%10; if (n/10 == 0) this.rest = null; else this.rest = new BigNo(n/10); } private BigNo add(int c) . public BigNo add(BigNo that) . private BigNo add(BigNo that, int c) { if (this.rest == null) return that.add(this.dig+c); if (that.rest == null) return this.add(that.dig+c); int d = this.dig + that.dig + c; return new BigNo(d%10, this.rest.add(that.rest,d/10)); } The final return statement refers to a constructor which is not shown. Why are two constructors needed? Provide the missing constructor. Does it have to be public? [4 marks] Why are there three add() methods? Explain why one is public and two are private. Provide bodies for the two add() methods for which only heading lines are shown. [6 marks] Provide a suitable toString() method. [4 marks] Suppose jack and jill are BigNo representations of the integers 46 and 57 respectively. Describe carefully the effect of the call jack.add(jill) [6 marks] 2 CST.2000.10.3 3 Further Java Write brief notes on the facilities for lightweight concurrency in Java. You should cover the following topics, using code fragments to illustrate your answer: (a) creating a thread (b) mutual exclusion (c) signalling (d) asynchronous interruption (e) managing priority [4 marks each] 4 Compiler Construction With reference to a strictly-typed block-structured programming language, write brief notes on the following topics: (a) the allocation and recovery of records stored in a heap (b) the implementation of variables of union type (c) the allocation of arrays with non-manifest bounds (d) the implementation of labels and GOTO commands [5 marks each] 3 [TURN OVER CST.2000.10.4 5 Introduction to Security Consider the following two separation-of-duty policies: (a) A transaction needs approval from two people, one in group A and one in group B. (b) A transaction needs approval from two distinct users of the system. Which of these is harder to implement using the standard Unix access control mechanisms, and why? [10 marks] Sketch an implementation of the easier policy using Unix mechanisms. [5 marks] Describe at least two alternative mechanisms that might be used to implement the other policy. [5 marks] 6 Data Structures and Algorithms Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted. [6 marks] Describe another algorithm that will find the same element, but with a guaranteed worst case time of O(n). [7 marks] Give a rough estimate of the number of comparisons each of your methods would perform when k = 50, operating on a set of 100 random 32-bit integers. [7 marks] 7 Computer Design Gordon Moore's law originally applied to memory size (in bits), but also applies to processor speed (in MIPS). However, main memory access latency does not follow Moore's law. (a) What is Moore's law? [4 marks] (b) Why doesn't main memory latency decrease in proportion to processor cycle time? [6 marks] (c) What mechanisms are used to hide poor main memory access times and why do these mechanisms work?

For each of the following areas, write brief comments on the way in which Java and its libraries have been designed to try to prevent programmers from making undetected errors and to ensure that code runs on all possible brands and models of computer, yielding the same results in each case. (a) Programmers who get mildly confused about syntax or who make typing errors. [4 marks] (b) Groups of programmers working on libraries that will form part of some large project. [4 marks] (c) Numbers, characters, trig functions and so on. [4 marks] (d) Opening files, reading or writing and then closing them. [4 marks] (e) Other features of Java not falling centrally within any of the above categories. [4 marks] 10 Programming in Java For each of the following ML definitions write, explain and comment on the closest reasonable Java equivalent code-fragment that you can construct. (a) fun fact n r = if n = 0 then r else fact (n-1) (n*r); [4 marks] (b) datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree * 'a tree; [4 marks] (c) val v = [1,2,3,7]; val v2 = map (fn n=>n*n:int) v; [4 marks] (d) exception Disaster of int; raise Disaster 99; [4 marks] (e) fun recursiveLength nil = 0 | recursiveLength (a :: b) = 1 + recursiveLength b; [4 marks] 6 CST.2001.1.7 SECTION E 11 Operating Systems (a) Describe how the CPU is allocated to processes if static priority scheduling is used. Be sure to consider the various possibilities available in the case of a tie. [4 marks] (b) "All scheduling algorithms are essentially priority scheduling algorithms." Discuss this statement with reference to the first-come first-served (FCFS), shortest job first (SJF), shortest remaining time first (SRTF) and round-robin (RR) scheduling algorithms. [4 marks] (c) What is the major problem with static priority scheduling and how may it be addressed? [4 marks] (d) Why do many CPU scheduling algorithms try to favour I/O intensive jobs? [2 marks] (e) Describe how this is achieved in the (i) UNIX and (ii) Windows NT operating systems. [3 marks in each case]

kindly answer all the questions