xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

离散数学代写-COMP9020

时间：2021-04-23

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

学霸联盟

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

学霸联盟