Winter 2004 Exam Solutions *** Please note *** These solutions were created for the TAs who marked the exam, and they have not been checked carefully for errors. Also, some answers are not written as completely or formally as we would expect. --------------------------------------------------------------------------- 1. The following paragraph is taken from the website at mathworld.wolfram.com. In 1985, ... G. Frey showed that he could create an unusual elliptic curve which appeared not to be modular. If the curve were not modular, then this would show that if Fermat's last theorem were false, then the Taniyama-Shimura conjecture would also be false. a) Using our precise symbolic notation, write the second sentence from above (the one that begins, "If the curve ..."). [Solution: Let m represent "Frey's curve is modular". Let f represent "Fermat's last theorem is true". Let t represent "The Taniyama-Shimura conjecture is true". ~M -> (~F -> ~T). ] b) In 1986, K. Ribet proved that Frey's curve is not modular. What could Ribet conclude from that about the Taniyama-Shimura conjecture and Fermat's last theorem? [Solution: If the Taniyama-Shimura conjecture is true, then Fermat's last theorem is true. Or equivalently, if Fermat's last theorem is false, then the Taniyama-Shimura conjecture is false. ] c) In the 1990s, A. Wiles, with help from a few others, proved the Taniyama-Shimura conjecture. What could Wiles conclude from that? [Solution: Fermat's last theorem is true.] 2. x is the second smallest odd integer [p(x) /\ -] s in Z, s < x /\ p(s) /\ \-/ y in Z, p(y) -> (y = s \/ y >= x).] 3. a) Venn diagram with sets U and H overlapping (dividing it into 4 regions) Shade everything except region in U and not in H b) \-/ x in A, U(a) -> H(a) c) Venn diagram with set A, B, C overlapping (dividing it into 8 regions). Put an X in region: A, B, not C d) A -> C \/ B -> C 4. b) Give the direct proof outline of (S) \-/ x in D, (-] y in D, p(x, y)) -> q(x) [Solution: Let x in D. Suppose -] y in D, p(x,y). [proof of q(x)] So q(x). Thus (-] y in D, p(x,y)) -> q(x). Since x is an arbitrary element of D, \-/ x in D, (-] y in D, p(x, y)) -> q(x). ] 5. 2^n - 1 = 2^n-1 + 2^n-2 + ... + 2^0 6. Consider the following statement about sequences a_0, a_1, a_2, ... : (S) -]j in N, \-/ i in N, j > a_i /\ a_i <= a_j (a) Formally prove or disprove (S) for the following sequence: (A1) -1,-2,-3,-4,-5,-6,-7,-8,-9, ... defined by A1 = \-/ n in N, an = -(n+1) [Solution: (S) is true for (A1) Let j = 0 Let i in N Then a_i = -(i+1) < 0 = j (Since i>=0) a_j = a_0 = -1, which is >= a_i (Since sequence is decreasing and a_j is the first element) Then j > a_i /\ a_i <= aj Since i is an arbitrary natural number, \-/ i in N, j > a_i /\ a_i <= aj Since j is a natural number, -] j in N, \-/ i in N, j > a_i /\ a_i <= aj ] (b) Formally prove or disprove (S) for the following sequence: (A2) 0,1,1,2,3,5,6,13,21,34, ... defined by A2 = \-/n in N, an = {n n = 0 \/ n = 1 {a_{n-2} + a_{n-1} n>=2 [Solution: (S) is false for (A2) Negate (S) to get \-/j in N, -] i in N, j > a_i -> a_i > a_j Let j in N Let i = j+2, then i in N Suppose j > a_i, so j > a_{j+2} a_i = a_j + a_{j+1} (By defn of A2, since j > 1, so j >=2) Then a_i > a_j (By defn of A2, since j+1 >= 1 and a_{j+1} >=1} Hence j > a_i -> a_i > a_j Since i is a natural number, -] i in N, j > a_i -> a_i > a_j Since j is an arbitrary natural number, \-/j in N, -] i in N, j > a_i -> a_i > a_j ] 7. a) Let c = 20. Then c in R+. (2) Let n in N. (1) Case: n = 0. (1) Then g(n) = 60 = 3c = cf(n) <= cf(n). (1) Case: n > 0. Then g(n) = 5n^2 <= 20n^2 = cn^2 = cf(n). Since n = 0 \/ n > 0, in all cases g(n) <= cf(n). (1) Since n in N is arbitrary: \-/ n in N, g(n) <= cf(n). (1) Since c in R+: -] c in R+, \-/ n in N, g(n) <= cf(n). b) [Solution: O_3(f) = O_4(f). Proof of O_3(f) subset O_4(f): Suppose g in O_3(f). We'll show that g in O_4(f). Then by definition there are constants c3 in R+ and b3 in N such that \-/ n in N, n >= b3 -> g(n) <= c3 f(n). (*) Let c = max{c3,g(0)/f(0),g(1)/f(1),...,g(b-1)/f(b-1)}. Then c in R+ since c >= c3 in R+. Let n in N. Case 1: n < b3. By definition of c, g(n)/f(n) <= c. So g(n) <= c f(n). Case 2: n >= b3. So g(n) <= c3 f(n), by (*) <= c f(n), since by definition of c, c3 <= c. Since n < b3 \/ n >= b3, g(n) <= c f(n). Therefore -] c in R+, \-/ n in N, g(n) <= c f(n). I.e., g in O_4(f). Proof of O_4(f) subset O_3(f): Suppose g in O_4(f). We'll show that g in O_3(f). Then by definition there is a constant c4 in R+ such that \-/ n in N, g(n) <= c4 f(n). (#) Let c = c4. Let b = 0 (any natural number will work). Then c in R+ since c4 in R+. Also b in N. Let n in N. Suppose n >= b. So g(n) <= c4 f(n), by (#) = c f(n), by definition of c. Thus n >= b -> g(n) <= c f(n). Since n is an arbitrary natural number, \-/ n in N, n >= b -> g(n) <= c f(n). Therefore, -] c in R+, -] b in N, \-/ n in N, n >= b -> g(n) <= c f(n). I.e., g in O_3(f). ] 8. Consider the following algorithm that finds the smallest element in an array. There may be duplicate elements in the array. MIN(A, n) min = A[0] i = 0 while(i < n) if (A[i] < min) min = A[i] i = i + 1 return min a) State a loop invariant for MIN, involving A, i and min. Do NOT prove that it is a loop invariant. [Solution: \-/j in N, (0 <= j <= i -> A[j] >= min) /\ -]j in N, (0 <= j <= i /\ A[j] == min) ] b) Let T_MIN(n) denote the worst case time complexity of MIN(A, n). Determine, with justification T_MIN. Do not use O, omega, theta. [Solution: 1. min = A[0] // 4 steps 2. i = 1 // 3 steps 3. while(i < n) // 4 steps 4. if (A[i] < min) // 5 steps 5. min = A[i] // 4 steps 6. i = i + 1 // 5 steps 7. return min // 2 steps Lines 1, 2 execute once. There are n-1 iterations of the loop, so in the worst case lines 3-6 execute n-1 times (Note: for line 5 to execute each time, the array would need to be in descending order). Line 3 executes once more (when the loop condition fails). Line 7 executes once. T_MIN = 4 + 3 + 18(n-1) + 4 + 2 = 13 + (n-1)18 = 18n - 5 (Note: when n = 0, T_MIN(n) = 0) ] c) Prove or disprove that T_MIN(n) in O(n^2). (For n = 0, use T_MIN(n) = 0). [Solution: By defn, -]c in R+, -]b in N, \-/n in N, n >= B -> (18n - 5) <= cn^2. Let c = 2 Let b = 18 Let n in N Suppose n >= B, so n >= 18 n >= 18 n^2 >= 18n n^2 - 5 >= 18n - 5 n^2 + n^2 - 5 >= 18n - 5 (since n >=18) 2n^2 - 5 >= 18n - 5, so 2n^2 >= 18n - 5 Then (18n - 5) <= cn^2, so T_MIN(n) <= cn^2 Hence n >= B -> T_MIN(n) <= cn^2 Since n is an arbitrary natural number, \-/n in N, n >= B -> T_MIN(n) <= cn^2 Since b in N, -] b in N, \-/n in N, n >= B -> T_MIN(n) <= cn^2 Since c in R+, -]c in R+, -] b in N, \-/n in N, n >= B -> T_MIN(n) <= cn^2 Therefore T_MIN(n) in O(n^2) ] 9. a) (|cx-cx'|/x)/(|x-x'|/|x|) = 1 b) Multiplying by a constant doesn't effect relative error if done with exact algorithm, so it can be done stably. 10. a) (2)(7)(8^10)(10) b) 1.110 x 2^2 |7-6.8|/|7| c) B=10, t=1, emin=0, emax=2 9(8+8) = 9(16) = 9(2 x 10^1) = 18 x 10^1 = 2 x 10^1 (9*8)+(9*8) = 72 + 72 = (7 x 10^1) + (7 x 10^1) = 14 x 10^1 = 1 x 10^1 11. a) The programmer thinks the loop stops because eventually the next term is no longer significant to the accumulated sum, and the postcond is true because the remaining part of the sequence is small compared to the accumulated sum. b) At around n = 2^23, "n += 1;" no longer changes n, so n becomes stuck at 2^23. However, before that happens, "sum += 1/n;" stops changing sum. So the loop does terminate, probably with sum ~= ln(2^23) ~= 15. [Note: We wouldn't expect your answer to use such specific numbers. We want you to explain that eventually the value of sum stops changing.]