The University of New South Wales
Final Exam
Session 2, 2014
COMP9020
Foundations of Computer Science
Time allowed: 2 hours
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, ` ∈ N with f ≤ `, devise a formula leap(f, `) that expresses the exact number of leap
years in the interval [f, `] using at most the two arguments f and ` as well as the arithmetic
operations floor, addition, subtraction, and division.
Example: applying the formula to f = 1896 and ` = 2004 should yield leap(1896, 2004) = 27.
Answer:
b`/4c − b(f − 1)/4c divisible by 4
− b`/100c − b(f − 1)/100c divisible by 100
+ b`/400c − b(f − 1)/400c divisible by 400
Question 2 (5 marks)
Prove that
∑n
i=0 k
i = k
n+1−1
k−1 for all n, k ∈ N with k > 1.
Answer: by induction on n. Base case
∑0
i=0 k
i = 1 = k−1
k−1 =
k0+1−1
k−1 . Inductive case
n+1∑
i=0
ki = kn+1 +
n∑
i=0
ki
= kn+1 +
kn+1 − 1
k − 1 by the ind. hyp.
=
(k − 1)kn+1 + kn+1 − 1
k − 1
=
kn+2 − 1
k − 1 .
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 } ,v) defined on the positive divisors of 45 by
x v 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
1
3 5
9 15
45
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) = n
3 f2(n) = n
5
f3(n) =
{
n3 if n is odd
n5 otherwise
f4(n) =
{
n3 if n is prime
n5 otherwise
and determine whether
(a) f1(n) is O(f2(n)),
(b) f2(n) is O(f3(n)),
(c) f4(n) is O(f3(n)).
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.
Answer:
(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) = m
5 ≥ 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) = m
5 ≥ m3c = cf3(m).
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 (
n
2
) + 4n3 + 3n2 + 2n+ 1 (2)
T (n) = 2T (
n
2
) + 4n2 + 3n+ 2 (3)
Answer: by the master theorem:
(a) O(2n)
(b) O(n3 log n)
(c) O(n2)
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)?
Answer:
(a) remove Y from the first and 56789 from the second word to arrive at SYDNE and 0123456789.
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. Since p < q, (2− p)pq > (2− q)pq.
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 · 1
4
· 50− 1 · 3
4
· 50 = 25− 37.5 = −12.5























































































































































































学霸联盟