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

Student Name:

Student Number:

Signature:

University of Wales

Copyright By cscodehelp代写 加微信 cscodehelp

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)