Briefly explain the differences between combinational and sequential logic. [2 marks] (b) With the aid of appropriate diagrams, briefly explain the operation of Moore and Mealy finite state machines and highlight their differences. [6 marks] (c) The state sequence for a binary counter is as follows: A B C D 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 The counter is to be implemented using four synchronously clocked D-type flip-flops. (i) Draw a state table for the counter, showing the required D inputs. [4 marks] (ii) Find expressions for the D inputs, making use of unused states if appropriate. [6 marks] (iii) What problem could occur when the counter circuit is powered-up? Give two possible general methods for overcoming the problem. [2 marks]

(a) With the aid of relevant diagrams, show the effect on the output of a combinational logic circuit of a: (i) static hazard; (ii) dynamic hazard. [3 marks] (b) Simplify the following expressions using Boolean algebra: (i) X = (A + B + A . B).(A + B). A . B (ii) Y = (A + B + A . B). C [4 marks] (c) Given: F = A . B . C . D + A . C + B . C . D + B . C + A . C . D + A . B . C . D (i) Show using a Karnaugh map that F can be simplified to F1 = A . B + A . B + A . C + B . C . D [2 marks] (ii) Show that there are a total of four possible expressions for F. [3 marks] (iii) Show how F1 can be implemented using NAND gates and draw the circuit diagram. Assume that complemented input variables are available. [2 marks] (iv) Show how the static 1 hazard in F1 can be eliminated using a Karnaughmap-based approach. [2 marks] (v) Now implement F1 assuming that only 2-input NAND gates are available. [4 marks

Let X and Y be sets. You are reminded that a relation from X to Y is a subset of the product X Y . (a) Explain what it means for a relation f from X to Y to be a function, an injection and a surjection from X to Y . [4 marks] (b) A bijection from X to Y is defined to be a function from X to Y which is both an injection and a surjection. Prove that a function f from X to Y is a bijection iff it has an inverse function g, i.e. g is a function from Y to X such that g f = idX and f g = idY . [Remember to prove both the "if" and "only if" parts of the assertion.] [12 marks] (c) Describe, without proof, a bijection from P(X Y ) to (X P(Y )) and its inverse. [4 mark

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]

(a) Suppose that X is a random variable whose value r is distributed Geometric(p). Write down the expression for the probability P(X = r). [3 marks] (b) By using a suitable generating function or otherwise, show that the expectation E(X) = (1 p)/p. [5 marks] The University Computing Service define a serious power outage as a power cut that lasts for longer than their Uninterruptable Power Supply equipment can maintain power. During the course of an academical year the number of serious power outages is a random variable whose value is distributed Geometric(2/5). Accordingly, the probability of having no serious power outages during the course of a year is 2/5. (c) The University is investigating a compensation scheme which would make no payment over the year if the number of serious power outages were zero or one but which would pay the Computing Service 1000 for every such outage (including the first) if the total number of serious power outages in a year were two or more. Determine the expected annual sum that the Computing Service would receive. [8 marks] (d) To what value would the parameter of the Geometric Distribution have to be changed (from 2/5) for the expected annual sum to be 750? [4 marks]

) An indicator light can be in one of three states: OFF, FLASHING and ON, with probabilities 1/2, 2/5 and 1/10 respectively. A test panel has five such lights whose states are mutually independent. (i) What is the probability that all five lights are OFF? [3 marks] (ii) What is the probability that three lights are OFF, one light is FLASHING and one light is ON? [3 marks] (iii) What is the probability that three or more lights are OFF and at most one is ON? [9 marks]

Consider the following class PrimeNumbers, which has three methods. The first, computePrimes() takes one integer input and calculates that many prime numbers. Iterator() returns an Iterator object that will iterate through the primes, and toString() returns a string representation.

public class PrimeNumbers implements Iterable { private List primes = new ArrayList(); public void computePrimes (int n) { int count = 1; // count of primes int number = 2; // number tested for primeness boolean isPrime; // is this number a prime while (count <= n) { isPrime = true; for (int divisor = 2; divisor <= number / 2; divisor++) { if (number % divisor == 0) { isPrime = false; break; // for loop } } if (isPrime && (number % 10 != 9)) // FAULT { primes.add (number); count++; } number++; } }

@Override public Iterator iterator() { return primes.iterator(); }

2

@Override public String toString() { return primes.toString(); } }

computePrimes() has a fault that causes it not to include prime numbers whose last digit is 9 (for example, it omits 19, 29, 59, 79, 89, 109, ...).

Normally, this problem is solved with the Sieve of Eratosthenes. The change in algorithm changes the consequences of the fault. Specifically, false positives are now possible in addition to false negatives.

(a) Reimplement the algorithm for calculating primes using the Sieve of Eratosthenes approach, but leave the fault in place.

(b) What is the first false positive and how many primes must a test case generate before encountering it?

(c) A test must reach a location in a program that contains the fault (reachability). After the location is executed, the state of the program is incorrect (infected). The infected state must propagate through the execution and cause some output of the final state of the program to be incorrect (propagation). Finally, the tester must observe part of the incorrect portion of the final program state (revealability). (This all serves to illustrate that testing is actually really complicated!) What does this example illustrate about these four concepts?

Given the following class: class Q2 { private int a; private int b; private int c; public void setAint a)this.a = a; } public void setB(int b{this.b = b;} public void setc(int c){this.C = } public int geta0{return a;) public int gets0freturn b;} public int getc0{return c} public int m1int a, int b){ return a + b; public boolean m2 (int x, int y)} return m1(x, y) +x + y < 10; What is the output of the following code segment: Q2 0bji = new Q20: y 10; What is the output of the following code segment? Q2 obj1 = new Q20; Q2 obj2 = new Q20; obji.setA(0); obj1.setB(e); obj1.setC(10); obj2.setA(4); obj2.setB (5); obj2.setc(-1), while(lobj1.m2(1, 3)) {obj2.setc(obj2.getc) + 10); System.out.println("obj2.c = "+ obj2.getc0); A. obj2.c = 10 B. obj2.c = 9 C. Infinite loop D. obj2.c = 1

answer all the above questions.