Foundations of Computer Science (COMP9020) FINAL EXAM — Session 1, 2017
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Foundations of Computer Science (COMP9020)
FINAL EXAM — Session 1, 2017
1. How many integers in the interval [一100, 100] are divisible by 5 or 7 (or both)?
口 64
65
N = 2 . (「100/51 +「100/71 一「100/351) + 1 = 2 . (20 + 14 一 2) + 1 = 65 口 67
口 68
2. Consider the alphabets x = {s, e, a} and v = {a, r, t}. How many words are in the set {o e (x / v)* : length(o) < 2} ?
口 2
口 4
口 6
7
3. Which of the following is not a correct equivalence?
-A ^ B 三 -(B V -A)
口 A V -B 三 -(B ^ -A)
口 A > -B 三 B > -A
口 -(A > B) 三 -B V A
4. Consider the functions f : N 一一 {0, 1, 2} and g : {0, 1, 2} 一一 {0, 1, 2} defined by
f (x) = x mod 3
g(x) = |x 一 2|
Which of the following statements is true?
口 f o f ≠ f
g o g = Id{0, 1, 2}
口 f o g is not onto
口 g o f is not onto
5. Consider the partial order < on S = (1, 2, 3, 4, 6, 12) defined by
x < y if and only if x l y (i.e., x is a divisor of 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 2 k + 1
口 n 2 k
口 n < k
n < k + 1
a tree has k + 1 vertices
7. We would like to prove that P(n) for all n 2 0.
Which of the following conditions imply this conclusion?
口
口
口
P(0) and Vn 2 1 (P(n) = P(n + 1))
P(0) and P(1) and Vn 2 1 (P(n) A P(n + 1) = P(n + 2))
P(0) and P(1) and Vn 2 0 (P(n) A P(n + 1) = P(n + 2))
True
P(0) and P(1) and Vn 2 1 (P(n) = P(n + 2))
8. Consider the recurrence given by T(1) = 1 and T(n) = 4 . T( 
) + n. This has order of magnitude
口 O(n)
口 O(n . log n)
O(n2)
master theorem
口 O(2n)
9. Let S = (1, 2, 3) and B = (0, 1) .
How many diferent onto functions f : S -- B are there?
口 0
口 口
6
23 - 2 = 6 since there are lBllS l = 23 functions in total, and two of them are not onto: f1 : s l- 0 and f2 : s l- 1
8
9
10. Which of the following is true for all A, B?
P(A n BlB) = P(AlB)
口 P(A n B) = P(B) . P(BlA)
口 P(A u B) 2 P(A) + P(B)
口 P(AlB) + P(Al
) = 1
Consider the following two formulae:
6 = -(A = (B A C))
w = -A v C
(a) Transform 6 into disjunctive normal form (DNF).
(b) Prove that 6, w l= -B (i.e., -B is a logical consequence of 6 and w).
(c) Is 6 v w a tautology (i.e., always true)? Explain your answer.
|
(b) From w it follows that -(A A -C). From (a) it then follows that A A -B, which implies -B. Alternative solution using a truth table:
(c) 6 v w is always true: Case 1: A is false or C is true. Then w is true. Case 2: Case 1 is false, then A A -C, hence 6 is true according to (a). Alternative solution extends the truth table from above by 6 v w. |
||||||||||||||
Prove that for all binary relations R1 c S x S and R2 c S x S the following holds:
If R1 and R2 are symmetric, then R1 / R2 is symmetric.
|
If (x, y) e R1 / R2 then (x, y) e R1 and (x, y) : R2 . By symmetry of R1 and R2 it follows that (y, x) e R1 and (y, x) : R2 . Hence, (y, x) e R1 / R2 . Alternative proof by contradiction: If R1 / R2 is not symmetric, then there exist x, y e S such that (x, y) e R1 and (x, y) : R2 but (y, x) : R1 / R2 . From (y, x) : R1 / R2 it follows that (y, x) : R1 or (y, x) e R2 . But (y, x) : R1 contradicts (x, y) e R1 given that R1 is symmetric, and (y, x) e R2 contradicts (x, y) : R2 given that R2 is symmetric. |
The Fibonacci numbers are defined as follows:
F1 = 1; F2 = 1; Fi = Fi- 1 + Fi-2 for i 2 3
Write a proof by induction for the statement that every third Fibonacci num- ber (that is, F3 , F6 , F9 , . . .) is even (i.e., divisible by 2).
|
Base case n = 3: F1 = 1; F2 = 1; F3 = 2. Hence, 2 l F3 . Inductive step n -- n + 3: By definition, Fn+3 = Fn+2 + Fn+1 = (Fn+1 + Fn ) + Fn+1 = 2 . Fn+1 + Fn From the induction hypothesis 2 l Fn it follows that 2 l (2Fn+1 + Fn ). |
Consider the following graph G :
d
c
(a) Give all 3-cliques of G.
(b) What is the chromatic number x(G) of G? Explain your answer.
(c) What is the maximal number of edges that can be added to G such that G remains planar? Explain your answer.
|
(a) {a,b,c}, {a,b,d} (b) x(G) = 3. 3 colours are necessary because G contains a 3-clique. 3 colours are also su伍cient:
(c) A maximum of 2 edges can be added, for example:
3 edges cannot be added since this would result in K5 , which is not planar. |
15. Consider a deck of six cards containing 2 jacks and 4 aces. One card is randomly drawn from the deck at a time. Calculate the expected number of drawing attempts until an ace is drawn:
(a) if the cards are put back into the deck after each drawing;
(b) if the cards are not put back into the deck after each drawing.
Briefly explain your answers.
|
(a) Each drawing event has the probability p =
(b) 1 . |
2023-05-04