Answers to Quiz 1 CIS 675 FAlgorithms Distribution of scores Average: 17.19 Median: 18.0 8- 9: 9 9 10-11: 10 10 10 11 11 11 12-13: 12 13 14-15: 14 14 14 14 14 14 15 15 15 15 15 15 16-17: 16 16 16 16 16 16 16 16 17 17 17 17 17 18-19: 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 Average 17.2 Median = 18 Note: For the histogram, fractional scores were rounded down Problem1(10points) For each of the following five pairs of functions f and g, state whether f (n)2Q(g(n)), and if not, then whether f (n)2O(g(n)) or f (n)2W(g(n)). f (n) = g(n) = Answer Why? (q) 2n 1 2n Q limn!¥2n 12n = 12 . (r) 62n 62n+1 Q limn!¥ 62n62n+1 = 12 . (s) 13 n2 + 100200300 n n3 O limn!¥ f (n)g(n) = limn!¥ 12 +100200 300 n 1 n = 0 (t) n3 101112 1314 n2 W limn!¥ n3 10111213 14 n2 = limn!¥ n 10111213 14 = ¥. (u) n2 22 log2 n Q limn!¥ n222 log2 n = limn!¥ n22log 2 n2 = limn!¥n2n2 = 1. (v) n2 (2log2 n)2 Q limn!¥ n2(2log2 n)2 = limn!¥n2n2 = 1. (w) n 3 + 12n2 + 9 26n2 + 8 n 2 O lim n!¥ n3+12n2+9 26n2+8 /n 2 = lim n!¥ n3+12n2+9 26n4+8n2 = 0. (x) n 4 + 12n2 + 9 26n3 + 8 n Q limn!¥ n4+12n2+9 26n3+8 /n = limn!¥ n4+12n2+9 26n4+8n = 1 26 . (y) 2 n n5 n 3 + 6n W lim n!¥ 2n/n5 n3+6n = limn!¥ 2n n8+6n7 = ¥. (z) 6 n n3 + 6n n 5 W lim n!¥ 6n n3+6n n5 = limn!¥ 6n n8+6n7 = ¥. Problem 2 (6 points) In each of the following, say whether the statement is true or false (1 point each) and justify your answer (2 points each). (j) n2 2O(n log2 n)? Answer: No. Because: limn!¥ n2n log 2 n = limn!¥ nlog 2 n = ¥ by Math Fact o. (k) n 4 (n + 1)2 2O(n 2)? Answer: Yes. Because: limn!¥( n4(n+1)2 )/n2 = limn!¥ n4n4+2n3+n2 = limn!¥ 11+2n 1+n 2 = 1. Page 1 of 2 September 21, 2009 Answers to Quiz 1 CIS 675 FAlgorithms (k’) (log2 n)2 2W(n log2 n)? Answer: No. Because: limn!¥(log2 n)2n log 2 n = limn!¥log2 nn = 0 by Math Fact o. (‘) 23n 2W(n22n)? Answer: Yes. Because: limn!¥ 23nn22n = limn!¥23n 2nn = limn!¥2nn = ¥ by Math Fact o. (m) n log2(n2)2W(n(log2 n)2)? Answer: NO. Because: limn!¥n log2(n2)n(log 2 n)2 = limn!¥ 2n log2 nn(log 2 n)2 = limn!¥ 2log 2 n = 0. (m’) 32n 2W(n42n+1)? Answer: No. Because: limn!¥ 32nn42n+1 = limn!¥( 34 )2n4n = limn!¥ 14n( 4 3 )2n = 0 since 43 > 1. Problem 3 (4 points) For each n 1, let Kn be the complete undirected graph on n-vertices. That is Kn = (Vn, En), where Vn =f1, ..., ngand En =ffu, vg: 1 u < v ng. Show by induction on n that En consists of n (n 1)/2 edges. (Obvious hints: The base case is n = 1. To help figure out what is going on, draw a picture!) An Answer: Base case: n = 1. Then K1 = (f1g,˘). So E1 has no edges and 1 (1 1)/2 = 0. Induction step: n > 1. Induction hypothesis: Suppose that En 1 has 12(n 1) (n 2)-many edges. Then En consists of the edges from En 1 together with the edgesf1, ng,f2, ng, ...,fn 1, ng. Therefore, the number of edges in En is: (n 1)(n 2) 2 + (n 1) = n (n 1) 2 . Some Reference Math Facts a. am an = am+n. b. am n = (am)n = (an)m. c. an bn = (a b)n. d. loga an = n. e. aloga n = n. f. (loga x)/(loga b) = logb x. g. log2(a b) = (log2 a) + (log2 b). h. c log2 a = log2 ac. i. nk=1 k = 12 n (n + 1). j. nk=0 2k = 2n+1 1. k. nk=1 k2 = n (n+1) (2n+1)6 . l. ¥k=1 2 k = 1. m. ¥k=1 k 2 k = 2. o. For a > 1 and b, c > 0: limn!¥ (loga n) b nc = limn!¥ nb ac n = 0. p. If limn!¥ f (n)g(n) = c, then: c = 0 0 < c < ¥ c = ¥ f (n)2O(g(n)) True True False f (n)2Q(g(n)) False True False f (n)2W(g(n)) False True True Page 2 of 2 September 21, 2009