6.042/18.062] Mathematics for Computer Science April 13, 2005 Srini devadas and Eric Lehman Quiz 2 YOUR NAME Calculators are not allowed on this exam You may use one 8.5 x 11"sheet with notes in your own handwriting on both side but no other sources of information You may assume all results from lecture, the notes, problem sets, and recitation Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them · The exam ends at930PM · GOOD LUCK! Problem Points Grade Grader 10 10 15 4 15 6 15 15 匚 Total_100
6.042/18.062J Mathematics for Computer Science April 13, 2005 Srini Devadas and Eric Lehman Quiz 2 YOUR NAME: • Calculators are not allowed on this exam. • You may use one 8.5 × 11” sheet with notes in your own handwriting on both sides, but no other sources of information. • You may assume all results from lecture, the notes, problem sets, and recitation. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. • The exam ends at 9:30 PM. • GOOD LUCK! Problem Points Grade Grader 1 10 2 10 3 15 4 15 5 20 6 15 7 15 Total 100
Quiz 2 NOTE: For this exam a" closed form"is a mathematical ex pression without summation notation, product notation, or the symbol Factorials and binomial coefficients may appear in a closed form. Some examples are shown below Closed forms NOT Closed Forms 42 k=0 (Vx+1 I(+)
� � � Quiz 2 2 NOTE: For this exam, a “closed form” is a mathematical expression without summation notation, product notation, or the . . . symbol. Factorials and binomial coefficients may appear in a closed form. Some examples are shown below. Closed Forms NOT Closed Forms n 42 k2 k=0 n � � n ( √x + 1) � 1 + 1 i i=1 n 1 1 1 n! + + + . . . + 3 1 2 n
Quiz 2 Problem 1. [10 points] Let S consist of all positive integers with no prime factor larger than 3, and define X Thus, the first few terms of the sum are X 1-6 12 (a)Write a closed-form expression in the box that makes the equation below true. X j=0k=0 Solution. Every positive integer with no prime factor larger than 3 has the form 3 for some nonnegative integers j and k. Thus, the expression 23k makes the equation true (b) Write a closed-form expression in the box that makes this equation true X Solution. Well apply the formula for an infinite geometric sum twice 27 j=0k=0 1-1/3 1-1 3
�� Quiz 2 3 Problem 1. [10 points] Let S consist of all positive integers with no prime factor larger than 3, and define: � 1 X = k k∈S Thus, the first few terms of the sum are: 1 1 1 1 1 1 1 1 X = + + + + + + + + . . . 1 2 3 4 6 8 9 12 (a) Write a closedform expression in the box that makes the equation below true. ∞ ∞ X = j=0 k=0 Solution. Every positive integer with no prime factor larger than 3 has the form 2j3k for some nonnegative integers j and k. Thus, the expression 1 2j3k makes the equation true. (b) Write a closedform expression in the box that makes this equation true: X = Solution. We’ll apply the formula for an infinite geometric sum twice. � � �∞ �∞ 1 �∞ 1 �∞ 1 = 2j3k 2j 3k j=0 k=0 j=0 �∞ 1 k=0 � 1 � = j=0 � 2j 1 1 − 1/3 ��∞ 1 = 1 − 1/3 j=0 � � � 2j � 1 1 = 1 − 1/3 1 − 1/2 = 3
Quiz 2 Problem 2. [10 points] Derive integrals that are closely-matching lower and upper bounds on the sum 1 In k k=n where n >3. Justify your answers with a diagram. Do not integrate. Your answers should be unevaluated integrals (a) Draw your diagram in the space below. To receive full credit, the diagram must clearly communicate why your integral bounds are correct Solution y In(n+1) n(2n) (b)Write your lower bound integral here ri- in( da (c)Write your upper-bound integral here 1
Quiz 2 4 Problem 2. [10 points] Derive integrals that are closelymatching lower and upper bounds on the sum � 2n 1 ln k k=n where n ≥ 3. Justify your answers with a diagram. Do not integrate. Your answers should be unevaluated integrals. (a) Draw your diagram in the space below. (To receive full credit, the diagram must clearly communicate why your integral bounds are correct.) Solution. - 6 y = 1 ln x y = 1 ln(x 1 ln n 1 ln(n 1 n) +1) +1) ln(2 n − 1 n 2n � 2n 1 (b) Write your lower bound integral here → dx n−1 ln(x+1) � 2n 1 (c) Write your upperbound integral here → dx n−1 ln x
Quiz 2 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the n-th harmonic number; thus, Hn=1/1+1/2+..+1/n (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) ogn 6O90 7+1 2H In n 6OΩ 0.01 100 n 6OΩ Solution.(1)9(2)O,o(3),O,9(4)2(5)g (b) Suppose that f(n)n g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false f(n)2~g(m)2 true false (n)=o(g(n)) true false false f(n)=6(29(m true false Solution.(a) True.(b)True. (c) False for all f, g.(d) False. Let f(n)=n, g(n) + logn
� � � � � � Quiz 2 5 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the nth harmonic number; thus, Hn = 1/1 + 1/2 + . . . + 1/n. (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) n2 log n 2 n = √ Θ O Ω o n + 1 3n − n 3 2n = Θ O Ω o 2Hn = (ln n) Θ O Ω o 0.01 n = (ln n) 100 Θ O Ω o Solution. (1) Ω (2) O, o (3) Θ, O, Ω (4) Ω (5) Ω. (b) Suppose that f(n) ∼ g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false. f(n) 2 ∼ g(n) 2 true false f(n) = O(g(n)) true false f(n) = o(g(n)) true false 2f(n) = Θ(2g(n) ) true false Solution. (a) True. (b) True. (c) False for all f, g. (d) False. Let f(n) = n, g(n) = n + log n