Problem 4

Order the following functions in increasing order of asymptotic complexity:

. n “log n

.  “n2 log n + 2n3

.  ^n (log n)

.  T(n) where T(n) = 3T(n /2) + 2n; T(1) = 1

.  T(n) where T(n) = T(n __ 1) + log n; T(1) = 1

.  T(n) where T(n) = 3T(n /3) + 2nlog n; T(1) = 1

Problem 5

Let R 己 A 根 A be a partial order and let f  : B 一 A be an arbitrary function.

Deine S 己 B 根 B as follows:

(x, y) e S   if and only if    (f (x), f (y)) e R

prove or disprove the following:

(a) If f is surjective then S is a partial order

(b) If f is injective then S is a partial order

Problem 6

prove or disprove the following:

For all graphs G and H where H is a subdivision of G:

(a) The clique number of H is less than or equal to the clique number of G

(b) The chromatic number of H is less than or equal to the chromatic number of H.

Problem 7

Give, with justiication, an example of an undirected graph with 6 vertices, 9 edges which is regular and planar.

Problem 8

For each of the following code snippets, provide an asymptotic upper bound for T(n), the running time of the code.

Problem 10

Let PF be the set of all propositional formulas.

Deine f : PF 一 Pow(PF) by

f (Ψ) = {ψ e PF  :  Ψ |= ψ}

Prove or disprove the following:

(a) For all Ψ, ψ e PF: f ((Ψ V ψ)) = f (Ψ) uf (ψ)

(b) For all Ψ e PF: f (一 Ψ) = (f (Ψ))c

Problem 11

Let f : B4 一 B be the boolean function deined as:

f (u, x, y, z) = {  1

if u = x and y = z

otherwise

which of the following boolean functions are equal tof?

(i)((u&&x) || (y&&z))|| ((!u&&!x) || (!y&&!z))

(ii)((1 + u + x) . (1 + y + z))%2

(iii)  1 — ((u + x) . (y + z)%2)

(iv)((u || x) && (y|| z))&&((!u ||!x) && (!y||!z))

(v) max{|1 — (u + x)| , |1 — (y + z)|}

(vi)  min{1 — | u — x |, 1 — |y — z |}

Problem 12

consider the following timetabling arrangement given in lectures:

The school administrator would like to know if it is possible to arrange an exam schedule where 3 (or more) subjects can be examined at the same time without any student having a clash (i.e.  two or more exams at the same time)

Do ONE of the following:

. Explain how this can be modelled as a graph theory problem, OR

. Explain how this can be modelled as a propositional logic problem.

In particular:

. Explain how to deine a suitable graph OR an appropriate set of propositional variables and formulas to model the situation

. Describe the associated graph theory / logic problem that needs to be solved

. Indicate how you could solve the problem. You do not have to ind a solution

Problem 13

we would like to pave a 1 X n rectangular path with a mix of 1 X 1 and 1 X 3 paving stones.

For example, if s represents a 1 X 1 stone and t represents a 1 X 3 stone,then possible ways of tiling a 1 X 6 path include:

. ssssss

. tt

. ssst

. ssts

. tsss

(Note that direction matters: e.g. ssstand tsss should be considered different arrangements)

a Let P(n, k) be the number of different arrangements of paving stones that can pave a 1 x n path using exactly k 1 x 3 paving stones.

Express P(n, k) either:

. in terms of combinatorial functions deined in lectures; or

. recursively (including base cases) in terms of P(n\, k\ ) where n\  三 n and k\  三 k.

b Let P(n) = P(n, 0) + P(n, 1) + . . . be the number of arrangements of paving stones that can pave a 1 x n rectangular path.

Find a recurrence equation for P(n) and provide,with justiication, an asymptotic upper bound.

Problem 14

Let (Ω, P) be a probability space.

prove or disprove:

(a) For all events A, B 己 Ω: If P(A) = P(A U B) then P(B) = P(A n B)

(b) For all events A, B 己 Ω with P(A), P(B) > 0: If P(A|B) > P(A) then P(B|A) > P(B)

Problem 15

Suppose we roll n fair, six-sided dice.

Let X be the random variable that indicates the maximum value of all dice.

(a) For m e [1, 6] what is the probability that X 三 m?