(i) Write down the linear program relaxation for the vertex cover problem and solve the linear program. [6 marks] (ii) Based on the solution of the linear program in (b)(i), derive an integer solution using the rounding approach described in the lecture. [2 marks] (c) Consider the following randomised algorithm for the unweighted vertex cover problem: Initialize S to be the empty set For all edges e=(u,v) do If neither u nor v belongs to S Randomly choose u or v with probability 1/2 and add the vertex to S End If End For Return S Derive an upper bound, as tight as possible, on the approximation ratio of the algorithm. Hint: Try to find an invariant that bounds from below the size of the intersection of the current solution S = S(i) with the optimum solution, where S(i) denotes the set S after the i-th iteration of the FOR loop.(a) State the fundamental theorem of linear programming. [3 marks] (b) Consider the following linear program: Minimize 3x1 2x2 subject to: 3x1 + x2 5 2x1 10 + 4x2 x1, x2 0

Let E, F be events over a finite alphabet S. Define the events E + F, EF and E*. [3 marks] Show that: (a) E* = 1 + EE* (b) E(F E)* = (EF)*E [4 marks] State Kleene's Theorem on the structure of events accepted by some Deterministic Finite Automaton (DFA). [1 mark] Consider the following DFA: a a b a b a b b Here is the initial state, and the two accepting states. Show that the event accepted is b*a(a*b b*a)*{1 + a*b}. [12 marks] [Hint. If M = A B C D is a partitioning of the transition matrix of a DFA so that A and D are square, then M* = (A + BD*C)* A*B(D + CA*B)* D*C(A + BD*C)* (D + CA*B)* with the same partitioning. Partition the states in the order {, }, {, }. You need calculate only the upper right component of M*.

A sequential machine with two input wires and a single output has a behaviour specified in the following transition table: Next state Output Initial state Input 00 01 10 11 Input 00 01 10 11 a c b a a 0 0 0 1 b d b b e 0 1 1 1 c e d e a Demonstrate that this behaviour could be exhibited by a machine with fewer states. [12 marks] Draw the state diagram for the reduced machine. [8 marks] 2 Computer Structures What are the parameters which characterise the operation of a cache? [8 marks] Describe three methods of mapping memory blocks to cache blocks. [7 marks] Would the cache be a help or a hindrance if the CPU were used to handle continuously changing data such as video? [5 marks] 1 Digital Communication I Define the term circuit as used in "circuit switching". [4 marks] Sketch the design of the in-band switching function of a circuit switch which switches 4 2 Mbps trunks each supporting 32 64 Kbps channels. [8 marks] Describe how you would augment this design to allow the set up and clearing of connections. You should invent your own simple protocol for this purpose. [8 marks] 4 Graphics Discuss sampling artifacts and their effect on image quality on a raster display. [10 marks] What can be done to reduce or eliminate them? [10 marks] 5 Programming in C Write program in C which, given two integer inputs J and K, will output the combinations of J things partitioned into K groups. For example, if J = 5 and K = 3, the output would be: (5,0,0) (4,1,0) (3,2,0) (3,1,1) (2,2,1) [20 marks] 2 CST.94.12.3 6 Programming Language Compilation Suggest how you would represent Lambda-expressions in a form suitable for a simple Lambda-evaluator in which the environment is represented as a linked list of name- value pairs. [5 marks] Outline the design of the evaluator, paying particular attention to the treatment of bound variables, abstractions and applications. [5 marks] Augment your evaluator to cope with sufficient expression operators, including a built-in version of the Y operator so that when the evaluator is given the abstract syntax tree for Y (f.n. n=0 -> 1, n*f(n-1)) 5 it will yield 120. [10 marks] 7 Artificial Intelligence I Compare and contrast heuristic search and exhaustive search. [6 marks] Which compromises are accepted by the heuristic approach? [8 marks] Illustrate your answer with examples of heuristics. [6 marks] 8 Databases What are the primitives in terms of which a network data model is presented? [4 marks] Explain how such a data model is specified in the CODASYL Schema Data Definition Language. [6 marks] How does an application programmer in COBOL gain access to a CODASYL database? [3 marks] Describe the COBOL programmer's model of the database, illustrating your answer with suitable data manipulation commands. [7 marks] 3 [TURN OVER CST.94.12.4 9 Specification and Verification of Hardware Briefly discuss each of the following topics: (a) the representation of schematic diagrams in predicate calculus [5 marks] (b) the use of primitive recursion in hardware specification [5 marks] (c) modelling combinational and sequential circuits [5 marks] (d) temporal abstraction [5 marks] 10 Complexity What is a Hamiltonian Circuit? What is the Boolean Satisfiability Problem "3-SAT"? [5 marks] words each, sketch (a) how an efficient solution to 3-SAT would allow you to construct an efficient solution to the Hamiltonian Circuit problem [6 marks] (b) how an efficient solution to the Hamiltonian Circuit problem would allow you to solve 3-SAT [6 marks] (c) what is meant by "efficient" in this context [3 marks] You are not expected to include technical details of any constructions you need in deriving one algorithm from another: a clear statement of what can be done will suffice. 4 CST.94.12.5 11 Computation Theory The Halting Problem for register machines is unsolvable. State, without proof, a precise form of this result. [3 marks] Let the computation by program p on data d be represented by the natural number k that codes the pair (p, d). By considering the set H(k) of the HALTing computations represented by codes k 0 6 k, show that there is an increasing total function h(k) which grows too fast to be computable. [6 marks] Given h : N N with the above property let f(k) = h(k) + k and g(x) = sup{k : f(k) 6 x}. Then f : N N is strictly increasing, and g : N N satisfies g(f(k)) = k, g(x) < k for all x < f(k). Show that g grows too slowly to be computable in the following sense. . . given G : N N such that (a) {G(n) : n N} is unbounded (b) G(n) 6 g(n) for all n N then G(n) is not computable. [11 marks] 12 Software Engineering Discuss the reasons why substantial software systems often take longer to implement than planned and do not perform as well as expected. [10 marks] If you were in charge of a large team implementing such a system, how would you ensure that the product was both reliable and finished on time? [10 marks]

It is proposed that persistent, strongly consistent data replicas should be maintained by a widely distributed, open, unstructured process group. (i) Discuss the potential advantages of replication, bearing in mind that strong consistency is required. [2 marks] (ii) Describe algorithms for maintaining strong consistency while retaining at least some of the advantages of replication. Show how your algorithms are robust with respect to concurrency and failure. [8 marks] (b) A distributed conference application provides a shared whiteboard. Each member of the conference has a replica of the whiteboard that is managed by a member of a closed process group. Discuss one approach by which the processes can achieve mutually exclusive access to the whiteboard, prior to propagation of the update to the whole group. [8 marks] (c) Contrast the styles of replica management required for (a) and (b) above. [2 marks]

You have been asked to design an event composition and aggregation service to operate above publish/subscribe middleware to be deployed in various environmental monitoring scenarios. Your service is to advertise and publish high-level events of interest to applications. It may subscribe to any published events in the domain of deployment. Your service may itself be distributed. Identify a list of technical design issues you would raise with your client prior to specifying the service in detail. [12 marks] (b) By means of a diagram illustrate the use of vector clocks to implement the delivery in causal order of multicast messages among members of a closed, unstructured process group. Include an explanation of the message delivery algorithm. [8 marks]

i need help for this project (if You are expected to investigate a case study (either drawn from your work site, or alternatively being secured through formal access) to analysis only two business processes from commencement to completion, with a focus on the more important or interesting tasks within the process. Be careful to select business processes of appropriate size. If you choose the processes which are too simple, you will find it hard to demonstrate your mastery of MIS concepts. Conversely, if you choose processes that are too complex, you may find it difficult to complete the assignment within the specified time. Consider discussing your choice with me before you begin work. The central premise of this project is that you are able to develop familiarity with describing the functional activities of the organization of your chosen case study, investigating the functional problems, and suggesting remedial actions in view of the IS and its capabilities to improve outdated business process. should be focus may be based on the following:

Providing background information of your chosen organization/system. Identify the kind of systems (software). Describing TWO business processes; including all related business functions -Please draw on wide sets of process mapping tools, i.e. a cross-functional diagram or alternatively flowchart. Therein, for rigors and coherence purposes, you will need to draw on relevant literature and modelling techniques to the issues raised in your chosen case study. Describing the technology and its main IT infrastructure components in your chosen case. Outlining organizational benefit from the extant IS application in the chosen process. Articulating the management level involved in using the system. Discussing the business and IS strategies influenced by this kind of technology. Commenting on any issues\ dysfunctional areas that arose during research of the case study. it should be for example like SAP or oracle for example in any organization for example in HR what is the process with the follow diagram

In C++, this program is about stacks and queues. With this assignment, we will keep a stack of the books you are using for your courses. For each book, you want to keep the author, title, publisher, and the last page you left off. After you finish with your stack, the next ADT will be a queue as a separate class in a separate .h file. The queue will be a list of all of the assignments you are working on, in the order in which they are due. This is a First in, First out abstraction. So, it helps us keep ordered as to what our assignments are. For each assignment, you will want to keep the class, the name of the assignment, the due date, and a stack of books that you will want to reference for this assignment. Remember to separate the files as the question asks: one .h one .cpp for Stack, one .h one.cpp for Queue and 1 main.cpp file Programming - Data Structures: The stack (our "list of books") should be implemented using a linear linked list of arrays, where each element in a book. The array must be dynamically allocated and each array must be of the same size. I recommend that the arrays be relatively small (e.g., 5) so that you can properly test the code. Stack ADT functions should include push, pop, peek, and display. The queue should be implemented using a circular linked list, where the rear pointer points to the last assignment in the queue, and rear->next points to the first assignment. You must implement enqueue, dequeue, peek and display. Remember the idea of your client program is to test out your ADT functionality so that a real application can be developed off site by another team of Software Engineers based on the ADT public functions. You want to make sure that your stack and queue ADTs perform well! This means a menu interface is required for your main set of functions

Implementing Using Classes: Begin by implementing the Stack ADT: Task 1. Construct a Stack object (constructor) Task 2. Push a Book at the top Task 3. Display all Books on the stack Task 4. Pop the most recent Book from the Top Task 5. Peek the Book at the Top of stack Task 6. Release all dynamic memory (destructor)

Then, continue by implementing the Queue: Task 7. Construct a Queue object (constructor) Task 8. Enqueue an Assignment to the Rear Task 9. Display the Queue Task 10. Dequeue an Assignment from Front Task 11. Peek from the Queue (to allow the client to obtain info about the next Assignment due without modifying the queue) Task 12. Release all dynamic memory (destructor)

A minority gate is its complement. (a) Give the boolean equation for a minority gate as a sum of products. [2 marks] (b) Sketch the circuit diagram for a minority gate using implementation as a single stage of CMOS logic. [3 marks] (d) Calculate the number o a resistance twice that of a similarly sized n-channel, use logical effort to compare the performance of the two implementations. [10 marks] 3 Digital Communication II (a) The Transmission Control Protocol (TCP) employs a transmit window and cumulative acknowledgement and timeout system, as well as sequence numbering of packets, to achieve reliable delivery of data. (i) Outline the procedure for round-trip time estimation and the calculation of the retransmission timer. [8 marks] (ii) Explain the function of buffering at the sender and receiver. (iii) How do fast retransmit and fast recovery improve performance after packet loss? (b) In a wireless network, delay to access the channel due to scheduling of the media access control protocol, and random packet loss due to interference, may be non-negligible. (i) Explain how this can interfere with the round-trip time estimation process above. [3 marks] (ii) Explain how this can interfere with the congestion control scheme that TCP employs. [3 marks] 3 (TURN OVER) CST.2006.8.4 4 Distributed Systems (a) Describe, with examples, the function of a naming service for a largescale distributed system. Include definitions for "name space" and "naming domain". [6 marks] (b) Discuss consistency versus availability for naming data in large-scale systems. [4 marks] (c) How can any distributed naming service be engineered so that invocations on behalf of users can be resolved efficiently in the presence of failures and heavy load? [4 marks] (d) Contrast the assumptions under which DNS was designed originally for the Internet, with the properties of dynamically formed groups of mobile hosts using wireless communication (MANETS). How might DNS-like services be provided for MANETS? [6 marks] 5 Advanced Systems Topics Modern peer-to-peer (P2P) systems are typically described as structured or unstructured. (a) Compare and contrast these two approaches. Include a discussion of the general topology, membership management and query mechanisms. Use examples to support your answer. [6 marks] (b) Which approach is more resilient to churn? Justify your answer. [2 marks] (c) One early criticism of P2P systems was that they did not consider network latencies. Describe how one can add proximity awareness to: (i) unstructured P2P systems; [1 mark] (ii) structured P2P systems. [3 marks] (d) Swarming P2P systems like BitTorrent are designed for efficient (and incentive compatible) download of large files. However, it is typically not possible to use the file until it has downloaded in its entirety. Sketch the design of a swarming P2P system which supports streaming video - that is, allows playback of video to overlap the ongoing download of the remainder of the stream. Comment on how efficient (in terms of network resources) your system would be in comparison with a system like BitTorrent. [8 marks] 4 CST.2006.8.5 6 Computer Vision (a) Explain the method of Active Contours. What are they used for, and how do they work? What underlying trade-off governs the solutions they generate? How is that trade-off controlled? What mathematical methods are deployed in the computational implementation of Active Contours? [10 marks] (b) When trying to detect and estimate visual motion in a scene, why is it useful to relate spatial derivatives to temporal derivatives of the image data? Briefly describe how one motion model works by these principles. [5 marks] (c) Provide a 3 3 discrete filter kernel array that approximates the Laplacian operator. Explain what the Laplacian might be used for, and what is the significance of the sum of all of the taps in the filter. [3 marks] (d) When visual sequences are encoded into an .mpeg video stream, typically about what percentage of the compression achieved is intra-frame (compression within individual still frames), and what percentage is inter-frame? Name a key feature that is extracted and estimated for purposes of prediction and, therefore, compression. [2 marks] 7 Security The Needham-Schroeder protocol is defined as 1. A S : A, B, NA 2. S A : {NA, B, KAB, {KAB, A}KBS }KAS 3. A B : {KAB, A}KBS 4. B A : {NB}KAB 5. A B : {NB 1}KAB (a) Explain the symbolism, and the purpose of the messages. [5 marks] (b) Explain the "bug" in the protocol. [5 marks] (c) Is the bug actually a vulnerability if one can assume (as the Needham- Schroeder paper does) that all principals execute the protocol faithfully? If not, why is it important? [5 marks] (d) Describe how one modern protocol derived from Needham-Schroeder deals with the issue. [5 marks] 5 (TURN OVER) CST.2006.8.6 8 Optimising Compilers (a) Summarise the idea of a basic block and explain why it is useful in intermediate representations for optimising compilers. [3 marks] (b) Construct the flowgraph (in which every node is a basic block consisting of one or more 3-address instructions) for the C function: int f(int x, int y) { int r = x + 1; if (y == 0) { r = r * r; } else { y = y - 1; r = r * y; } return r + 1; } [4 marks] (c) Define static single assignment (SSA) form, and explain the changes you would have to make to your flowgraph from part (b) in order for it to be in SSA form. [3 marks] (d) Consider a flowgraph in which every node contains a single 3-address instruction. Each node whose instruction assigns some value to a variable is considered a "definition" of that variable; we are interested in discovering, for each node n in the flowgraph, which definitions reach n. A definition m is considered to reach n if the variable to which m assigns a value may still have that value at entry to n. (i) Define the notion of a definition reaching a node in the flowgraph in terms of possible execution flows of control. [2 marks] (ii) By analogy with live variable or available expression analysis, or otherwise, design dataflow equations for computing RD(n), the set of definitions which can reach a node n. [4 marks] (iii) Sketch an algorithm to compute RD(n), briefly commenting on any initialisation required. [4 marks] 6 CST.2006.8.7 9 Artificial Intelligence II Consider the following Bayesian network: A B C D The associated probability distributions for the binary random variables A, B, C and D are Pr(a) = 0.1, Pr(a) = 0.9, Pr(b) = 0.8, Pr(b) = 0.2, and: A B Pr(c|A, B) B C Pr(d|B, C) > > 0.5 > > 0.2 > 0.6 > 0.9 > 0.8 > 0.8 0.7 0.1 (a) Explain why the representation of the joint distribution of A, B, C and D using the Bayesian network is preferable to a direct tabular representation. [2 marks] (b) Use the variable elimination algorithm to compute the probability distribution of B conditional on the

. Examples are a national health service, a national police service and a global company with worldwide branches. Communication must be supported within and between domains and external services may be accessed. For example, health service domains may all access a national Electronic Health Record service; police service domains may all access a national Vehicle Licensing service. (a) (i) Define publish/subscribe communication. [3 marks] (ii) What are the advantages and disadvantages of offering publish/subscribe as the only communication service?

You are a 22nd century historian researching the "FEE" (First Epidemic Era) of 2019-2025, for which records are patchy. You research which government policy was in place in any given week during this historic phase. Policies, in order of severity, are: No restrictions, Tier 1, Tier 2, Tier 3, and Lockdown. (a) From other historic sources, you know the following about sequences of policy levels: if you are in a given policy level, there is a 40% chance you will stay there, a 20% chance that you will be upgraded to the next-highest (more severe) level next week, and a 10% chance that you will be downgraded to the next-lowest (less severe) policy level. The background lockdown probability (which applies if nothing more informative is known about lockdown) is 10%. For each observation sequence, there is also a 5% chance of the sequence ending at any point. Transitions to any other policy level beyond those already described are equally likely. Observation sequences begin with each policy level at equal likelihood. Using the information given above, construct the full transition probability table. [7 marks] (b) You want to estimate which policy was in place for the first six weeks of 2025, but unfortunately, the only information you have about this is a sequence of Covid case numbers for these six weeks: [0 99], [0 99], [> 200], [> 200], [> 200], [100 199]./ You know that case loads are associated with policy levels as in the Table below. Describe how you can calculate the sequence of most likely policy levels for these 6 weeks, giving numbers for at least three steps of the calculation. Assume that all policies are equally likely in the week preceding the first week. [8 marks] No Restriction Tier 1 Tier 2 Tier 3 Lockdown 0-99 cases 5% 10% 20% 50% 90% 100-199 cases 15% 40% 40% 30% 9% > 200 cases 80% 50% 20% 20% 1% (c) In which respects is the modelling described above not fully adequate to describe an actual epidemic?

(a) Describe the syntax of the synchronized keyword in Java and explain the effect on the runtime behaviour of a program. (b) Compare and contrast the approaches of using a single mutex to guard access to an entire data structure and using individual mutexes on each unit of storage? within the data structure. (c) Consider a queue data structure, based on a linked list. The operations pushTail and popHead are to be provided and it should be possible to execute both concurrently whenever doing so would be safe (but not when it would be unsafe). Provide a Java implementation of the data structure and concurrency control mechanism, including the methods to push new items on the tail of the queue and to pop items from the head. 2 Algorithms II (a) Briefly describe the Dijkstra algorithm for finding shortest paths from a single source and explain why it cannot be used on graphs with negative edge weights. [Pseudocode is not required.] (b) Describe and explain in detail the Johnson algorithm that finds all-pairs shortest-paths by repeatedly applying Dijkstra to each vertex, even in graphs with negative edge weights. [Pseudocode is not required but all phases of the algorithm must be clearly explained.] (c) Some people wonder why it would not be simpler to reweight edges by adding a sufficiently large constant K to each edge weight so as to make all the weights positive. Prove that this cannot work. (d) In Johnson's algorithm, why do we introduce a new vertex s? Could we not use, instead of a new vertex, one of the vertices of the original graph? Either prove that we can or provide a counterexample.

(a) Describe in detail an algorithm that returns the minimum distance from a point to a line segment in two dimensions. Ensure that you include all of your assumptions and all necessary mathematical calculations. [7 marks] (b) A quadratic Bezier curve is defined by three points, P1, P2, P3, and a parameter, t: P(t) = (1 t) 2 P1 + 2t(1 t)P2 + t 2 P3, 0 t 1 Describe an algorithm that draws the quadratic Bezier curve, using straight lines only, to within a tolerance . You may use the algorithm from part (a) and you may assume that you already have an algorithm for drawing a straight line. [8 marks] (c) Consider the control of detail in a curve that is represented by a sequence of many straight line segments. Describe how Douglas and Pucker's algorithm can be used to remove superfluous points. You may use the algorithm from part (a).

(a) Consider a simple random walk, Sn, defined by S0 = a and Sn = Sn1 + Xn for n 1 where the random variables Xi (i = 1, 2, . . .) are independent and identically distributed with P(Xi = 1) = p and P(Xi = 1) = 1 p for some constant p with 0 p 1. (i) Find E(Sn) and Var (Sn) in terms of a, n and p. [4 marks] (ii) Use the central limit theorem to derive an approximate expression for P(Sn > k) for large n. You may leave your answer expressed in terms of the distribution function (x) = P(Z x) where Z is a standard Normal random variable with zero mean and unit variance. [6 marks] (b) Consider the Gambler's ruin problem defined as in part (a) but with the addition of absorbing barriers at 0 and N where N is some positive integer. Derive an expression for the probability of ruin (that is, being absorbed at the zero barrier) when starting at position S0 = a for each a = 0, 1, . . . , N in the t 2

5 Logic and Proof (a) State (with justification) whether the following formula is satisfiable, valid or neither. Note that a and b are constants. h x [q(x) r(x)] r(a) x [r(x) q(a) p(x) q(x)]i p(b) r(b)

(b) Attempt to prove the formula [x y R(x, y)] x z R(x, f(z)) by resolution, with brief explanations of each step, including the conversion to clause form. [4 marks] (c) Give a model for the following set of clauses, or prove that none exists. {R(x, y), R(y, x)} {R(x, f(x))} {R(x, y), R(y, z), R(x, z)}

The Prolog predicate perm(+In,-Out) generates all permutations of the input list In. A programmer implements perm/2 as follows: perm([],[]). perm(L,[H|T]) :- take(L,H,R), perm(R,T). The predicate take(+L,-E,-R) removes one element (E) from the input list L and unifies R with the remainder of L. Thus, the list R has one element fewer than L. (a) Consider the perm/2 predicate

answer the question clearly