UL23/0207
CM1020
BSc EXAMINATION
COMPUTER SCIENCE
Discrete Mathematics
Release date: Monday 6 March 2023 at 12:00 midday Greenwich Mean Time
Submission date: Tuesday 7 March 2023 by 12:00 midday Greenwich Mean Time
Time allowed: 24 hours to submit
INSTRUCTIONS TO CANDIDATES:
Section A of this assessment consists of a set of TEN Multiple Choice Questions (MCQs)
which you will take separately from this paper. You should attempt to answer ALL the
questions in Section A. The maximum mark for Section A is 40.
Section A will be completed online on the VLE. You may choose to access the MCQs at
any time following the release of the paper, but once you have accessed the MCQs you
must submit your answers before the deadline or within 4 hours of starting whichever
occurs first.
Section B of this assessment is an online assessment to be completed within the same
24-hour window as Section A. We anticipate that approximately 1 hour is sufficient for you
to answer Section B. Candidates must answer TWO out of the THREE questions in Section
B. The maximum mark for Section B is 60.
Calculators are not permitted in this examination. Credit will only be given if all workings
are shown.
You should complete Section B of this paper and submit your answers as one document,
if possible, in Microsoft Word or a PDF to the appropriate area on the VLE. Each file
uploaded must be accompanied by a coversheet containing your candidate number. In
addition, your answers must have your candidate number written clearly at the top of the
page before you upload your work. Do not write your name anywhere in your answers.
© University of London 2023
Page 1 of 7
UL23/0207
SECTION A
Candidates should answer the TEN Multiple Choice Questions (MCQs) quiz, Question 1
in Section A on the VLE.
Page 2 of 7
Question 1
(a) List the elements of the following sets:
i. {x|x ∈ Z ∧ (x 2
= 6)}
ii. {x|x ∈ Z ∧ (x 2
= 9)}
iii. {x|x ∈ N ∧ (x mod 2 = 1) ∧ (x < 10)} [3]
(b) Let A and B be two sets such that |
A| = |
B| = n and |
A ∩ B| = 1. Find
i. |
A ∪ B|
ii. P(A ∪ B) | |
where n is a positive integer and
S. Show your working.
P(S) represents the power set of a set
(c) Prove the following set identities, using either Venn Diagrams or the rules
of sets. Show your working.
i. (A ∩ B) ∪ (A ∩ B) = A
ii. (A − B) − C A − C
⊆
iii. (A − C) ∩ (C − B) = ∅ [6]
[3]
(d) Let p, q and r be three propositions for which p and q are true, and r is
false. Determine the truth value of for each of the following:
i. p → (r → q)
ii. (p ⊕ r) → ¬q
iii. p ∧ (r → q)
Candidates should answer any TWO questions from Section B.
SECTION B
[4]
Page 3 of 7
UL23/0207
What are the truth values for each of the following:
ii. ∃x∃y(x + y = 0) ∨ (x ∗ y = 0)
iii. ∀x∀y(x ∗ y ≥ x + y)
⊆ C
and x ∈ B, then x ∈/ A − C. [4]
[4]
(f) Re-write the following statements without any negations on quantifiers:
i. ∃x∀y(x ≤ y)
¬∃xP(x)
¬∃x¬∃yP(x, y)
iii. ¬∃x∀yP(x, y)
ii.
i.
i. Let A, B and C be three sets. Prove by contradiction that if A ∩ B
ii. Suppose that I want to purchase a tablet computer. I can choose either a
large or a small screen; a 64GB, 128GB, or 256GB storage capacity, and
a black, white, gold, or silver cover. How many different options do I have?
[3]
[3]
(g) Decide whether the following arguments are valid or not. State the Rule of
Inference or fallacy used.
UL23/0207 Page 4 of 7
(e) The universe of discourse is the set of all positive integers, Z^+.
Question 2
(a) Minimise the following logic function using the Karnaugh maps method:
f(a, b, c) = a
0
b + bc0 + bc + ab0
c
0
[6]
(b) Given the following logical circuit with three inputs A, B and C:
[4]
ii. Simplify the logical expression in (i). Explain your answer. [5]
(c) Let f be a function R − {−3} → R − {1} with f(x) = x
x+3 .
i. Show that f is a bijective function [4]
ii. Find the inverse function f
−1
[2]
iii. Plot the curves of both function f and f
−1 on the same graph. [2]
iv. suppose we change the co-domain of the function f to be R:
f : R − {−3} → R
v. Is f still a bijective function? Explain your answer. [3]
(d) How many binary sequences of length 8 start with a 1 and end with a 0? [4]
i. Use the boolean algebra notation and write down the boolean expression of the
output, Q of this circuit.
UL23/0207 Page 5 of 7
Question 3
[3]
(b) Find the maximum number of comparisons to be made to find any record in a
binary search tree which holds 3000 records.
[6]
Use Dijkstra’s algorithm to find the shortest path from A to I. Show your working.
(a) Explain the difference between an Euler path and an Euler cycle.
(d) The figure shows a network of cycle tracks. The number on each edge represents
the length, in miles, of that track. Jay wishes to cycle from A to I as part of a
cycling holiday. She wishes to minimise the distance she travels.
[3]
(c) Explain what is meant by the term ‘path’.
UL23/0207 Page 6 of 7
∀x, y ∈ S, xRy ⇐⇒ x mod 2 = y mod 2
i. Draw the digraph of R. [2]
ii. Show that R is an equivalence relation.
iii. Find the equivalence classes for R
item is R a partial order? Explain your answer
END OF PAPER
(e) Given S is the set of integers {2, 3, 4, 5, 6, 7, 8}. Let R be a relation defined on S
by the following condition such that,
(f) Letf : A → B and g : B → C be functions. Prove that if g o f is one-to-one ,
then f is one-to-one.
[6]
[2]
[2]
[6]
UL23/0207 Page 7 of 7
