代写COMPSCI 120 COMPUTER SCIENCE代做留学生SQL语言
VERSION 1
Question/Answer Booklet
ID#: COMPSCI 120
THE UNIVERSITY OF AUCKLAND
SECOND SEMESTER 2020
Campus: City
COMPUTER SCIENCE >Mathematics for Computer Science
(Time allowed: TWO hours)
Write your first name here:
Write your last name here:
Write your UPI here:
Write your ID# here:
NOTE:
This exam will begin with 10 minutes of reading time. You may not write anything
in this time.
There are 15 problems, on pages 3 to 15 . The total number of marks is 24 .
Attempt all of the questions; there is no penalty for incorrect answers, and many
problems have partial credit!
There is more than enough space for an answer to every problem in this booklet. If
you find yourself running out of space, this may be a sign that you are overthinking
things!
Show all working, and place all answers in this booklet. For multiple-choice problems,
please circle your answers in this booklet. Do not remove any pages from this booklet!
Pages 16 through 18 of this exam are left blank, to give you additional paper to
work on. They will not be marked.
Best of luck!
Multiple-choice.
Twelve multiple-choice problems are given over the next seven pages. Each problem is
worth one point! No justification is needed for the problems on these pages: just circle the
correct answer.
1. Which of the following statements is TRUE?
(a) 63 % 5 = 34 % 6
(b) For every three natural numbers a, b and n, if a ≡ b mod n, then a%n 6= b%n
(c) For every three natural numbers a, b and n, (a + bn) %n = a%n + b
(d) For every three positive integers a, b and n, (a + b) %n = (a%n + b%n) %n
[1 mark]
2. Which of the following statements is TRUE?
(a) lim
n→∞
n4 + 3n + 2
n5 + 4n + 2
= 1
(b) lim
n→∞
n! + n log5(n) + 10
100
10000n + n5 + 1
= 0
(c) The function f(n) = log2(n) + 2
n grows faster than the function g(n) = n2
(d) The function f(n) = n5 log2(n) + 7 grows faster than the function g(n) = n
6 + 1.
[1 mark]
3. Which of the following statement is TRUE?
(a) The product of two irrational numbers is always an irrational number
(b)
√
2 · √18 is an irrational number
(c) Z ⊆ N
(d) The sum of a rational number and an irrational number is always an irrational number
[1 mark]
4. Two objects are described below. Which of the following statement is TRUE about
these objects?
f : Z→ R, f(x) = x% 3
((x% 3)− 1)2
g : Z→ Z, g(n) =
{
0 when n is odd
1 when n is even
(a) g ◦ g is not defined
(b) The domain of g is {0, 1}
(c) Both f and g are functions
(d) g is a function but f is not
[1 mark]
5. You want to distribute 20 identical candies amongst 4 of your siblings. (It is possible
that after you distribute the candies, one or more of your siblings may not get any
candy at all). What is the probability that after the distribution two of your siblings
get exactly 3 candies?
(a)
(
4
2
) · (15
1
)(
23
3
)
(b)
(
4
2
)(
20
4
)
(c)
(
15
1
)(
23
3
)
(d)
20 · 19 · 18 · 17 · 16 · 15
204
[1 mark]
6. Consider the following algorithm:
Input: A positive natural number m.
(1) Set n = m and s = 0.
(2) If n ≤ 0 then stop.
(3) Otherwise, increase s by 1, update the value of n to be n− s2 and go to Step (2).
Output: s.
Which of the following statements about this algorithm is TRUE?
(a) There is an input value m for which the algorithm does not stop.
(b) For every input value of m, the value stored in n at the end of this algorithm will
be non-negative.
(c) The algorithm outputs 3 if the input is m = 7.
(d) The algorithm goes through Step (2) (dlog2(n)e+ 1) times
[1 mark]
7. Let A be the collection of non-empty prefixes of the string “Aotearoa” and B be the
collection of substrings of even length of the string “Aotearoa”. What is |A|+ |A∩B|?
(a) 13 (b) 11 (c) 12 (d) 14
[1 mark]
8. Which of the following is a negation of the statement “If x is a positive integer, then
there is a real number y such that x = y2 ”?
(a) x is a non-positive integer and there is a real y such that x = y2.
(b) There is a positive integer x, such that x is not equal to y2 for every real number y.
(c) There is a non-positive integer x, such that x is not equal to y2 for every real
number y.
(d) A positive integer x is never equal to y2, for every real number y.
[1 mark]
9. How many distinct 10-character strings can be formed by the rearrangement of
characters of the string “ALGORITHMS”?
(a) 10! (b) 1010 (c)
(
10
1
)
(d) 10!
2!
[1 mark]
10. Which of the following statements about trees is TRUE?
(a) There is a rooted tree on 10 vertices, which has exactly 3 vertices of degree 3, 1
vertex of degree 5, and 8 edges.
(b) A binary tree of height 3 can have at most 15 vertices.
(c) Let u, v and w be vertices of a rooted tree. If u is a child of a child of w and v is
a parent of w, then there is no path from u to v.
(d) A graph with only one vertex is not a tree.
[1 mark]
11. Consider the following claim and its proof: For every positive integer n, there is a
graph on 2n vertices in which all vertices have degree 1.
Proof. Let V = {v1, . . . v2n}. Add in the edges {v1, v2}, {v3, v4}, . . . {v2n−1, v2n}. This
gives us the desired graph, as each vertex in v is in exactly 1 such edge.
Which method is being used to prove the claim?
(a) This is not a proof, it is just an example.
(b) Proof by contradiction
(c) Proof by induction
(d) Proof by construction
[1 mark]
12. Which of the following statements about graphs is TRUE?
(a) Every graph on n vertices with n− 1 edges is connected.
(b) There is a graph on 10 vertices such that 2 vertices have degree 3, 4 vertices have
degree 2, 1 vertex has degree 4, and 3 vertices have degree 5.
(c) There is a graph on 10 vertices such that exactly 2 vertices have degree 1, 4
vertices have degree 3, and 1 vertex has degree 10.
(d) If there is a path from x to y, then there must also be a walk from x to y.
[1 mark]
Arguments.
Problems 13, 14, and 15 on this exam are free-response proof-based problems. For these
problems, it is not enough to just have the right answer: you need to prove that the
statements are correct! With that said, we may give partial marks for attempts at these
problems even if they aren’t fully rigorous proofs. As a result, even if you don’t think you
can come up with a complete argument, do try to explain in your own words what you think
is going on! Describe the definitions that you think are relevant, talk about ideas that you
think might lead to the solution eventually, and otherwise give it your best shot.
13. Let n be a positive integer. Suppose G = (VG, EG) is a graph on n vertices and
T = (VT , ET ) is a tree on n vertices. Find the maximum possible value of |EG|− |ET |.
Explain your answer.
Any tree on n vertices has exactly n − 1 edges. Hence |ET | = n − 1. To find the
maximum of |EG| − (n − 1) you need to find the maximum possible number of
edges in a graph. The maximum number of edges is achieved on a complete graph
where every vertex is adjacent to all other vertices. The degree of every vertex in
a complete graph on n vertices is n− 1. So by the sum-degree formula
(n− 1) + (n− 1) + . . . + (n− 1)︸ ︷︷ ︸
n times
= 2|EG|
n(n− 1) = 2|EG|
Therefore |EG| = n(n− 1)
2
. Finally, the maximum possible value of |EG| − |ET | is
n(n− 1)
2
− (n− 1) = (n− 1)(n− 2)
2
[4 marks]
14. Let n be an integer such that (3n + 6) % 4 = 0. Find (n2 + 2n + 1) % 4. Justify your
claim.
Any integer n can be expressed as n = 4q + r, where q and r are integers
and r = n% 4. Thus, any integer n will have one of the following forms-
4q, 4q + 1, 4q + 2, or 4q + 3 for some q ∈ Z
Case 1: If n = 4q, then 3n+6 = 12q+6. Therefore, (3n+6) % 4 = (12q+6) % 4 =
2.
Case 2: If n = 4q + 1, then 3n + 6 = 12q + 9. Therefore,
(3n + 6) % 4 = (12q + 9) % 4 = 1.
Case 3: If n = 4q + 2, then 3n + 6 = 12q + 12. Therefore,
(3n + 6) % 4 = (12q + 12) % 4 = 0.
Case 4: If n = 4q + 3, then 3n + 6 = 12q + 15. Therefore,
(3n + 6) % 4 = (12q + 15) % 4 = 3.
Hence, n = 4q + 2
Now, when n = 4q + 2, (n2 + 2n + 1) % 4 = ((4q + 2)2 + 2(4q + 2) + 1) % 4
= (16q2 + 16q + 4 + 8q + 4 + 1) % 4 = (16q2 + 24q + 9) % 4 = 1
[4 marks]
15. Use the process of mathematical induction to prove the following claim:
For any positive integer n, 73n − 1 is divisible by 72.
We will prove this statement by induction.
Base Step:
Let n = 1. So 731 − 1 = 72 which is divisible by 72 as required.
Induction Step:
Assume that 73k−1 is divisible by 72 for some integer k > 1, that is, 73k−1 = 72z
for some integer z.
We will show that 73k+1 − 1 is also divisible by 72 and can thus be written as 72`
for some integer `.
73k+1 − 1 = 73(73k)− 1
= 73(73k)− 1 + 73− 73 # adding and substracting 73
= 73(73k − 1) + 72
= 73(72z) + 72 # induction
= 72(73z + 1).
Thus 73k+1 − 1 is divisible by 72 as required.
By the principle of mathematical induction, 73n − 1 is divisible by 72 for any
positive integer n.
[4 marks]