Answer to Midterm Question 1 Determine whether or not [not(q) --> not(p)] --> (p --> q) is a tautology. If it is a tautology, prove it without using a truth table. If not, give a counter-example. [not(q) --> not(p)] --> (p --> q) <=> not{not[not(q)] or not(p)} or [not(p) or q] def. of --> <=> not[q or not(p)] or [not(p) or q] double negation <=> not[not(p) or q] or [not(p) or q] commutativity <=> T not(x) or x = T You got one third of the credit for correct use of each of: 1) the definition of --> 2) techniques to simplify the expression and 3) not(x) or x = T. If you used the fact that a statement is logically equivalent to its contrapositive in your argument, you got five points for remembering that fact, but that's all since such arguments employ circular reasoning. ------------------------------- Answer to Midterm Question 2 Classify each of the following functions f as one-to-one, onto , both, or neither. R denotes the set of all real numbers, and R+denotes the set of nonnegative real numbers 2.1: There is no problem 2.1. Everybody got 0/0 on it. :-). 2.2: f:R->R. f = g o h, where g(x) = sqrt(x) maps R+ to R and h(x) = x^2 maps R to R+. Hence f(x) = sqrt(x^2). Thus f(x) = x for all x >= 0, and f(x) = -x for all x<0. So f(x) = |x| for all x. Thus f is neither one-to-one (since f(-1) = f(1) = 1, for instance) nor onto (since there is no x for which f(x) = -1, for example). Grading policy: 0 for saying that g(x) was not a function. 0 for saying that f was both one-to-one and onto. 2 for saying that f was one-to-one, but not onto. 2 for saying that f was onto, but not one-to-one. 5 for saying that f was neither one-to-one nor onto. 2.3: f:R->R. f(x) = 3(x^1/3) + 13. f is one-to-one, since it's a strictly increasing function. f is onto, since, for any y in the real numbers, f(((y-13)/3)^3) = y. Thus for all y there is an x such that f(x) = y. So f is both one-to-one and onto. Grading policy: 0 for saying that f was neither one-to-one nor onto. 2 for saying that f was one-to-one, but not onto. 2 for saying that f was onto, but not one-to-one. 5 for saying that f was both one-to-one and onto. 2.4: f:D->D. D = {0,1,2,3,4,5,6,7,8,9}. f(x) = the last digit of x^3. Note that f(0)=0, f(1)=1, f(2)=8, f(3)=7, f(4)=4 f(5)=5, f(6)=6, f(7)=3, f(8)=2, f(9)=9. So f is a bijection taking D onto itself. So f is both one-to-one and onto. Grading policy: 0 for saying that f was neither one-to-one nor onto. 2 for saying that f was one-to-one, but not onto. 2 for saying that f was onto, but not one-to-one. 5 for saying that f was both one-to-one and onto. 2.5: f:B->C. B = the set of bit strings of length ten, C = the set of bit strings of length nine, f(x) = the complement of the last nine bits of x. Now, f is not one-to-one, since f(0000000000)=f(1000000000)=111111111. f is onto, however. Given a bit string c of length nine, let c' be its complement. Let 0c' be the bit string of length ten that consists of 0 followed by c'. Then f(0c') = the complement of c' = c. So f is onto but not one-to-one. Grading policy: 0 for saying that f was one-to-one, but not onto. 2 for saying that f was neither one-to-one nor onto. 2 for saying that f was both one-to-one and onto. 5 for saying that f was onto, but not one-to-one. ------------------------- Answer to Midterm Question 3 Find a simple expression in terms of n for sum_{k=1}^n k 2^k. Solution 1: Following the hint, we let f(x) = sum_{k=0}^n x^k. By the formula for a geometric series, f(x) = (x^{n+1} - 1)/(x - 1). Therefore, differentiating with respect to x, we have sum_{k=1}^n kx^{k-1} = f'(x) = [(x-1)(n+1)x^n - (x^{n+1} - 1)]/(x-1)^2. Plugging in x = 2, we get sum_{k=1}^n k2^{k-1} = (n+1)2^n - 2^{n+1} + 1. This is almost what we want; we need only to multiply both sides of the equation by 2: sum_{k=1}^n k2^k = 2((n+1)2^n - 2^{n+1} + 1) = (n-1)2^{n+1} + 2. Solution 2: This solution is simpler and doesn't follow the hint, but requires a little more ingenuity. We compute directly: sum k2^k = sum k(2^{k+1} - 2^k) = sum k2^{k+1} - sum k2^k = (sum (k+1)2^{k+1} - sum 2^{k+1}) - sum k2^k = (sum (k+1)2^{k+1} - sum k2^k) - sum 2^{k+1} = ((n+1)2^{n+1} - 0) - 2*sum 2^k = (n+1)2^{n+1} - 2(2^{n+1} - 1). -------------------- Answer to Midterm Question 4 4.1 Find the smallest integer n such that f(x) = 5x^4 + 2x^3 - 6x + 9 if O(n^n). Since f(x) is a polynomial of degree 4, the answer is n = 4. No partial credit was given for this part of the problem. 4.2 Find the smallest integer $n$ such that f(x) = 16x^2 + x^2 (log x) + 8x (log(log x)) is O(x^n). Since f(x) is a sum of 3 terms, we must decide which one grows most rapidly as x -> infinity. Now log(log x) grows more slowly than x, so the last term will not dominate. But log x > 16 for x large enough, so 16x^2 is dominated by x^2(log x). Thus, f(x) is O(x^2(log x)). Since 1 < log x < x in the hierarchy of function growth rates, x^2 < x^2(log x) < x^3 in this hierarchy. Hence n=3 is the smallest integer such that f(x) is O(x^n). About half credit was given for recognizing that x^2(log x) is the dominant term in the sum, but not concluding that n=3. 4.3 Find a simple, small function g(x) such that f(x) = x^2 4^{2x} + x 6^{x} is O(g(x)). Of the 2 terms in this sum, the first dominates as x -> infinity, because 4^(2x) = 16^x dominates 6^x and x^2 dominates x. About half credit was given for recognizing that x^2*4^(2x) dominates, but simplifying it wrong. The best answers are g(x) = (x^2)*(16^x) or (x^2)*(4^(2x)). 4.4 Find a simple, small function g(x) such that f(x) = (5x^4 + 2x^3 - 6x + 9)^5 (16x^2 + x^2(log x) + 8x(log(log x)))^2 (x^2 4^{2x} + x 6^{x})^3 This amounts to putting together the results of the previous parts. Using part 4.1, the first factor is O((x^4)^5) = O(x^20); using part 4.2, the second is O((x^3)^2) = O(x^6); and using part 4.3, the third factor is O((x^2*16^x)^3) = O(x^6 * 16^(3x)). Since Big-O of a product is the product of Big-O of the individual factors [some partial credit was given if the answer obviously reflected knowledge of this fact, although the factors themselves were wrong], the result is g(x) = x^20 * x^6 * x^6 * 16^(3x) = x^32 * 16^(3x). Two other common acceptable answers were x^31 * 16^(3x) and x^30 * (log x)^2 * 16^(3x). No additional credit was taken off for this question on the basis of a wrong answer in (a),(b),(c) unless errors in those parts oversimplified the necessary work for part (d). -------------------- Answer to Midterm Question 5 Use the Euclidean Algorithm to compute d=gcd(145,19), and find integers s and t such that 145s +19t = d. First, we compute the gcd of 145 and 19, using the Euclidean algorithm: 145 = 19(7) + 12 19 = 12(1) + 7 12 = 7(1) + 5 7 = 5(1) + 2 5 = 2(2) +1 2 = 2(1), so 1 is the gcd. (This makes sense since 19 is prime and 145 is not a multiple of 19.) 10 points were awarded for this part, and most people got them. Secondly, the problem asked to find integers s and t such that 145s + 19t = 1. There are many ways of doing this, from the "magic box" to plugging in each equation into the one above it. One method is to use the equations above, starting with the top one, to successively write 12, 7, 5, 2, and finally 1 in terms of 145 and 19. So we have, from the first equation, 12 = 145(1) + 19(-7). From the second equation, we get 7 = 145(-1) + 19(8) Then 5 = 145(2) + 19(-15) 2 = 145(-3) + 19(23) and finally 1 = 145(8) + 19(-61). So we can take s= 8 and t= -61. Partial credit was given as long as the method of approach was clear. People who made arithmetic mistakes tended to only get 2 to 4 points (depending on how clear their write-up was) because this whole question was, essentially, just a big piece of arithmetic.