Comparative Programming Languages.Make sense of what certified influence all of the three terms is endeavoring to show and get a handle on what all of the going with pictures suggests, inside the setting of this recipe: I, Ia, I, Ii , ka, kd, ks,Li , N, Ri , V, n [10 marks] 3 [TURN OVER CST.2001.6.4 SECTION B 5 (a) Briefly make sense of the idea of coroutines as utilized in BCPL and frame the impact of the library capabilities createco(f, size), deleteco(ctpr), callco(cptr, val) and cowait(val). [10 marks] (b) Outline how you would plan a coroutine to converge, in expanding request, two limitless surges of expanding numbers provided by two other coroutines. [5 marks] (c) Briefly frame how you would execute a similar to blending system in an item situated language, for example, Java, that doesn't give a coroutine instrument.[5 marks].Depict an O(n) calculation to find every one of the firmly associated parts of a given coordinated diagram and make sense of why it is right. You might find it helpful to utilize the idea of the progenitor (v) of a vertex v which is the vertex, u, with most elevated completing time for which there exists a (potentially zero length) way from v to u. [10 marks] 2 Computer Design (a)What does it regularly store and for what reason is it frequently an element of 1000 more modest than an information reserve? [5 marks] 2 1.6.3 3 Digital Communication I (a) Define the terms circuit and parcel with regards to correspondence frameworks. [5 marks] (b) What kind of assurance truly does circuit exchanging give? [5 marks] (c) What benefits does parcel exchanging give over circuit exchanging? [5 marks] (d) Which of recurrence division multiplexing, time division multiplexing and code division multiplexing loan themselves to circuit exchanging? Which to parcel exchanging? Make sense of why or why not for each situation. [5 marks] 4 Computer Graphics and Image Processing (a) Describe the z-support polygon examine transformation calculation. [10 marks] (b) In beam following, whenever we have figured out where a beam strikes an article, the enlightenment at the convergence point can be determined utilizing the equation: I = Iaka + X I Iikd(Li N) +X I Iiks(Ri V) n Explain what genuine impact every one of the three terms is attempting to display and make sense of what every one of the accompanying images implies, inside the setting of this recipe: I, Ia, I, Ii , ka, kd, ks,Li , N, Ri , V, n [10 marks] 3 [TURN OVER CST.2001.6.4 SECTION B 5 Comparative Programming Languages (a) Briefly make sense of the idea of coroutines as utilized in BCPL and frame the impact of the library capabilities createco(f, size), deleteco(ctpr), callco(cptr, val) and cowait(val). [10 marks] (b) Outline how you would plan a coroutine to converge, in expanding request, two limitless surges of expanding numbers provided by two other coroutines. [5 marks] (c) Briefly frame how you would execute a similar to blending system in an item situated language, for example, Java, that doesn't give a coroutine instrument.[5 marks] 6 Compiler Construction (a) Describe one possible structure (e.g. ELF) of an object file. Illustrate your answer by considering the form of object file which might result from the following C program. int a = 1, b = -1; extern int g(int); extern int c; int f() { return g(a-b) + c; } It is not necessary to consider the exact instruction sequence, just issues concerning its interaction with the object file format. [10 marks] (b) Describe how a linker takes a sequence of such programs and produces an executable file. [4 marks] (c) Compare and contrast static and dynamic linking in a system using your object file format. [6 marks] 4 CST.2001.6.5 7 Prolog for Artificial Intelligence A weighted binary tree can be defined using compound terms in the following way. A node of the tree is represented by the term n(V, L, R), where V stands for the value of the node, and L and R stand for the left and right branches, respectively. A terminal node has the R and L components instantiated to the null list. Given an input tree T, write a Prolog program that constructs a tree of the same shape as T, but in which the value of each node has been set to the value of the maximum value node in T. [Note: Maximum marks are available only for programs that perform this task in one recursive descent of the input tree, and which use no more than four clauses.] [20 marks] 8 Databases The environmental agency is setting up an SQL database to monitor long-term trends in the climate. Data are collected from observatories of a number of different kinds. Flood risk is of particular concern. Each water authority measures river levels and rates of flow hourly at major points, and records reservoir levels daily. In addition, the agency maintains weather stations both inland and at sea. These record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind. Values of new precipitation, temperature, pressure, and wind speed and direction are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur. Maximum and minimum temperature and pressure, the total number of hours of sunshine and the total precipitation are maximum (and minimum as appropriate) day value for each statistic, together with the monthly totals of sunshine and precipitation. The warehouse also keeps detailed information relating to periods of extreme weather from the relevant observatories, with one or more keywords describing the nature of the incident (flood, blizzard, hurricane etc.) and an optional comment. Write notes to assist in the design of the schema for the relational data warehouse, including any diagrams that you find helpful. Explain how your design will enable meteorologists to find relevant past records, noting any assumptions that you make about the nature of the data. [You should not go into unnecessary detail about the structure of the primary database. You may assume that expert meteorologists will select the data for the warehouse.] [20 marks] SECTION C 9 Semantics of Programming Languages Write short notes on four of the following five topics. (a) The relationship between three forms of operational semantics of the Language of Commands (LC) given by an evaluation relation hP, si hV, s0 i a transition relation hP, si hP 0 , s0 i a transition relation between the configurations hc, r, si of the SMC-machine (b) The notion of semantic equivalence of LC phrases and its congruence property. (c) Call-by-name and call-by-value rules for evaluating function applications in the Language of Functions and Procedures (LFP) and the relationship between the evaluation relations for LFP based upon each of them. (d) The notion of bisimilarity of two configurations in a labelled transition system. (e) The rules defining the possible labelled transitions of parallel composition (P1|P2) and restriction ( c . P) in the Language of Communicating Processes (LCP). [5 marks each] 7 10 Foundations of Functional Programming The following are some concepts that have flourished in the context of functional programming but which have (so far) been less heavily used in main-stream languages even when they have been available: (a) polymorphic types (b) type reconstruction (c) higher-order functions (d) lazy evaluation (e)

Optimising Compilers (a) A dataflow analyser is required which can report on local variables having write-write dataflow anomalies. A write-write anomaly is present in a program if there is a path in the flowgraph containing two writes to a given variable and with no intervening read to that variable. For example y=a; if (p) x=1; if (q) x=2; if (y==b) y=1; else y=2; has an anomaly for x but not for y. Given node n in the flowgraph, let R(n) be the set of variables v for which a node n 0 exists with n 0 writing to v and having a path from n 0 to n which does not contain a read from v. (i) Give dataflow equations for R(n) and thence construct an algorithm which reports variables having such anomalies. Pay attention to the initialisation of any iteration which you employ. [8 marks] (ii) Discuss briefly to what extent your algorithm could be extended to deal with global variables or with address-taken local variables. [4 marks] (b) Let us say that an undirected graph (N, E) is k-cyclic if N = {n1, . . . , nk} and E = {(n1, n2),(n2, n3), . . .(nk1, nk),(nk, n1)}. (i) Give a function body, or flowgraph, for which the register inference graph for its local variables forms a 4-cyclic graph. [4 marks] (ii) Give a formula c(k) which gives the number of colours (or registers) needed for a minimal colouring of a k-cyclic continuations For each case give a brief explanation of the facility referred to, suggest a circumstance in which it might be useful and comment on how immediately relevant to non-functional languages it seems. [4 marks per part] 8 CST.2001.6.9 11 Logic and Proof (a) In the context of clause-based proof methods, define the notion of pure literal and describe what should be done if the set of clauses contains pure literals. [3 marks] (b) Use the Davis-Putnam method to discover whether the following set of clauses is satisfiable. If they are satisfiable, show a satisfying interpretation. {P, R} {P, R} {P, Q} {Q, R} {P, Q, R} [6 marks] (c) The three-fingered inhabitants of the planet Triterra build base-3 computers. A Triterran named Randal Tryant has found a way of verifying base-3 combinational logic. His Ordered Ternary Decision Diagrams (OTDDs) are the same as a technology used on planet Earth except that all variables and expressions range over the values 0, 1 and 2 instead of just 0 and 1. (i) Describe how a full ternary decision tree can be reduced to an OTDD without regard for efficiency. [2 marks] (ii) Sketch an efficient algorithm to convert a ternary expression directly to an OTDD without constructing the full decision tree. For a typical ternary connective use modulo-3 multiplication, written as . [6 marks] (iii) Demonstrate your algorithm by applying it to the ternary expression ((i i) j) 2. [3 marks] 1.6.10 12 Complexity Theory (a) Show that any language that can be accepted by a nondeterministic machine in time f(n) can also be decided by a deterministic machine in space O(f(n)). [4 marks] (b) Show that any language that can be accepted by a nondeterministic machine in space f(n) can also be decided by a deterministic machine in time O(c (f(n)+log n) ), for some constant c. [6 marks] (c) Explain what the above results tell us about the inclusion relationships among the complexity classes: NL, co-NL, P, NP, PSPACE and NPSPACE3 2005.8.4 5 Advanced Systems Topics A computer system provides a compare-and-swap (CAS) operation which is used in the following manner: seen = CAS (address, old, new) It loads the contents of address, compares that value against old and if it matches stores the value new at the same address. All of this is performed atomically and the value read from the address is returned as seen. (a) Making use of CAS, write pseudo-code for a simple multi-reader spin-lock. Your design should permit concurrent readers to enter their critical sections in parallel but ensure that writers gain exclusive access. Be sure to provide pseudo-code for each of the four operations supported by the lock, and describe the layout of the lock's data fields in memory. [10 marks] (b) Why might this simple spin-lock perform poorly on a large multi-processor system? How might you improve the lock to achieve better performance on such a system? [4 marks] A programmer analyses a multi-threaded application and discovers that the majority of the execution time is spent contending for access to a shared data structure. (c) Describe three methods for reducing lock contention amongst threads accessing a highly-concurrent data structure. In each case briefly describe a situation or workload to which the method is particularly well suited. [6 marks] 4 CST.2005.8.5 6 Security A mobile telephone company has 5 million prepay customers who buy scratchcards to pay for air time. Each card has a code of 9 decimal digits, and at any time there are about 20 million cards active (issued to the supply chain and not yet used). (a) Discuss the relative advantages and disadvantages of implementing the code system with a database of random numbers versus an encrypted counter. [4 marks] (b) If you were using an encrypted-counter system, how would you go about selecting, adapting or designing a suitable cipher? [4 marks] (c) Some of the customers have got clever. As they are allowed two invalid code attempts, they try two random codes before entering a correct one. The telephone company is now getting 2000 complaints a month from people who bought a scratchcard and found, when they tried to use it, that someone else had already guessed the number. How would you modify the system to reduce the level of complaints? [8 marks] (d) You are now approached by a telephone company in China which wants to use your system to manage 100 million prepay customers. What further modifications would you consider? [4 marks] 5

What does it mean to say that two confifigurations of a labelled transition system

are bisimilar? [3 marks]

Describe a labelled transition system for a language of communicating processes

with input prefifixing (c(x). P), output prefifixing (

ch Ei . P), an inactive process (0),

choice (P + P0 ), parallel composition (P|P0 ) and channel restriction ( c . P). You

may assume there is a relation E n which defifines when an integer expression E

evaluates to an integer n. [7 marks]

For each of the following pairs of processes, say whether or not they are bisimilar.

Justify your answer in each case.

(a)

ch 1i .((

ch 2i . 0) + (

ch 3i . 0)) and (

ch 1i . ch 2i . 0) + (

ch 1i . ch 3i . 0) [4 marks]

(b) P and c .((c(x). 0)|(

ch 1i . P)), where c does not occur in P

[6 marks]

10 Foundations of Functional Programming

Give as simple a set of rules as you can for transforming lambda calculus to a form

where there are no bound variables mentioned, but where there are many instances

of the three standard combinator constants S, K and I. [6 marks]

Describe tree-rewrites suitable for reducing expressions written in terms of

combinators. [6 marks]

Explain how you might deal with the issue of keeping track of the values of bound

variables if you were to interpret lambda calculus directly. [8 marks]

5

[TURN OVERCST.2000.6.6

11 Logic and Proof

For each of the given pairs of terms, give a most general unififier or indicate why

none exists. (Here x, y, z are variables while a, b are constant symbols.)

h(x, y, x) and

h(y, z, u)

h(x, y, z) and

h(f(y), z, x)

h(x, y, b) and

h(a, x, y)

h(x, y, z) and

h(g(y, y), g(z, z), g(u, u))

[4 marks]

A standard unifification algorithm takes a pair of terms t1 and t2 and returns a

substitution such that t1 = t2. Show how this algorithm can be used to fifind

the unififier of several (n > 2) terms t1, t2, . . . , tn: a substitution such that

t1 = t2 = = tn. Indicate how the unififier is constructed from the unififiers

of n 1 pairs of terms. (Assume that all required unififiers exist and ignore the

question of whether the unififiers are most general.) [6 marks]

Prove using resolution the formula

(a) State what is meant by a directed graph and a strongly connected component.

Illustrate your description by giving an example of such a graph with 8 vertices

and 12 edges that has three strongly connected components. [5 marks]

(b) Describe, in detail, an algorithm to perform a depth-fifirst search over such a

graph. Your algorithm should attach the discovery and fifinishing times to each

vertex and leave a representation of the depth-fifirst spanning tree embedded

within the graph. [5 marks]

(c) Describe an O(n) algorithm to discover all the strongly connected components

of a given directed graph and explain why it is correct. You may fifind it useful

to use the concept of the forefather (v) of a vertex v which is the vertex, u,

with highest fifinishing time for which there exists a (possibly zero length) path

from v to u. [10 marks]

2 Computer Design

(a) What is a data cache and what properties of data access does it exploit?

[5 marks]

(b) What is a direct mapped cache and under what conditions will it exhibit poor

performance? [5 marks]

(c) Under what circumstances might a word of data in main memory be

simultaneously held in two separate fifirst-level cache lines? [5 marks]

(d) A translation look aside buffffer is a specialised cache. What does it typically

store and why is it often a factor of 1000 smaller than a data cache? [5 marks]

2CST.2001.6.3

3 Digital Communication I

(a) Defifine the terms circuit and packet in the context of communication systems.

[5 marks]

(b) What sort of guarantee does circuit switching provide? [5 marks]

(c) What advantages does packet switching provide over circuit switching?

[5 marks]

(d) Which of frequency division multiplexing, time division multiplexing and code

division multiplexing lend themselves to circuit switching? Which to packet

switching? Explain why or why not in each case. [5 marks]

4 Computer Graphics and Image Processing

(a) Describe the z-buffffer polygon scan conversion algorithm. [10 marks]

(b) In ray tracing, once we have determined where a ray strikes an object, the

illumination at the intersection point can be calculated using the formula:

I = Iaka +X

i

Iikd(Li N) +X

i

Iiks(Ri V)n

Explain what real effffect each of the three terms is trying to model and explain

what each of the following symbols means, within the context of this formula:

I, Ia, i, Ii , ka, kd, ks,Li, N, Ri, V, n

[10 marks]

isappointments of some imitation directors, a majority get together plan is utilized. Reproduction administrators are thought to be non-vindictive and fall flat stop. To refresh an oversaw information thing, the activities given by the overseeing system include: lock(item) update(item, esteem, timestamp) read(item, timestamp) unlock(item) (a) Suppose the information thing is an at first void rundown of values and the update activity attaches a worth. Represent the majority gathering plan for five imitations, showing various update and read activities. [8 marks] (b) How is a complete request of updates accomplished by majority gathering in the presence of simultaneous update demands by clients to the open gathering? Examine how any issues that could emerge can be settled. [4 marks] (c) When can unlock(item) be executed securely by the starting reproduction administrator? Depict any extra convention that is required. [5 marks] (d) Suppose that the cycle bunch is overseeing non-covering parcels of a conveyed data set rather than copies. Could majority at any point gathering have any impact in making the connected updates expected for circulated exchanges? Legitimize your response.

(a) Name three kinds of programming weakness; give an illustration of each and a brief portrayal of how each could be taken advantage of. (b) Alice needs to go after Bob's PC through the Internet, by sending IP parcels to it, straightforwardly from her own PC. She doesn't believe that Bob should find out the IP address of her PC. (I) Is this simpler to accomplish for Alice with TCP-or UDP-based application conventions? Make sense of why. [3 marks] (ii) For the more troublesome convention, make sense of one method that Alice could attempt to beat this hindrance and one countermeasure that Bob would be able carry out in his PC. [3 marks] (iii) Name three capacities that Alice's Internet specialist organization would be able execute to make it more challenging for Alice to accomplish her objective? [3 marks] (c) In what way are TCP/UDP port numbers under 1024 unique?(a) Distributed limit approaches can be disconnected into network joined limit (NAS) and limit district associations (SANs). Figure out with the aide of a chart the basic differentiations between the two philosophies. [4 marks] (b) The association record structure (NFS) is generally speaking used in area. (I) Why is NFS not commonly remembered to be suitable for wide locale associations? [2 marks] (ii) Briefly analyze how one could change NFS to all the more probable assistance wide district networks. [2 marks] (c) Distributed shared virtual memory can be used inside a handling pack to clearly grant multi-hung ventures to coincidentally find various machines. Sketch the arrangement of a DSVM structure. Understand what happens both at the point when a memory read and when a memory create occurs. Comment on the expected execution and generosity of your structure. [6 marks] (d) EROS is a limit based working system. (I) What is a limit? [1 mark] (ii) Explain with the aide of a diagram how EROS uses standard paging hardware to duplicate limit gear. [5 marks] 6 CST.2006.9.7 6 Computer Vision (a) Extraction of visual features from pictures habitually incorporates convolution with channels that are themselves worked from mixes of differential executives. One model is the Laplacian 2 2 x2 + 2 y2 of a Gaussian G(x, y) having scale limit , making the channel 2G(x, y) for convolution with the picture I(x, y). Figure out thoroughly all of the going with three manager groupings, where infers two-layered convolution. (I) 2 (x, y) I(x, y)] [2 marks]