Exam2009Q.pdf

Loading ...
Global Do...
News & Politics
 
 
 
EXAM COVER SHEET 
      NOTE: This exam paper may be        
RETAINED by the student 
 
EXAM DETAILS 
Course Code:  
MATH1074/MATH2045 
Course Description:       Mathematics for Computing/Discrete Mathematics 
Date of exam:  
11/06/2009      Start time of exam:     1:45 PM     Duration of exam:     2hr 15min
Total numbe
 
r of pages (incl. this cover sheet)    5     
ALLOWABLE MATERIALS AND INSTRUCTIONS TO CANDIDATES 
 
1. Write your full name and student number on each exam booklet together with the number of exam books used.  
2. Students must not write, mark in any way any exam materials, read any other text other than the exam paper or 
do any calculations during reading time.  
3. This is a CLOSED BOOK Exam.  
4. Commence each question on a new page. Carry out the instructions on the front cover of the exam script book 
and the front of this exam paper.  
5. Non-text-storing calculators are allowed.  
6. Attempt all questions. There are 6 questions in the examination.  
7. There is a total of 210 marks on this examination.  
8. To obtain full marks for a question, full working should be shown.  
9. This examination contributes 60% of your final mark in MATH1074/MATH2045.  
Created on: 8 May 2009 -- 3-51-38:693 -- 3389  
MATH1074/MATH2045 Examination, June 2009
2
1. Let A = {a, b, c}, B = {c, d, e, f, g}, C = {1, 2, 3, 4} and D = {x, y}.
(a) (i) Find A ∪B.
(ii) B \ A.
(iii) B ∩ C.
(b) For this part of the question, write each answer as a set of ordered pairs.
(i) Find a one-to-one function from A to C.
(ii) Find a function from B to C which is not onto.
(c) Let ρ = {(a, 2), (a, 3), (c, 1)} be a relation between A and C, and let σ =
{(1, x), (2, y), (4, y)} be a relation between C and D.
(i) Find the logical matrix representations Mρ and Mσ of ρ and σ.
(ii) Find the composite relation σ ◦ ρ.
(iii) Find Mσ◦ρ.
(iv) Find the Boolean matrix product Mρ · Mσ, and verify that it equals
Mσ◦ρ.
(d) Let φ = {(a, a), (a, b), (b, a), (b, b), (c, c)}. Is φ an equivalence relation on A?
Justify your answer.
((3× 5) + (2× 5) + (4× 5) + 5 = 50 marks)
2.
(a) Write down an example of a real number x for which |x| = x+ 5.
(b) Find two real values of x such that b−xc = dxe − 6.
(c) Evaluate log5 625.
(d) Let p(x) be the 3rd-degree (“cubic”) polynomial x3 − x2 + 1.
(i) If q(x) is another polymonial such that
deg[p(x)+ q(x)] = 0
(∗)
then what is deg[q(x)]?
(ii) Find an example of a polynomial q(x) which satisfies the equation (∗)
of part (i).
(5 + 5 + 5 + (5 + 5) = 25 marks)
MATH1074/MATH2045 Examination, June 2009
3
3.
(a) Consider the compound proposition P ∨ (Q ∧ ∼R) → ∼P ∨Q ∨R.
(i) Construct the truth table for the compound proposition.
(ii) Is the compound proposition a tautology, a contradiction or a contin-
gency? Justify your answer.
(b) Let P (x) mean “x is an odd integer”. Consider these two predicate formulae:
I. ∀x P (x)
II. ∃x P (x)
(i) Find a domain of interpretation D1 ⊆ Z for which I and II are both
false.
(ii) Find a domain of interpretation D2 ⊆ Z for which I and II are both
true.
(iii) Find a domain of interpretation D3 ⊆ Z for which I is false and II is
true.
(iv) Is there a domain of interpretation D4 ⊆ Z for which I is true and II is
false? Explain your answer.
(c) (i) Give a direct proof that, for all integers x and y, if x is odd and y is
even then 3x− y2 is odd.
(ii) Prove by induction that, for every positive integer n,
12 + 22 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
.
((10 + 5) + (4× 5) + (5 + 10) = 50 marks)
4.
(a) Let d be the greatest common divisor of 52 and 144.
(i) Use the Euclidean algorithm to find d.
(ii) Using your answer to (i), express d as a linear combination
d = a · 52 + b · 144
of 52 and 144, where a and b are integers.
(b) The table below is designed to enable the movement of discs to be recorded,
during the solution to the Towers of Hanoi puzzle for three poles. The first
row shows the initial stage of the puzzle for the case where the number of
discs is n = 3. In this case the large disc is dl, the medium-size disc is dm
and the small disc is ds.
(i) Complete the table for the case of 3 discs.
MATH1074/MATH2045 Examination, June 2009
4
Stage
Positions of Discs
Pole 1 Pole 2 Pole 3
0
ds
dm
dl
—
—
(ii) Suppose instead that we have 4 discs (n = 4). To solve the puzzle in
the least number of steps, where should the smallest disc be placed in
the first move?
(iii) Suppose instead that we have 10 discs (n = 10). How many steps are
needed to solve the puzzle?
((10 + 10) + (10 + 5 + 5) = 40 marks)
5.
(a) Eight people are walking along side by side when they come to a narrow
bridge. They must cross the bridge in single file.
(i) In how many ways can the order of the eight people be chosen?
(ii) The eight people decide to select a leadership group of 3 people to go
first. In how many ways can the leadership group be chosen?
(iii) The eight people decide to choose a single Leader to go first, followed
by a First Deputy Leader and a Second Deputy Leader in that order.
In how many ways can the leadership group be chosen?
(b) A man throws all his socks into a drawer. Next morning he rushes to the
drawer and starts pulling out socks one at a time, hoping to quickly find a
matching pair.
(i) If he has 20 differently coloured pairs of socks, how many socks must
be grabbed before he can be sure that two of them match?
(ii) If, instead, he has 100 pairs, how many socks must be grabbed before
he can be sure that two of them match?
((3× 5) + (2× 5) = 25 marks)
MATH1074/MATH2045 Examination, June 2009
5
6. Suppose that two dice are tossed.
(a) Write down the sample space S of all possible outcomes.
(b) Find the probability of getting two fours.
(c) Find the probability of getting two odd numbers.
(d) Find the probability that the sum of the two scores is at most 5.
(e) Given that the two scores are both odd, what is the probability that their
sum is at most 5?
(f) Given that the sum of the two scores is at most 5, what is the probability
that they are both odd?
(g) Are the two outcomes “sum ≤ 5” and “both odd” dependent or indepen-
dent?
(4 + 1 + 3 + 3 + 3 + 3 + 3 = 20 marks)