CSC2047 Assignment 1

CSC2047 – Assessment: Individual Coursework 1

Question Sheet
Total Marks: 100

1.
a. Let 𝐴, 𝐵 and 𝐶 be sets. Show that 𝐴 × (𝐵 ∩ 𝐶) = (𝐴 × 𝐵) ∩ (𝐴 × 𝐶)
(4 marks)
b. Let 𝑓: ℝ → ℝ and 𝑔: ℝ → ℝ be functions such that
𝑓(𝑥) = 5𝑥 − 2 and 𝑔(𝑥) = 𝑥
2 − 4.
Give a definition for the composite function 𝑓 ∘ 𝑔.
(4 marks)
c. A graph 𝐺 = (𝑉, 𝐸) is said to be isomorphic to a graph 𝐻 = (𝑉
′
,𝐸
′
) if there exists a
bijective function, 𝑓, from the vertices of 𝐺 to the vertices of 𝐻 such that for two
adjacent vertices in 𝐺, 𝑢 and 𝑣, the corresponding vertices in 𝐻, 𝑓(𝑢) and 𝑓(𝑣), are
adjacent.
Given the two graphs
𝐺 = ({1,2,3},{(1,2), (2,3)}) and 𝐻 = ({−2,0,2},{(−2,0), (0,2)},
show that 𝐺 is isomorphic to 𝐻.
(12 marks)
2.
a. Given the graph 𝐺, which can be illustrated as
Formally define the graph 𝐺′ which is the largest possible subgraph of 𝐺 where every
vertex in 𝐺′ has degree 3.
(5 marks)
4
1
2
3
5
2
3
1
0 -2
2
CSC2047 – Assessment: Individual Coursework 1
b. Using appropriate propositional variables, construct a well-formed formula (WFF) for
the expression:
“If Paul and Jay go to the shops then Alex will not go to the shops.”
Make sure to clearly state how your propositional variables relate to the expression.
(7 marks)
c. Using the same propositional variables defined in (2b), construct a WFF for the
expression:
“Either Alex or Paul go to the shops with Jay, which is the same as saying, Alex and
Jay go to the shops and not Paul, or, Paul and Jay go to the shops and not Alex.”
(8 marks)
3. Let 𝐴 be an array of 15 integers and 𝐵 be an array of 10 integers. The arrays 𝐴 and 𝐵 are
indexed from 1 to 15 and 1 to 10 respectively. Construct predicates to assert that
a. The third element of 𝐴 is larger than all elements of 𝐵.
(3 marks)
b. The elements of 𝐵 form a consecutive sequence within 𝐴.
(3 marks)
c. If 𝑥 is an element of 𝐴 then – 𝑥 is an element of 𝐵.
(7 marks)
d. The value 7 occurs only once in 𝐴.
(7 marks)
4.
a. Let 𝑥, 𝑦 ∈ ℤ. Prove by construction that the sum of 𝑥 + 𝑦 is even when
i. 𝑥 and 𝑦 are both even,
(4 marks)
ii. 𝑥 and 𝑦 are both odd.
(4 marks)
b. Prove by construction, that for any 𝑛 ∈ ℤ that (𝑛
2 mod 2) = 0 or 1.
(12 marks)
5.
a. Give a recursive definition for the following sequence which is defined over the
natural numbers:
−2, 6, −18, 54, −162, 486, …
(3 marks)
b. Use the pseudo code below to formulate an equivalent recursive definition
Function f(n)
if n = 0:
return 1;
else:
return f(n-1)+3n+2;
end
end
(3 marks)
CSC2047 – Assessment: Individual Coursework 1
c. Using your recursive definition from (5b) compute 𝑓(3).
(1 mark)
d. Find a closed-form solution to the function
𝑓(𝑛) = {
0 𝑖𝑓 𝑛 = 0
𝑓(𝑛 − 1) + 2𝑛 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
(5 marks)
e. Prove, by induction, that your closed-form solution in (5d) is correct.
(8 marks)