Computer Science & Software Engineering
SEMESTER 2, 2015 SUPPLEMENTARY AND DEFERRED EXAMINATIONS
CITS2211
Discrete Structures
FAMILY NAME: ____________________________ GIVEN NAMES: ______________________


STUDENT ID: SIGNATURE: ____________________________

This Paper Contains: 24 pages (including title page)
Time allowed: 2:10 hours (including reading time)

INSTRUCTIONS:

The exam has 12 questions with a total value of 120.

Answer all questions in the spaces provided in the question booklet.

All answers must be throughly justified. Answers that are given without explanation will be
assumed to be guesses and will not be given any marks - even if they happen to be correct.

Candidates may bring one double-sided A4 page of handwritten notes to the examination.
These notes must be hand written, not photocopies or printed and may be written on both sides
of one A4 page. The page can not be folded or have any attachments. Any notes that do not
meet these conditions will be considered unauthorised material, and will be removed by the exam
invigilators. Your notes page must be submitted with your exam paper at the end of the
exam.

Calculators are not required.

PLEASE NOTE


Examination candidates may only bring authorised materials into the examination room. If a supervisor
finds, during the examination, that you have unauthorised material, in whatever form, in the vicinity of your
desk or on your person, whether in the examination room or the toilets or en route to/from the toilets, the
matter will be reported to the head of school and disciplinary action will normally be taken against you. This
action may result in your being deprived of any credit for this examination or even, in some cases, for the
whole unit. This will apply regardless of whether the material has been used at the time it is found.
Therefore, any candidate who has brought any unauthorised material whatsoever into the examination room
should declare it to the supervisor immediately. Candidates who are uncertain whether any material is
authorised should ask the supervisor for clarification.

Supervisors Only - Student left at:
This page has been left intentionally blank

2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 3
1. Express the following statements using propositional or predicate logic.
State any assumptions you make.
(a) The software should provide an update of the situation which is
either suitable or not, and if the situation is suitable then the
software should start to process the entry fee.
[2 marks]
(b) If something is a binary relation then there is a set such that the
relation is a subset of the product of the set with itself.
[2 marks]
QUESTION 1 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 4
(c) In this department there is an employee whose supervisors are not
in the department.
[3 marks]
(d) For some two different natural numbers there is a third natural
number such that the sum of the first two is the same as the sum
of the third one with itself.
[3 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 5
2. (a) Prove, or disprove, whether (P ↔ Q) → ((P ↔ Q) ∧ Q) is a
tautology.
[5 marks]
(b) Prove, or disprove, that (P ∨ Q) → R is logically equivalent to
¬((Q ∧ ¬R) ∨ (P ∧ ¬R)).
[5 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 6
3. (a) In the Venn diagram below, shade in the region C \ (A \B).
A B
C
[2 marks]
(b) Let A = {0, 1, {0, 1},∅}, B = {{0, 1}, {0}, 0}. Write down the
following sets, using correct bracketing.
A ∪B =
A ∩B =
[2 marks]
QUESTION 3 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 7
(c) State the general formula relating the number |A∪B| to the num-
bers |A|, |B|, and |A∩B|. Then check that this formula is satisfied
for the sets A and B of Part (b).
[4 marks]
(d) For the sets A and B of Part (b), write down the following num-
bers:
|P(A)| =
|A×B| =
[2 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 8
4. Give an example, with reasons for your answer, of a binary relation
on Z that is:
(a) Many to one
[3 marks]
(b) Transitive but not symmetric
[3 marks]
(c) Not reflexive, not transitive, not symmetric
[4 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 9
5. Recall that N is the set {0, 1, 2, 3, . . .} of natural numbers, and that N0
is the same set with 0 excluded: N0 = {1, 2, 3, . . .}.
(a) Let g : P(N) → N defined by g(A) = |A|. Is g injective? Surjec-
tive? Bijective? Explain carefully your answer.
[4 marks]
QUESTION 5 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 10
(b) Show that P(N0) is NOT countable.
Hint: use a similar argument to Cantor’s diagonal.
[6 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 11
6. (a) How many passwords satisfy all of the following conditions:
• The length is 4 characters.
• All characters are either digits or upper case letters.
• It must contain at least one letter and at least one digit.
[4 marks]
QUESTION 6 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 12
(b) Let S be the set of finite binary strings. Define the relation R on
S by:
xRy whenever the digit 0 appears in both x and y or neither of
them, and the digit 1 appears in both of them or neither of them.
i. Show that R is an equivalence relation.
[3 marks]
ii. What is the equivalence class of the empty string? Describe
the equivalence classes of R. In particular, explain how many
there are.
[3 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 13
7. (a) Draw a non-deterministic finite state machine for alphabet {a, b}
that recognises exactly all the words in the following language.
Each word uvw in the language can be chopped into three sub-
strings u, v and w such that: (1) v is not empty and contains no
as and (2) w contains no bs but consists in just an even number
of consecutive as.
[5 marks]
(b) Draw a deterministic finite state machine to recognize the same
language as in 7(a).
[5 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 14
8. (a) Give a regular expression for the language L of all strings of 0s
and 1s where each pair of adjacent 1s is immediately followed by
at least two adjacent 0s.
[3 marks]
(b) Give a regular expression for the complementary language to L
from question 8(a). That is, the set of strings from that alphabet
which are not in L.
[3 marks]
QUESTION 8 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 15
(c) Let L ⊆ {0, 1, 2, 3}∗ be the language consisting of all strings such
as 000111000 that have some number of 0s followed by the same
number of 1s and then the same number of 0s again. Prove that
L is not a regular language.
[4 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 16
9. (a) Consider a project that is broken down in tasks with dependencies
and time to complete as follows:
Task Hours to perform Pre-requisite tasks
A 4 None
B 2 D,A
C 2 B
D 3 None
E 1 D
F 3 E
G 3 C
H 1 G
I 3 J,H
J 4 F,C
i. Construct a PERT chart for this process.
[3 marks]
ii. Determine the minimum time-to-completion, a critical path
and a topological sort for this process.
[3 marks]
QUESTION 9 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 17
(b) Show that, for an integer n, if n3 is a multiple of 3, then n is a
multiple of 3.
[4 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 18
10. (a) i. Prove, using the pigeonhole principle or otherwise that: if
each point of the Euclidean space R3 (i.e. normal three di-
mensional space) is coloured red, green, or blue, then there
are two points of the same colour at distance 1cm from each
other.
[3 marks]
ii. Given a group of 100 people, at least how many people were
born during the month when the most people in the group
were born?
[2 marks]
QUESTION 10 CONTINUES OVER THE PAGE
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 19
(b) Use induction to show that 11n+4 is divisible by 5 for all positive
integers n.
[5 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 20
11. Outline a procedure that could be used by a Turing Machine to com-
pute the following function given an input string from the alphabet
{a, b}. The output should be a string an consisting of just the letter a
repeated a certain number n of times. This an should be equal to the
longest string of consecutive as in the input string. For example, input
abaabbbaaa should produce output aaa.
You do not have to give a formal specification of the machine’s moves,
but explain the algorithm in terms of the series of steps the machine
would use for this calculation.
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 21
SPACE FOR Q11 Answer continued ...
[10 marks]
SEE OVER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 22
12. (a) Define a grammar that generates the language (01)∗1(0)∗. Justify
your answer.
[5 marks]
(b) Can you define a context-free grammar that generates the lan-
guage 0∗1(01)∗ (from Question 12(a))? Justify your answer.
[5 marks]
END OF PAPER
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 23
Blank page for extra writing if needed
2nd SEMESTER 2015 SUPPLEMENTARY EXAMINATIONS 24
Blank page for extra writing if needed

欢迎咨询51作业君