The University of Wales
Final Exam Session 2, 2014
COMP9020 Foundations of Computer Science
Time allowed: 2 hours
Copyright By PowCoder代写 加微信 powcoder
Total number of questions: 10 Maximum number of marks: 50
Not all questions are worth the same. Answer all questions.
Textbooks, lecture notes, etc. are not permitted, except for up to 2 double-sided A4 sheets containing handwritten notes.
Calculators may not be used.
Answers must be written in ink. Use a pencil or the back of the booklet for rough work. Your rough work will not be marked.
You can answer the questions in any order.
You may take this question paper out of the exam. Write your answers into the answer booklet provided.
Question 1 (5 marks)
A leap year is a year containing one additional day. Nowadays, that day, the 29th of February, is added on every year divisible by 4, unless it is also divisible by 100 but not by 400. For instance, the years 2000 and 2004 were leap years but 1900 was not.
For the purpose of this question let us pretend that this rule has always been followed since the year 0 and will always be followed.
For f,l ∈ N with f ≤ l, devise a formula leap(f,l) that expresses the exact number of leap years in the interval [f,l] using at most the two arguments f and l as well as the arithmetic operations floor, addition, subtraction, and division.
Example: applying the formula to f = 1896 and l = 2004 should yield leap(1896, 2004) = 27. Answer:
⌊l/4⌋ − ⌊(f − 1)/4⌋
− ⌊l/100⌋ − ⌊(f − 1)/100⌋ + ⌊l/400⌋ − ⌊(f − 1)/400⌋
Question 2 (5 marks)
Provethatn ki =kn+1−1 foralln,k∈Nwithk>1. i=0 k−1
divisible by 4 divisible by 100 divisible by 400
by induction on n. Base case 0 i=0
n+1 n ki = kn+1 + ki
= kn+1 + kn+1 −1 k−1
= (k−1)kn+1 +kn+1 −1 k−1
=kn+2−1 . k−1
ki = 1 = k−1 = k0+1−1. Inductive case
by the ind. hyp.
Question 3 (4 marks)
Prove that (S ∩ T) × (U ∩ V ) = (S × U) ∩ (T × V ) holds for all sets S, T, U, and V . Answer: the claimed equality holds.
(s, u) ∈ (S ∩ T ) × (U ∩ V ) ⇔ s ∈ (S ∩ T ) ∧ u ∈ (U ∩ V ) ⇔s∈S∧s∈T∧u∈U∧u∈V ⇔s∈S∧u∈U∧s∈T∧u∈V
⇔ (s, u) ∈ S × U ∧ (s, u) ∈ T × V ⇔ (s, u) ∈ (S × U ) ∩ (T × V )
Question 4 (5 marks)
Consider the partial order D45 = ({ x ∈ P : x|45 } , ⊑) defined on the positive divisors of 45 by x ⊑ y iff x|y. Give 3 different topological sorts of D45.
Answer: 45 = 3 · 3 · 5 with positive divisor set {1, 3, 5, 9, 15, 45}. We can arrange this in a Hasse diagram
and read off the topological sorts:
⟨1,3,5,9,15,45⟩ ⟨1,5,3,9,15,45⟩ ⟨1,3,5,15,9,45⟩ ⟨1,5,3,15,9,45⟩ ⟨1,5,3,9,15,45⟩ ⟨1,3,9,5,15,45⟩
Question 5 (6 marks)
Consider the four functions f1(n) = n3
n3 f3(n) = n5
and determine whether (a) f1(n) is O(f2(n)), (b) f2(n) is O(f3(n)), (c) f4(n) is O(f3(n)).
if n is odd otherwise
f2(n) = n5
n3 if n is prime
For each of the three parts, either give values n0 and c that prove the big-oh relationship, or assume that there are such values n0 and c, and then derive a contradiction.
(1, 2): f1 is O(f2). Constants n0 = 0 and c = 1 work as witnesses.
(2,3): f2 is not O(f3). Suppose otherwise for constants n0 and c. Consider the smallest odd
number m at least max(n0 + 1, √c). Then f2(m) = m5 ≥ m3c = cf3(m).
(4,3): f4 is not O(f3). Suppose otherwise for constants n0 and c. Consider the smallest composite number m at least max(n0 + 1, √c). Then f4(m) = m5 ≥ m3c = cf3(m).
f4(n) = n5 otherwise
Question 6 (6 marks)
For each of the following recurrences, what is T (n)’s order of growth? T(n)=2T(n−1)+4n2 +3n+2 (1)
T(n)=8T(n2)+4n3 +3n2 +2n+1 (2) T(n)=2T(n2)+4n2 +3n+2 (3)
Answer: by the master theorem: (a) O(2n)
(b) O(n3 log n)
Question 7 (5 marks)
Suppose license plates are constructed using three letters picked (without replacement) from the word SYDNEY followed by two decimal digits picked (again without replacement) from the word 012345566778899.
(a) How many license plates can be constructed if the letters and digits have to be different (e.g. DYS54 is allowed but YSY54 is not because Y occurs twice),
(b) How many license plates can be constructed if the letters and digits need not be different (e.g. YSY54 is allowed and so is END55 but not SDD64)?
(a) removeYfromthefirstand56789fromthesecondwordtoarriveatSYDNEand0123456789. Choosing three different letters from the first = 5 · 4 · 3 = 60 possibilities. Choosing two from the second word = 10 · 9 = 90 possibilites. Together that’s 60 ∗ 90 = 5400 different license plates.
(b) We start with 60 choices as before for the three letters from the first word where all letters are different. To those we add the ones containing two Ys. There are 4 other letters and 3 positions for the other letter = 12 different words with two Ys. The two numbers can be chosen from 10 digits so that’s 102 = 100 possibilites. But we’ve accounted for certain combinations that we cannot have—the combinations of the form dd for d ∈ {0, 1, 2, 3, 4}. There are 5 of those. Altogether we have (60 + 12) · (100 − 5) = 6840.
Question 8 (5 marks)
Let Gk be a graph on k vertices, consisting of a cycle of k − 1 vertices plus a central node connected to all vertices on the cycle. Given k > 3, what is the chromatic number of Gk?
Answer: χ(Gk) ∈ {3,4}: the cycle may be odd or even, needing 2 or 3 colours, the central node takes one more.
Question 9 (5 marks)
You have applied to join a chess club and been told that to qualify you must play three games against X, winning two games in a row. In other words, the sequences “WWL” (for “win,win,loss”), “WWW”, and “LWW” will get you qualified whereas “WLW” and anything with fewer than two wins will not get you qualified.
“Who gets the white pieces?” you ask and are told you and X alternate and you can choose whether to start the first game with white or with black.
Knowing that the probability of beating X is better with the white pieces (first-move advantage) should you choose white or black for the first game?
Use 0 < Pb < Pw < 1 for the probability of winning when playing with the black, respectively, white pieces to model the problem and prove your answer correct.
Answer: I should choose to start with black. Let p, q ∈ (0, 1) be the probability of me winning with black and white, respectively, so p < q. The probability of winning two games in a row when starting the first game with black is the sum of the probabilities of winning the first two, the last two, or all three games: pq(1−p)+(1−p)qp+pqp = (2(1−p)+p)pq = (2−p)pq whereas the same calculation for beginning with white results in qp(1 − q) + (1 − q)pq + qpq = (2(1−q)+q)qp=(2−q)qp. Sincep
Question 10 (4 marks)
Suppose you are taking an exam consisting of 50 multiple choice questions. Each question has four possible answers exactly one of which is correct. A correct answer scores 2, an incorrect answer scores −1 and blank scores 0. You did not study at all, and decide to randomly guess all the answers and leave no blanks. What should you expect to score in the exam? Derive the correct answer to this question mathematically.
Answer: 2·41 ·50−1·43 ·50=25−37.5=−12.5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com