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
STUDYBLUE makes things that make you better at school.
Things like
online flashcards with photos and audio.
Things like personalized quizzes and friendly reminders about when (and what) to study next.
Think of it as a digital backpack™: access to all of your study materials online and on your phone.
STUDYBLUE exists to make studying efficient and effective for every student, for free.
Join us.
“Simply amazing. The flash cards are smooth, there are many different types of studying tools, and there is a great search engine. I praise you on the awesomeness.”
Dennis
