Key Concepts in Computer Science -Assignment 7

1) [8 marks] Determine whether each of these functions from Z to Z is one-to-one.
a) f(n) = n – 1
This is one to one. Any y ∈ codomain will get exactly one element from the domain (n + 1).
b) f(n) = n2 + 1
This is not one to one. For example, 5 will be covered by 2 and -2.
c) f(n) = n3
This is one to one. Every element in the codomain is covered at most once.
d) f(n) = ⌈ 𝒏/𝟐 ⌉
This is not one to one. For example, 3 will be covered by 5 and 6.
2) [8 marks] Which functions in the previous question (question 1) are onto?
f(n) = n – 1
This is onto. Any y ∈ codomain will be mapped to n + 1.
f(n) = n^2 + 1
This is not onto. For example, 0 is not covered by any integer in the domain.
f(n) = n^3
This is not onto. For example, 2 is not covered by any integer in the domain.
f(n) = ⌈ 𝒏/𝟐 ⌉
This is onto. Any y ∈ codomain will be mapped to 2n.
3) [8 marks] Find f∘ g and g∘ f, where f(x) = x2+2 and g(x) = x+3, are functions from R to R.
f∘ g = f (g(x)) = (g(x))2+2 = (x+3)^2+2= x^2+6x + 9 + 2 = x^2+6x + 11
g∘ f = g (f(x)) = f(x) +3 = x2+2 + 3 = x2+5
4) [9 marks] Find the first five terms of the sequence defined by each of these recurrence relations and initial conditions.
a) an = -3an-1 , a0 = -2
a1 = -3×-2 = 6
a2 = -3×6 = -18
a3 = -3×-18 = 54
a4 = -3×54 = -162
a5 = -3×-162 = 486
b) an = 2𝑎𝑛−12+3 , a0 = 1
a1 = 2×(12) + 3 = 5
a2 = 2×(52)+ 3 = 53
a3 = 2×(532) + 3 = 5,621
a4 = 2×(56212) + 3 = 63,191,285
a5 = 2×(631912852) + 3 = 7,986,276,999,902,453
c) an = 2an-1 – an-2 + 2an-3 , a0 = 1, a1 = 1, a2 = 2
a3 = 2×2 – 1 + 2×1 = 5
a4 = 2×5 – 2 + 2×1 = 10
a5 = 2×10 – 5 + 2×2 = 19
a6 = 2×19 – 10 + 2×5 = 38
a7 = 2×38 – 19 + 2×10 = 77
5) [9 marks] What are the values of these sums, where S = {1, 3, 7}?
a) Σ𝑗𝑗 ∈𝑆 = 1 + 3 + 7 = 11
b) Σ𝑗^2𝑗 ∈𝑆 = 1^2 + 3^2 + 7^2 = 59
c) Σ1𝑗 ∈𝑆 = 1 + 1 + 1 = 3
6) [8 marks] Find the solution to each of these recurrence relations with the given initial conditions. Use an iterative approach.
a) an = -an-1 , a0 = 5
a0 = 5
a1 = -5
a2 = 5
a3 = -5
a4 = 5
a5 = -5
we can see that the values are changing between 5 and -5. One possibility is:
an = (-1n) × 5
b) an = an-1 + 3 , a0 = 1
a0 = 1
a1 = (1) + 3 = 1 + 3 = 1 + (1×3)
a2 = (1 + 3) + 3 = 1 + 3 + 3 = 1 + (2×3)
a3 = (1 + 3 + 3) + 3 = 1 + 3 + 3 + 3 = 1 + (3×3)
a4 = (1 + 3 + 3 + 3) + 3 = 1 + 3 + 3 + 3 + 3 = 1 + (4×3)
a5 = (1 + 3 + 3 + 3 + 3) + 3 = 1 + 3 + 3 + 3 + 3 + 3 = 1 + (5×3)
we can see the following solution fits the recurrence relation:
an = 1 + (n×3)