51作业君
首页
低价平台
服务介绍
代写程序
代写论文
编程辅导
程序案例
论文案例
联系方式
诚邀英才
代写选择指南
程序辅导案例
>
Program
>
程序代写案例-VERSION 1
欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
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! Page 1 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 2 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 3 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 4 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 5 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 6 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 7 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 8 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 9 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 10 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 11 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 12 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 13 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 14 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 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] Page 15 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 16 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 17 of 18 VERSION 1 Question/Answer Booklet ID#: COMPSCI 120 This page is intentionally left blank. Page 18 of 18
欢迎咨询51作业君
官方微信
TOP
Email:51zuoyejun
@gmail.com
添加客服微信:
abby12468