Student Name:
Student Number:
Signature:
University of Wales
Copyright By PowCoder代写 加微信 powcoder
School of Computer Science and Engineering Foundations of Computer Science (COMP9020) FINAL EXAM — Session 1, 2017
This paper must be submitted and cannot be retained by the student
Instructions:
• Ensure you enter your correct name and student number above!
• This exam paper contains 10 multiple-choice questions (pages 1-3) plus 5 open questions (pages 4-8).
Each multiple-choice question is worth 4 marks (10 ⇥ 4 = 40).
Each open question is worth 12 marks (5 ⇥ 12 = 60).
Total exam marks = 100.
• Only use a blue or black pen. All answers must be recorded in this paper.
• For the multiple-choice questions, tick one box for your answer directly (each multiple-choice question has only one correct answer).
To make a correction, tick all boxes, then circle one box for your answer.
• Fortheopenquestions,writeyouranswerinthespaceprovided(ifyouneed more space, you can write on the back of the sheet).
• A separate white booklet is provided for scratch work only. Do not write your answers in the Examination Answer Book, it will not be marked.
• Time allowed – 120 minutes + 10 minutes reading time.
• The exam is closed book. Reference materials are not allowed, apart from
one A4-sized sheet (double-sided is ok) of your own notes.
• Number of pages in this exam paper: 8 (in addition to this cover sheet).
1. How many integers in the interval [ 100, 100] are divisible by 5 or 7 (or both)?
⇤64 I⇥⇤ 65
⇤ N = 2·(b100/5c+b100/7c b100/35c)+1 = 2·(20+14 2)+1 = 65
2. Consider the alphabets ⌃ = {s, e, a} and intheset{!2(⌃\ )⇤: length(!)2}?
3. Which of the following is not a correct equivalence?
⇥⇤¬A_B ⌘ ¬(B^¬A) ⇤A^¬B ⌘ ¬(B_¬A) ⇤A)¬B ⌘ B)¬A ⇤¬(A)B) ⌘ ¬B^A
4. Consider the functions f : N ! {0,1,2} and g : {0,1,2} ! {0,1,2}
= {a, r, t}. How many words are
defined by
Which of the following statements is true?
⇥⇤ g g = Id{0, 1, 2}
⇤ f gisnotonto ⇤g f isnotonto
f(x) = xmod3 g(x) = |x 2|
5. Consider the partial order on S = {1, 2, 3, 4, 6, 12} defined by
x y if and only if x | y Which of the following is not true?
⇤ lub({1, 4, 6}) = 12 ⇥⇤ glb({4, 6, 12}) = 1
⇤ correct is glb({4, 6, 12}) = 2
(S , ) is a lattice
1 < 3 < 2 < 6 < 4 < 12 is a topological sort of (S , )
6. All connected graphs with n vertices and k edges satisfy
(i.e., x is a divisor of y)
⇥⇤ I n k + 1
a tree has k + 1 vertices
7. We would like to prove that P(n) for all n 0.
Which of the following conditions imply this conclusion?
⇤ P(0) and 8n 1 (P(n) ) P(n + 1))
⇤ P(0) and P(1) and 8n 1 (P(n) ^ P(n + 1) ) P(n + 2))
⇥⇤ P(0) and P(1) and 8n 0 (P(n) ^ P(n + 1) ) P(n + 2)) ⇤True
P(0) and P(1) and 8n 1 (P(n) ) P(n + 2))
8. ConsidertherecurrencegivenbyT(1)=1andT(n)=4·T(n2)+n. This has order of magnitude
O(n·logn) 2
⇤ master theorem
9. Let S = {1,2,3} and B = {0,1}.
How many di↵erent onto functions f : S ! B are there?
⇥⇤ 23 2 = 6 since there are |B||S | = 23 functions in total, and two of them
⇤arenotonto: f1 :s7!0and f2 :s7!1
10. Which of the following is true for all A, B?
⇥⇤ P(A \ B|B) = P(A|B)
⇤ P(A \ B) = P(B) · P(B|A)
⇤ P(A [ B) P(A) + P(B)
⇤ P(A|B) + P(A|B ̄) = 1
11. Consider the following two formulae:
= ¬(A)(B^C))
(a) Transform into disjunctive normal form (DNF).
(b) Prove that , |= ¬B (i.e., ¬B is a logical consequence of and ). (c) Is _ a tautology (i.e., always true)? Explain your answer.
(a)A+BC = A·BC = A·(B+C) = AB+AC (b) From it follows that ¬(A ^ ¬C).
From (a) it then follows that A ^ ¬B, which implies ¬B. Alternative solution using a truth table:
TTTFTF Case 1: A is false or C is true. Then is true.
Case 2: Case 1 is false, then A ^ ¬C, hence is true according to (a). Alternative solution extends the truth table from above by _ .
is always true:
12. Prove that for all binary relations R1 ✓ S ⇥ S and R2 ✓ S ⇥ S the following holds:
If R1 and R2 are symmetric, then R1 \ R2 is symmetric.
If(x,y)2R1 \R2 then(x,y)2R1 and(x,y)