COMP11120 Mathematical Techniques for Computer Science Exam18-1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP11120

Mathematical Techniques for Computer Science

Section A

1.  a)  Show that for all i, j and kin Z,                (3 marks)

j modi = 0 and kmodi = 0        implies           (j + k) modi = 0


b)  Consider the following binary operation on the set of binary strings of length eight, where the ith symbol in

s * s\

is

.  1 if the ith symbols of sands\ are equal and

. 0 if they are different.

For example

00110101 * 10010001 = 01011011:

i)  Is the given operation commutative? Give a reason for your answer. (2 marks)

ii)  Is this operation associative? Justify your answer.                               (4 marks)

c)  Consider the following function which takes as its input a binary string and produces as its output a binary string using the following two-step procedure:

. replace every 0 by 1 and every 1 by 0;

. count the number of symbols in the given string and put that number of 1s at the end of the string.


For example, the string 0001101 becomes 11100101111111.

Is this function injective? Is it surjective? Justify your answers.         (8 marks)


d)  For the following functions from [1; ¥) to R, give information about which ones eventually dominates which other functions.

(i)  n     n log(n + 1)

(ii)  n     n3

(iii)  n     2

(iv)  n     210n                                                                                              (3 marks)


2.  Somebody has implemented a program that produces a pseudo-random number in the set f0; 1; 2; 3}.  They do this by sampling a stream of bits whenever the program is called. They read two bits from the stream, and then convert those two bits by parsing them as binary numbers.  The intention is that every number should appear with the same probability.

You have some doubts whether the probability distribution is as intended because you suspect that when sampling two bits, the second bit is not independent from the first one.

a)  Assume the program produces numbers as intended.  Give a probability space that describes the given situation.     (2 marks)

b)  You look at the bit sampling process.  Assume that the first bit sampled is equally likely to be 0 or 1, but the probability of the second bit being different from the first one is half the probability of them being equal.  Give a probability space that describes this situation.                                                                                (2 marks)

c)  For the situation from part b) calculate the conditional probability distribution given that the first bit sampled is 1.            (2 marks)

d)  Given the situation from part b) calculate the conditional probability distribution given that the second bit sampled is 1.    (2 marks)

e)  A random variable is created by running the program twice and adding up the two numbers that result.

Give the expected values of this random variable, once for the distribution from part a) and once for the distribution from part b).      (2 marks)

f)  You wish to test which of the two probability distributions from parts a) and b) better describes the situation, so you aim to carry out Bayesian updating to find out whether the implemented program matches the first or the second of these distributions.

You run the program three times, obtaining the numbers 3, 1 and 0 in that order. Carry out the corresponding calculations for Bayesian updating.   What do you conclude at the end of the process?                              (10 marks)

3.  a)  For each of the following statements state whether it is true or false.  In each case explain your answer.   (8 marks)

(i)  :(:P ^ Q) 三 (P ^ :Q)

(ii)  A propositional formula can be both a tautology and be satisfiable.    (iii)  A propositional formula can be both a tautology and a contradiction.

(iv)  For propositional formulae A1 ; : : :An  truth tables can be used to establish the validity of a judgement A1 ; : : : ;An -A in propositional logic.

b)  Consider this propositional formula:

(P $ Q) ^(P ! :(Q ^ P),:

(i)  Use our CNF algorithm to transform the formula into conjunctive normal form. (2 marks)

(ii)  Transform the formula into disjunctive normal form and simplify your answer as much as possible.    (3 marks)

Justify all the steps in your derivations.

c)  Give a natural deduction proof for the following.                                       (3 marks)

P -Q! (P ^ Q)

Use the inference rules of our natural deduction system, which are given on the last pages of this exam paper.

d)  Consider the first-order language with the two binary predicate symbols I;B, three unary predicate symbols H ; St ; S, two constants JRL; Ref and a supply of variables x;y; z; : : :. Assume the non-logical symbols are interpreted as follows.

I(x;y)   means that x is an item in y

B(x;y)   means that x borrows y

H(x)   means that x is high-demand

St(x)   means that x is a staff member at the Univ. of Manchester S(x)   means that x is a student at the Univ. of Manchester

JRL    represents John Rylands Library

Ref   represents the Reference Section

Express each of the following sentences as formulas.                                 (4 marks)

(i)  Items in the Reference Section cannot be borrowed.

(ii)  There are items in the John Rylands Library which cannot be borrowed.

(iii)  Borrowing high-demand items in the John Rylands Library is restricted to staff and students of the University of Manchester.


2024-01-15