Name: _______________________________, ___________________________________
(Last name)
Student ID#: __________________________________
Section: E
York University
Department of Electrical Engineering & Computer Science Lassonde School of Engineering
EECS 2001 E Quiz 1 (Version A) May 17, 2019
(First name)
Instructor: Ali Mahmoodi
Guidelines and Instructions:
1. This is a 60-minute, closed-book test.
2. This exam paper has 4 pages (including this page) and 7 questions.
3. Print your name and write down your student number clearly.
4. If you need more space to write your answer use the back of the page but clearly indicate
which question you are answering.
5. You may not leave within the first and last 10 minutes of the exam. Remain seated until all exams are collected.
Question 1
/3
Question 2
/4
Question 3
/4
Question 4
/4
Question 5
/4
Question 6
/5
Question 7
/6
Total
/33
EECS 2001 Quiz 1 – Summer 2019 Section E
Question1.[3marks]Let𝐴 = {𝑛 |1 ≤ 𝑛 ≤ 15,𝑎𝑛𝑑𝑛 = 5𝑘𝑓𝑜𝑟𝑠𝑜𝑚𝑒𝑘 ∈ 𝑁}and𝐵 = {𝑎,𝑏}.Givean explicit listing of
a) 𝐴∪𝐵
A = {5, 10, 15}, B = {a, b} => 𝐴 ∪ 𝐵 = {5, 10, 15, a, b} (1 mark for the correct answer)
b) 𝐴 × 𝐵 = {(5, a), (5, b), (10, a), (10, b), (15, a), (15, b)} (1 mark for the correct answer)
c) Power set of B = { ∅, {a}, {b}, {a, b}} (1 mark for the correct answer)
Question 2. [4 marks] Are the following statements true or false? Assume the domain of x and y is the set of integers. Briefly explain your answer.
a) ∀𝑥∃𝑦 𝑥 + 𝑦 = 5
True! For any x, there is y = 5 -x which satisfies the equation. (1 mark for true and 1 for the correct explanation)
b) ∃𝑦∀𝑥𝑥∙𝑦=𝑥
True! Let y =1, then for any x we have x.y = x (1 mark for true and 1 for the correct explanation)
Question 3. [4 marks] show that ¬(¬p ↔ (r ˅ p)) is logically equivalent to 𝑟 → 𝑝 One can use a truth table (1 mark for each correct row)
r
p
¬(¬p ↔ (r ˅p))
𝑟→𝑝
T
T
¬(¬T↔ (T ˅T)) =¬(F↔ T) =T
T
F
F
¬(¬F↔ (F ˅F)) =¬(T↔ F) =T
T
F
T
¬(¬T↔ (F ˅T)) = ¬(F↔ T) =T
T
T
F
¬(¬F ↔ (T ˅ F)) = ¬(T ↔ T ) = F
F
Page2of4
EECS 2001 Quiz 1 – Summer 2019 Section E Question 4. [4 marks] A palindrome is a string that reads the same forward as backward, like “madam”.
Give a recursive definition of the set of all palindromes P over an alphabet Σ.
Set of all palindromes P over an alphabet Σ can be defined as
1) ε P; a , a P
2) a xP,axaP 3) No other string is in P
(1 mark for the correct base case: line 1, 2 marks for recursion: line 2, and 1 for line 3).
Question 5. [4 marks] Prove that for any simple undirected graph G the sum of the degrees of all nodes in G is even.
See Theorem 0.21 of the Text: Every edge in G is connected to two nodes. Each edge contributes 1 to the degree of each node at its end points. Therefore each node contributes 2 to the total sum. Hence if G contains e edges, then the sum of all degrees is 2e implying it is even.
(The key is to notice that each edge contributes 2 to the sum. Deduct marks for any incorrect reasoning or hole in the proof.)
Question 6. [5 marks] Prove that log2 3 is irrational.
Assume log2 3 is rational. This implies log2 3 = 𝑝/𝑞 for some positive integers p and q. But log2 3 = 𝑝/𝑞 implies q log2 3 = 𝑝 which implies log2 3𝑞 = 𝑝. By definition of log we have 2𝑝 = 3𝑞. But this is impossible since left side is even and right side is odd. Therefore log2 3 cannot be rational.
(This is done by contradiction. Give 0 for any attempt by induction. Give partial mark ( <= 3) if they attempt proof by contradiction, but cannot make it work. Full mark only if they can arrive correctly at the contradiction).
Page3of4
EECS 2001 Quiz 1 – Summer 2019 Section E
Question 7. [6 marks] Use induction to prove that any natural number n, 𝑛 ≥ 12, can be written as 𝑛 = 4𝑎 + 5𝑏 where a and b are from the set of non-negative integers (i.e. natural numbers with 0 included).
Let P(n) be the statement that a natural number 𝑛 ≥ 12, can be written as 𝑛 = 4𝑎 + 5𝑏. Base case: P(12) is true since 12 = 4 × 3 + 5 × 0.
Induction hypothesis: Assume P(n) is true for some natural number 𝑛 ≥ 12. That means we can write 𝑛 = 4𝑎 + 5𝑏 for non-negative integers a and b.
Induction step: we show 𝑃(𝑛) → 𝑃(𝑛 + 1). By induction hypothesis we can write 𝑛 + 1 = 4𝑎 + 5𝑏 +1. Now there are two cases: a) either a > 0, or b) a = 0.
Case a) a >0: then we can write 𝑛 + 1 = 4𝑎 + 5𝑏 + 1 = 4(𝑎 − 1) + 5(𝑏 + 1). Note that both (a-1) and (b+1) are non-negative integers.
Caseb) a=0.Inthiscasesince𝑛 ≥ 12wemusthave𝑏 ≥ 3. Thenwecanwrite𝑛 + 1 =4𝑎 + 5𝑏 + 1 = 4𝑎 + 5(𝑏 − 3) + 15 + 1 = 4𝑎 + 5(𝑏 − 3) + 4 × 4 = 4(𝑎 + 4) + 5(𝑏 − 3). Here also both (b-3) and (a+4) are non-negative integers and we are done.
(2 marks for the base case and 2 marks each for the induction step cases. Give partial marks depending on the correctness of the arguments)
Page4of4