CMSC351 Kruskal Homework 0 There are twelve problems Within reason you should show your work Problem 0 is due before class Wednesday January 29 Problems 1 9 are due Friday January 31 Problem 0 Memorize the following summation formulas Do not hand in a b c a b n cid 88 n cid 88 i 1 i 0 i n n 1 2 2i 2n 1 1 cid 88 i 0 ri 1 1 r r 1 i i 1 5 cid 88 5 cid 88 i 1 2i i 0 n cid 88 i 1 n cid 88 i 1 5 3i2 4 4 6i2 1 Problem 1 Evaluate the following sums by hand Problem 2 Write as a single summation Problem 3 a Assume bx a What is x in terms of a and b b Using only part a show that logc ab logc a logc b c Show that alogb n nlogb a Problem 4 Di erentiate the following functions a ln x2 5 b lg x2 5 c 1 ln x2 5 NOTE In Computer Science we use lg x to mean log2 x CMSC351 Kruskal Homework 0 Problem 5 Integrate the following functions HINT Use integration by parts d x ln x HINT Use integration by parts Problem 6 Use mathematical induction to show the following a 1 x 1 b 3x 7 c ln x e x lg x a b n cid 88 i 1 i i 1 n n 1 n 2 3 2i 2n 1 1 n cid 88 i 0 n cid 88 i 0 2i a2n b Problem 7 Assume that you guess that Problem 8 Consider the formula 7n3 log n 3n4 2n2 a What is the high order term b What is the second order term c Write the formula in notation in simplest form for constants a and b Use constructive induction to verify the formula and derive a and b Page 2 of 3 CMSC351 Kruskal Homework 0 Problem 9 Assume that you have a random list of n distinct numbers For example here is a list of nine numbers 50 20 90 60 40 70 10 80 30 The rst number is 50 the second number is 20 the third number is 90 etc The smallest number is 10 the second smallest number is 20 the third smallest number is 30 etc Let 1 i cid 54 j n Do NOT show your work a What is the probability that the ith number is the smallest number b What is the probability that the ith number is one of the two smallest numbers c What is the probability that the ith number is the smallest of the rst i numbers d What is the probability that the ith number is one of the i smallest numbers e What is the probability that the ith and jth numbers are the two smallest numbers in either order numbers 2 k n f What is the probability that the ith and jth numbers are both among the k smallest g Assume n is odd What is the probability that the element in the middle i e location n 1 2 is either larger than the maximum of the rst n 1 2 values or larger than the maximum of the last n 1 2 values Page 3 of 3
View Full Document
Unlocking...