# CS代考 COMP9020) FINAL EXAM — Session 1, 2017 – cscodehelp代写

Student Name:
Student Number:
Signature:
University of Wales

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)?
⇤ N = 2·(b100/5c+b100/7cb100/35c)+1 = 2·(20+142)+1 = 65
2. Consider the alphabets ⌃ = {s, e, a} and intheset{!2(⌃ )⇤: length(!)2}?
= {a, r, t}. How many words are
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}
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) = |x2|

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 ⇥⇤ 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)) (i.e., x is a divisor of y) 8. ConsidertherecurrencegivenbyT(1)=1andT(n)=4·T(n2)+n. This has order of magnitude ⇤ O(n) ⇤O(n·logn) ⇤ 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: ABC ¬B FFFFTT FFTFTT FTFFTF FTTFTF TFFTFT TFTTTT TTFTFF 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)CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com