Key Concepts in Computer Science -Midterm 2

[Proofs]
1. [10 marks]
a) Prove using the rules of inference that the premises p –> q, -p –> r, r –> s imply the conclusion

-q –> s.
Ans:
1. p –> q Premise
2 -q –> -p Contrapositive of (1)
3 -p –> r Premise
4 -q –> r Hypothetical Syllogism using (2) and (3)
5. r –> s Premise
6. -q –> s  Hypothetical Syllogism using (4) and (5)
b) Use rules of inference to show that the hypotheses (-r v -f)–> ( s ^ q ) and s–> t and -t implies r.
Ans:
1. -t Premise
2. s–> t Premise
3. -s Modus Tollens using (1) and (2)
4. (-r  v -f)–> ( s ^ q ) Premise
5. – ( s ^ q ) –> – (-r v -f) Contrapositive of (4)
6. (-s v  -q)–>( r ^ f ) De Morgan’s law and double negation
7. -s  v -q Addition using (3)
8. r ^ f Modus Ponens using (6) and (7)
9. r Simplification using (8).

2. [10 marks] Use Proof by cases to show that if n is an integer then n2 ≥ n.
Ans:
Case 1: n ≥ 0  n2 ≥ n (this is true for all integers larger than or equal to zero)
Case 2: n < 0 n2 < n (this is true because n2 is always positive while we assume n is negative)
3. [10 marks] Prove that there is no positive integer n such that n2 + n4 = 200.
Ans:
The only possible solutions to the equation would require n4  200 since n2 and n4 are positive. So
possible values of |n|  3. Also from the equation n2(n2+1) = 200. If |n|  3 then n2(n2+1)  32(32+1)
= 90 is too small. So there is no solution.
[Sets and Set Operations]
4. [10 marks] Find the truth set of each of these predicates where the domain is the set of integers.
a) Q(x) : x2 < 4
Ans: The truth set is {-1, 0, 1}
b) R(x) : 2x < x2
Ans: The truth set is all negative numbers: { … , -3 , -2 , -1}

[Functions]
6. [10 marks] Determine whether each of these functions from Z to Z is one-to-one (i.e., injective) or
onto (i.e., surjective) or both. Justify your answer.
a) f(n) = n4 – 1
Ans: It is not one-to-one. For example, 1 and -1 are both mapped to 0.
It is not onto. For example, there is no integer to be mapped to 1. (there is
no integer n in which n4 =2)
b) f(n) = ⌈
𝒏
𝟑
⌉
Ans: It is not one-to-one. For example, 3 and 4 are both mapped to 1.
It is onto. For any m in the codomain, 3m from domain is mapped to it.
7. [10 marks] Find f∘ g and g∘ f, where f(x) = 2×2+1 and g(x) = 𝟏√𝒙 , are functions from R to R.
f∘ g(x) = 𝟐(𝟏√𝒙𝟐)+𝟏 = 𝟐𝒙+𝟏
g∘ f(x) = 𝟏√𝟐𝒙𝟐+𝟏
[Sequences and Summations]
8. [10 marks] Consider the following sequences. What is a3?
a) an = 3×2𝑎𝑛−1 a1 = 1
[Note: 2𝑎𝑛−1 is 2 to the power of 𝑎𝑛−1]
a2 = 3×21 = 6
a3 = 3×26 = 192
b) an = ⌈𝑎𝑛−122⌉ a1 = 3
a2 = ⌈322⌉ = 5
a3 = ⌈522⌉ = 13
9. [10 marks] Find the solution to each of these recurrence relations with the given initial conditions. Use an iterative approach.
a) an = an-1 + 4 a0 = 2
a0 = 2
a1 = (2) + 4 = 2 + 4 = 2 + (1×3)
a2 = (2 + 4) + 4 = 2 + 4 + 4 = 2 + (2×4)
we can see the following solution fits the recurrence relation:
an = 2 + (n×4)
b) an = 3an-1 + 1 a0 = 1
if you write the value of the first few sequences, you will see the following relation.
𝒂𝒏= 𝟑𝒏+𝟏− 𝟏𝟑−𝟏 = 𝟑𝒏+𝟏− 𝟏𝟐
10. [10 marks] What are the values of these sums:
a) Σ(−2)𝑖6
𝑖=2 =
(-22) + (-23) + (-24) + (-25) + (-26) = 4 – 8 + 16 – 32 + 64 = 44
b) ΣΣ(𝑖22𝑗=02𝑖=0𝑗2) =
0202 + 0212 + 0222 + 1202 + 1212 + 1222 + 2202 + 2212 + 2222 = 0 + 0 + 0 + 0 + 1 + 4 + 0 + 4 + 16 = 25
[Algorithms]
11. [10 marks] Apply greedy algorithm to make change using coins with the following three coins:
a) C1: 20 cents (coin C1 has 20 cents value)
b) C2: 7 cents (coin C2 has 7 cents value)
c) C3: 1 cent (coin C3 has 1 cent value)
a) 56 cents
56 = 2.20 + 16
16 = 2.7 + 2
2 = 2.1
We need 2 C1, 2 C2 and 2 C3
b) 23 cents
23 = 1.20 + 3
3 = 3.1
We need 1 C1, 0 C2 and 3 C3
12. [10 marks] Give pseudocode for an algorithm that takes a list of n integers (n ≥ 1) and returns the location of the last even integer in the list, or returns 0 if there are no even integers in the list.
procedure lasteven(a1,…,an: integers)
For example, if the input is 7, 2, -4, 3, 9, -18, 21 the last even integer is at location 6.
procedure lasteven(a1,…,an: integers)
answer : = 0
for i : = 1 to n
if ai is even
then answer : = i
return answer