CPS420
MIDTERM 1 SOLUTIONS
W2019
PART
1.
A – GRAPH THEORY
Committee Overlaps
Academic
Competitions
Executive
Nanh Taz
Zixuan
Social
Outreach
Finance
Note that it was not necessary to label the edges to answer this question. They are labelled here to explain the answer.
2. Committee Meetings
This question has more than one correct answer. One possible answer is shown in the graph below:
W: Academic
M:Competitions
3. Modified Committee Overlaps
M: Executive
W: Social
F: Outreach
F: Finance
The two red lines should be added to the above graph (again edge labels are shown here to explain)
Academic
Competitions
Executive
Social
Outreach
Finance
4. Cliques
a) 3-cliques: {E,A,F}, {E,S,F}, {E, C, F}, {E, C, S}, {C,F,S} b) 4-cliques: {E, C, F, S}
1
CPS420 MIDTERM 1 SOLUTIONS W2019
5. Further Thoughts
Would it now be possible to schedule meetings for all of these committees in the three available time slots in such a way that all the student reps could attend all the meetings of the committees on which they are serving?
No because the graph contains a 4-clique. Adjacent vertices need to be scheduled on different days, and in the 4-clique each of the 4 vertices is adjacent to the other 3, so 4 different days are needed for the 4 committees in the 4-clique.
PART B – SEQUENCES, RECURRENCE RELATIONS
Given the sequence an defined with the recurrence relation:
a0 = 2
ak = 4k + ak-1 + 2 for k 1 1. Terms of the Sequence
a1 = 4×1 + a0 +2 = 4×1 + 2 + 2 = 4×1 + 2×2 = 8
a2 = 4×2 + a1 +2 = 4×2 + (4×1 + 2×2) + 2 = 4×2 + 4×1 + 3×2 = 18
a3 = 4×3 + a2 +2 = 4×3 + (4×2 + 4×1 + 3×2) + 2 = 4×3 + 4×2 + 4×1 + 4×2 = 32
a4 = 4×4 + a3 +2 = 4×4 + (4×3 + 4×2 + 4×1 + 4×2) + 2 = 4×4 + 4×3 + 4×2 + 4×1 +
5×2 = 50
2. Iteration
Using iteration, solve the recurrence relation when n0 (i.e. find an analytic formula for an). Simplify your answer as much as possible, showing your work. In particular, your final answer should not contain sums ( ) and products ( )
an = 4 × ∑𝑛 𝑖 + 2(𝑛 + 1) = 4n(n+1)/2 + 2(n+1) = 2(n+1)2 𝑖=1
2
CPS420 MIDTERM 1 SOLUTIONS
W2019
PART C – INDUCTION
1. Set D
D=N+
2. P(n)
P(n) is: 4n mod 10 = 4 ∨ 4n mod 10 = 6 3. Basic Step of the Proof
When n=1 4n mod 10 = 4 mod 10 = 4, so P(1) is true When n=2 4n mod 10 = 16 mod 10 = 6, so P(2) is true
4. Inductive Step of the Proof
Assume that some positive integer k is such that P(m) is true for all mk
i.e. m{1, …, k} 4m mod 10 = 4 ∨ 4m mod 10 = 6 (Inductive Hypothesis) We will now show that P(k+1) is true, i.e. 4k+1 mod 10 = 4 ∨ 4k+1 mod 10 = 6
4k+1= 4×4k
By Inductive Hypothesis P(k) is true, i.e. 4k mod 10 = 4 ∨ 4k mod 10 = 6
Case 1: 4k mod 10 = 4
this means aN 4k = 10a + 4
so 4k+1= 4×4k = 4(10a + 4) = 40a +16 = 10(4a+1) + 6 i.e. 4k+1 mod 10 = 6
Case 2: 4k mod 10 = 6
this means aN 4k = 10a + 6
so 4k+1= 4×4k = 4(10a + 6) = 40a +24 = 10(4a+2) + 4 i.e. 4k+1 mod 10 = 4
So 4k+1 mod 10 = 6 ∨ 4k+1 mod 10 = 4
i.e. P(k+1) QED
3