闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

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

Main Exam A Semester 2 2019

MATH1064

Discrete Mathematics for Computation

Multiple Choice Section

In each question, choose at most one option.

Your answers must be entered on the Multiple Choice Answer Sheet.

1. Let A = {1,a,b,x,y,z} and B = {1, 2,a,x,y}. Then the number of elements in A U B is

(a) 2. (b) 3. (c) 4.

(d) 5. (e) 6.

2. Let f : P({1, 2, 3, 4, 5, 6, 7, 8}) ! N be a function deﬁned by f(A) = |A|. Then f is

(a) surjective but not injective.

(e) not a valid function.

(b) neither surjective nor injective.

(d) injective but not surjective.

3. Let A = {a,{b}, {c,b},a} be a set and let P(A) be its power set. Which one of the following statements is true?

(a) |A| = 4

(d) |A| = |P(A)|

(b) b 2 A

(e) P(A) [ {a} = P(A)

4. Let X = {1, 2, ..., 2n}. Then the cardinality of the power set |P(X)| is equal to

(a) 2n .

(d) 8n .

(b) 4n .

(e) 10n .

5. Given |A| = 10, |B| = 20, |C| = 30, |A U B| = 5, |A U C| = 5, |B U C| = 10 and |A U B U C| = 3, then |A [ B [ C| is

(a) 20. (b) 43. (c) 57.

(d) 60. (e) impossible to determine.

6. Which of the sets listed below is given by the shaded region in the following Venn diagram?

(a) A [ B [ C

(d) A [ (B U C)

(b) (A [ B) U C

(e) A U (B [ C)

7. A large jar is full of blue, red, white and black balls. You grab ﬁve of them. How many possible outcomes are there?

(a) ✓ ◆3(8)

(b) ✓ ◆2(7)

(d) ✓ ◆4(8)

(e) None of the above

8. The number of permutations of {1, 2, 3, 4, 5} is

(a) 24. (b) 72. (c) 96.

(d) 120. (e) none of the above.

9. An expression of parenthesis is correctly matched, if every initial segment of the expres- sion has at least as many opening parentheses than closing parenthesis (eg. “(())()” or “(()())” for n = 3).

What is the number of expressions containing 4 pairs of parentheses which are correctly matched?

(a) 4 (b) 14 (c) 21 (d) 24 (e) 31

10. How many rearrangements are there of the word WOOLLOONGABBA?

(a) ✓ ◆2(8)

(b)

13!

4! · 23

(d) 137

(e) 7! · ✓ 2(13)◆

11. The remainder when dividing 765432 by 9 is

(a) 0. (b) 1. (c) 3. (d) 5. (e) 7.

12. Let p,q 2 N be prime numbers, let n = pq, and let a > 1, a | n. Then we may conclude that

(a) a - p and a - q . (b) a | p and a | q .

(e) a · p = n.

13. Which one of the following functions f : Z ! Z is injective?

(a) f(n) = n3 − n (b) f(n) = 2n +8

(e) f(n) = n4

14. Which one of the following statements is not correct?

(a) 2n 2 O(3n ) (b) 7log(n) 2 O(1)

(e) log2 (n) 2 ⇥(log10 (n))

15. Let f : N ! N be deﬁned by f(n) = n +5n+72 . Which one of the following statements is not correct .

(a) f(n) 2 O(n3 ) (b) f(n) 2 ⇥(n2 )

(e) f(n) 2 O(n4 )

16. Which one of the following propositions is a contradiction?

(a) p ^ (q ^ r) (b) (p ! q) ^ (¬ q ^ q) (c) (p ! q) ^ q

(d) (p ^ q) ^ (¬ p ^ ¬ q) (e) (p $ r) ^ (p ^ ¬ q)

17. Identify the correct negation of the following quantiﬁer statement.

Ax 2 D: (P(x) ^ ¬Q(x))

(a) 3x 2 D: (P(x) ! Q(x)) (b) Ax 2 D, (P(x) ^ ¬Q(x))

(e) Ax 2 D, (P(x) ^ Q(x))

18. What is the expected number of times a “3” appears when a fair die is rolled 12 times?

(a) 2 (b) 3 (c) (d) 4 (e) 5

19. What is the expected number that appears on a die biased such that “5” and “6” come up twice as often as every other number?

(a) 3 (b) 4 (c) 5 (d) 6 (e) 7

20. The binary number (1110)2 is equal to

(a) (111)3 .

(d) (A)16

(b) (14)10 .

(e) all of the above.

Extended Answer Section

There are ﬁve questions in this section, some with a number of parts. Write your answers in the space provided below each part. You must show your working and give reasons for your answers. If you need more space there are extra pages at the end of the examination paper.

1. (a) Write down the statement of the binomial theorem.

(b) In the expansion of (x +1)7 , what is the coeﬃcient of x3 ?

(Do not evaluate formulas involving exponents, factorials, binomial coeﬃcients, etc.)

2. (a) Write down the statement of the quotient remainder theorem.

(b) Using the Euclidean algorithm, ﬁnd gcd(154, 40). Show all working.

a = −b.

3. (a) Let G = (V,T,S,P) be the grammar with vocabulary V = {a,b,S,A,B}, start symbol S, terminal symbols T = {a,b}, and production rules

P = {S ! aA, A ! aA, A ! B, B ! b, B ! bB}.

(i) Determine the language L(G) generated by the grammar G.

(ii) Construct a ﬁnite state automaton that recognises L(G).

Your automaton may be deterministic or non-deterministic.

(b) Determine a context-free grammar G\ that generates the language

L\ = {abn a | n ≥ 2},

and show that L\ = L(G\ ).

4. (a) Consider the relation R on {1, 2, 3, 4}, given by

R = {(1, 1), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 4)}.

For each of the following statements, determine whether the statement is true or

false. If it is true, give a brief reason (you do not need to give a formal proof). If it

is false, give a counterexample.

i)R is reﬂexive.

ii)R is symmetric.

iii)R is transitive.

iv)R is anti-symmetric.

(b) Which of the following graphs contain an Eulerian circuit?

(iii)

(c) Let G be a graph with six vertices and with degrees 1, 2, 3, 3, 3, 4. How many edges does G have? Explain your answer.

(d) Prove that every simple graph with exactly 4 vertices and at least 4 edges must be connected.

5. (a) Suppose that (an )n≥1 is a sequence deﬁned by

a1 = 0 and ak = ak−1 +2k for all k ≥ 2.

Prove that for all n ≥ 1, we have

an = n2 + n − 2.

(b) Show that it is possible to arrange the numbers 1, 2, . . . , 2k in a row such that for any two of these numbers, their average never appears between them.

In other words, show that there exists an arrangement a1 ,a2 , . . . ,a2k of the numbers 1, 2, . . . , 2k such that for all pairs of numbers ai and aj , i < j, we have ak (ai +aj )/2 for all i < k < j . (Hint: Use induction.)