QBUS1040: Foundations of Business Analytics Mid-semester exam Solution Semester 1, 2019 This is a 120-minute in-class exam. There is no separate reading time. The exam is open book, open notes. You may refer to the documentation of Python (python.org) and Python packages such as NumPy (docs.scipy.org) and Scikit-learn (scikit-learn.org). However, you cannot discuss this exam with anyone until the exam is over. This means you cannot use online forums, social media platforms and any other means of communication. The only exception is that you can ask invigilators for clarification. The use of search engines (Google, Bing, Yahoo, Baidu, etc.) is also forbidden. Throughout this exam we use standard mathematical notation; in particular, we do not use (and you may not use) notation from any computer language, or from any strange or non-standard mathematical dialect (e.g., physics). This exam consists of ten problems. Six of them are in this paper. The last four problems are described in a separate Jupyter Notebook file. You need to write your answers to problems 1-6 directly in this exam. You should use scratch paper (which you will not turn in) to do your rough work. We will deduct points for messy and poorly written solutions, even if they are correct. You should also download the Jupyter Notebook file for this exam from Canvas (go to ‘Assignments/Mid-semester exam’ section) and type your code in the space provided. When you are done, save the file and upload it to Canvas (again, go to ‘Assignments/Mid-semester exam’ section). Problem 1 is multiple choice. For this problem simply choose the appropriate response or responses. You do not need to give any justification for your answers to these questions. If we can’t tell which response or responses you are selecting, we will give zero credit. For the remaining problems you are asked for a free-form answer, which must be written in the box below the problem. We won’t read anything outside the boxes. Note that problems have unequal weight. Some are easy. Others, not so much. Good luck! SID: Question: 1 2 3 4 5 6 7 8 9 10 Total Points: 10 10 10 10 10 10 10 10 10 10 100 Score: i QBUS1040 Mid-semester exam Semester 1, 2019 1. Suppose S = {a, b, c} and T = {d, e, f} are two linearly independent sets of n-vectors. For each of the sets given below, determine which statement is correct. You may not use a computer to answer the questions. (Only one is correct in each case.) (a) (3 points) {a, b, c, d, e, f} © is always linearly independent. © is always linearly dependent. © could be linearly independent or linearly dependent, depending on the values of a, . . . , f . (b) (3 points) {a+ d, b+ e, c+ f} © is always linearly independent. © is always linearly dependent. © could be linearly independent or linearly dependent, depending on the values of a, . . . , f . (c) (4 points) {a, a+ b, a+ b+ c} © is always linearly independent. © is always linearly dependent. © could be linearly independent or linearly dependent, depending on the values of a, . . . , f . Solution: Q1(a) a, b, c, d, e, f could be linearly independent or linearly dependent. Example of linearly dependence: a = d, b = e, c = f . Example of linearly independence: When n >= 6 let a, b, c, d, e, f be six different unit vectors. Q1(b) a+ d, b+ e, c+ f could be linearly independent or linearly dependent. Example of linearly dependence: a = d, b = e, c = f . Example of linearly independence: When n >= 6 let a, b, c, d, e, f be six different unit vectors, starting from (1, 0, 0, 0, 0, 0). Thus, a + d = (1, 0, 0, 1, 0, 0), b + e = (0, 1, 0, 0, 1, 0), c + f = (0, 0, 1, 0, 0, 1), they are linearly independent. Q1(c) a, a+ b, a+ b+ c is always linearly independent. Proof Set x1 ∗a+x2 ∗ (a+ b)+x3 ∗ (a+ b+ c) = 0, where x1, x2, x3 are three scalars. Rearrange the equation will give us (x1 + x2 + x3) ∗ a+ (x2 + x3) ∗ b+ x3 ∗ c = 0. Given a, b, c are linearly independent, we have x3 = x2 = x1 = 0. Page 1 of 6. QBUS1040 Mid-semester exam Semester 1, 2019 2. (10 points) The cross product of two 3-vectors a = (a1, a2, a3) and x = (x1, x2, x3) is defined as the vector a× x = a2x3 − a3x2a3x1 − a1x3 a1x2 − a2x1 . Assume a is fixed. Show that the function f(x) = a× x is a linear function of x, by giving a matrix A that satisfies f(x) = Ax for all x. (You can just give A; you do not need to verify that a×x = Ax for all x.) Solution: a× x = a2x3 − a3x2a3x1 − a1x3 a1x2 − a2x1 = 0 · x1 − a3 · x2 + a2 · x3a3 · x1 + 0 · x2 − a1 · x3 −a2 · x1 + a1 · x2 + 0 · x3 = 0 −a3 a2a3 0 −a1 −a2 a1 0 x1x2 x3 Thus, A = 0 −a3 a2a3 0 −a1 −a2 a1 0 Marking Scheme • full marks for correct answer; • 6 marks for making mistakes in the final answer, e.g. missing a minus sign or wrong index; • 1 marks for the attempt; • 0 mark for no attempt or just copying the question. 3. (10 points) We consider a set of n currencies, labeled 1, . . . , n. (These might correspond to USD, RMB, EUR, and so on.) At a particular time the exchange or conversion rates among the n currencies are given by an n × n (exchange rate) matrix R, where Rij is the amount of currency i that you can buy for one unit of currency j. (All entries of R are positive.) The exchange rates include commission charges, so we have RjiRij < 1 for all i 6= j. You can assume that Rii = 1. Suppose y = Rx, where x is a vector (with nonnegative entries) that represents the amounts of the currencies that we hold. What is yi? Your answer should be in English. Solution: From the linear equation y = Rx, we can deduce that yi = n∑ k=1 Ri,kxk. Thus, yi is the total amount of currency i obtained when we exchange all our money in other currencies to currency i and take into account the commission charges. Marking Scheme • full marks for correct answer; • 8 marks for correct answer but not mentioning the commission charges; • 6 marks for right idea but imprecise or incorrect answer • 4 marks for incorrect answer but made some reasonable attempt • 0 mark for no attempt or unsubstantial attempt (e.g. copy and paste from the question) Page 2 of 6. QBUS1040 Mid-semester exam Semester 1, 2019 4. (a) (5 points) How are x and Ax related, where A is the 6× 6 matrix A = 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 . Your answer should be in English. Solution: 4(a) Ax = 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 x1 x2 x3 x4 x5 x6 = x5 x6 x1 x2 x3 x4 A shifts all entries/elements in x downwards by two positions, i.e. the first four elements in x become the last four elements in Ax, while the last two elements in x become the first two elements in Ax. Marking Scheme • full marks for correct answer; • 4 marks for missing the exact ordering, e.g. shifting the last two elements in x to the first two positions in Ax; • 2 marks for taking x as a scalar; • 1 marks for the attempt or lack of interpretation in English; • 0 mark for no attempt, wrong concept in matrix-vector multiplication or taking x as a matrix. (b) (5 points) What is A3? (You can just give the matrix.) Hint. The answer should make sense, given your answer to part (a). Solution: (b) A3 = I6×6 = 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 Marking Scheme • full marks for correct answer; • 3 marks for missing a row/column in the matrix or just interpreting (A3)ij as the number of paths of length 3 from j to i without giving the exact answer of the matrix A3; • 1 mark for the attempt; • 0 mark for no attempt or wrong concept in matrix-matrix multiplication. Page 3 of 6. QBUS1040 Mid-semester exam Semester 1, 2019 5. Suppose you need to compute z = (A+B)(x+ y), where A and B are m× n matrices and x and y are n-vectors. (a) (3 points) What is the approxima te flop count if you evaluate z as expressed, i.e., by adding A and B, adding x and y, and then carrying out the matrix-vector multiplication? (b) (3 points) What is the approximate flop count if you evaluate z as z = Ax + Ay + Bx + By, i.e., with four matrix-vector multiplies and three vector additions? (c) (4 points) Which method requires fewer flops? Your answer can depend on m and n. (Remark. When comparing two computation methods, we usually do not consider a factor of 2 or 3 in flop counts to be significant, but in this question you can.) Solution: For this question recall that given a m × n matrix A and a n-vector x, the exact number of flops required to evaluate Ax is m(2n−1) and the approximate number of flops (given in lecture notes) is 2mn. Either were accepted. Thus, the solutions will be split into two parts: A version for the exact and a version of the approximate. Exact Flops (a) The addition of A and B requires mn flops and the addition of x and y requires n flops. The multiplication of A + B and x + y requires m(2n − 1) flops. Altogether ca := mn+ n+m(2n− 1) = 3mn+ n−m flops are required. (b) Each matrix-vector multiplication requires m(2n − 1) flops. Each addition of m−vectors require m flops. Thus this method requires cb := 4m(2n− 1) + 3m = 8mn−m flops. (c) Taking the difference between cb and ca, we have cb − ca = (8mn−m)− (3mn+ n−m) = 5mn− n = n(5m− 1). However, n and m are positive integers greater than 1, and as a result 5m − 1 is also positive. Hence cb − ca > 0 for all n and m. In conclusion, the method from part a) requires less flops. Approximate Flops (a) The addition of A and B requires mn flops and the addition of x and y requires n flops. The multiplication of A + B and x + y requires 2mn flops. Altogether ca := mn+ n+ 2mn = 3mn+ n flops are required. (b) Each matrix-vector multiplication requires m(2n − 1) flops. Each addition of m−vectors require m flops. Thus this method requires cb := 8mn+ 3m = 8mn+ 3m flops. (c) Taking the difference between cb and ca, we have cb − ca = (8mn+ 3m)− (3mn+ n) = 5mn− n+ 3m = n(5m− 1) + 3m. However, n and m are positive integers greater than 1, and as a result 5m − 1 is also positive. Hence cb − ca > 0 for all n and m. In conclusion, the method from part a) requires less flops. Marking Scheme for a) and b) • full marks for correct answer; • 2 marks for almost correct answer. i.e. off by a constant factor; • 1 mark for some correct steps; • 0 marks for no attempt or incorrect steps and answer; Marking Scheme for c) (allowed errors in a) and b) to be carried forward) • full marks for correct answer with reasoning; • 3 marks for correct answer but lack of convincing reasoning; Page 4 of 6. QBUS1040 Mid-semester exam Semester 1, 2019 • 3 marks for correct approach and steps but the final conclusion was missing; • 2 marks for correct approach but incorrect answer and conclusion; • 0 marks for no attempt or incorrect steps and answer; 6. (10 points) Let A and B be the n × n adjacency matrices of two directed graphs with n vertices. The squared distance ‖A−B‖2 can be used to express how different the two graphs are. Show that ‖A − B‖2 is the total number of directed edges that are in one of the two graphs but not in the other. Solution: • (1 mark) For the attempt. • (3 marks) Understand what is an adjacency matrix, how it is related to a graph. – The nxn matrix A has the form, Ai,j = 1, if (i, j) ∈ R, Ai,j = 0 if (i, j) 6∈ R. – Ai,j = 1 means there is an edge between i and j (The discussion of direction is not necessary, if they assume A and B has the same form. • (1 mark) Understand the rule of matrix addition. – A−B is subtracting corresponding elements of A and B. • (3 marks) Discuss the Matrix A−B. – Matrix A−B will have elements 0, 1 or -1. – If (A− B)i,j = 1, we have Ai,j = 1 and Bi,j = 0. In other words, the corresponding relation (i, j) is only contained in matrix A. Same logic for (A−B)i,j = −1. – If (A−B)i,j = 0, we have Ai,j = 1 and Bi,j = 1, or Ai,j = 0 and Bi,j = 0. The first possibility means relation (i, j) is in both Matrix A and B. The second possibility means relation (i, j) is neither in Matrix A nor Matrix B. • (2 marks) Discuss what is the norm of a matrix. – ||A − B|| = √∑n i=1 ∑n j=1(A−B)i,j . Therefore, ||A − B||2 computes the number of 1 and -1 in matrix A−B. 7. (10 points) See the Jupyter Notebook file for problem description and instructions. Solution: 7(a) True. Suppose that β1c1 + . . . + βkck = 0. Then we have β1a1 + . . . + βkak = 0 and β1b1 + . . . + βkbk = 0. Since a1, . . . , ak are linearly independent, the coefficients must be 0. So c1, …, ck are linearly independent. 7(b) False, we cannot conclude. Examples on both sides of the argument can be found. Page 5 of 6. QBUS1040 Mid-semester exam Semester 1, 2019 8. (10 points) See the Jupyter Notebook file for problem description and instructions. Solution: 8(a) True. Since Aei = Bei for each i, we see that each column of A equals the corresponding column of B, hence A = B. 8(b) False. This holds only sometimes. For example, if x = (1, 0), A = [ 1 10 2 10 ] , B = [ 1 5 2 5 ] , then the results can be the same even the matrices are not equal. 9. (10 points) See the Jupyter Notebook file for problem description and instructions. Solution: 9(a) True. Please refer to formula (3.6) in the textbook. 9(b) True. Please refer to formula (3.5) in the textbook. 10. (10 points) See the Jupyter Notebook file for problem description and instructions. Solution: Please refer to the individual feedback report sent to you for the code solving Problem 10. Page 6 of 6.
