CMPS 211 Homework Assignment 3 Solution, Spring 2013

CMPS 211 Spring 2007-2008 Solutions for Suggested Problems Chapter 3 (Part 2) Section 3.1 6- procedure numNegative (a1, a2, …, an: integers) count := 0 for i := 1 to n if ai < 0 then count := count + 1 {count has the desired value} 10- procedure powerNonNeg (x: real; n: positive integer) power := 1 for i := 1 to n power := power  x {power has the desired value, and this is a subprocedure being called by another} procedure power (x:real; n: integer) power := powerNonNeg (x, absValue(n)) if n < 0 then power := 1 / power {power has the desired value, for all negative and nonnegative powers} 18- procedure lastSmallest (a1, a2, …, an: integers) smallest := a1 smallestLoc := 1 for i := 2 to n if ai  smallest then begin smallest := ai smallestLoc := i end {smallestLoc has the desired value} 32- procedure greaterTerms (s1, s2, …, sn: integers) sum := s1 termList := {} for i := 2 to n if ai > sum then termList := termList  si sum := sum + si {termList has the desired set} 42- procedure selectionSort (a1, a2, …, an: real numbers) for i := 1 to n-1 begin min := ai minIndex := i for j := i+1 to n if aj < min then begin min := aj minIndex := j end temp := ai ai := aminIndex aminIndex := temp end { a1, a2, …, an are sorted} 50- a) procedure insertionSort (a1, a2, …, an: real numbers) for j := 2 to n begin i := 1 while aj < ai i := i + 1 m := aj for k := 0 to j - i - 1 aj-k := aj-k -1 ai := m end {a1, a2, …, an are sorted} procedure varInsertionSort (a1, a2, …, an: real numbers) for j := n down to 2 begin i := j-1 while aj < ai i := i - 1 m := aj for k := 0 to j - i - 1 aj-k := aj-k -1 ai := m end {a1, a2, …, an are sorted} b) Sort 3, 2, 4, 5, 1, 6 Compare 6 with 1, replace 6 with itself at the same location  3, 2, 4, 5, 1, 6 Compare 1 with 5, 4, 2, 3, replace 1 with 3  1, 3, 2, 4, 5, 6 Compare 4 with 4, replace 5 with itself at the same location  1, 3, 2, 4, 5, 6 Compare 2 with 3, 1, replace 2 with 3  1, 2, 3, 4, 5, 6 Compare 2 with 1, replace 2 with itself at the same location  1, 2, 3, 4, 5, 6 c) The number of comparisons is = 1 + 1 + … + 1 + 1 = n-1 d) The number of comparisons is = (n-1) + (n-2) + … + 2 + 1 = n(n-1) / 2 Section 3.2 8- a) f(x) = 2x2 + x3 log x 2x2  x4 for x > 1 x3  x3 for x > 1 log x < x for x > 1  2x2 + x3 log x < x4 + (x3)(x) = x4 + x4 = 2x4  f(x) =  (x4) for c = 2 and x > 1 c) f(x) = x4 + x2 + 1  x4 + x4 + x4 = 3 x4 for x > 1 x4 + 1  x -4 for x > 1   x4 for x > 1   = 3  f(x) =  (x 0 ) =  (1 ) for c = 3 and x > 1 12- Show x log x =  (x2). log x  x for x > 1  x log x  x2 for x > 1  f(x) =  (x 2 ) for c = 1 and x > 1 Show x2   (x log x). Want to show that there doesn’t exist a pair of c and k to satisfy the equation x2  c x log x and x > k Since x is positive, we can divide both sides of the inequality by x, then x  c log x and x > k but there are no values of c and k to satisfy this inequality.  x2   (x log x). 18- Show that 1k + 2k + … + nk =  (n k+1 ) 1k  nk for n  1 2k  nk for n  1 n k  n k for n  1  1k + 2k + … + nk  nk + nk + … + nk (n times)  1k + 2k + … + nk  n ( nk ) = nk+1  1k + 2k + … + nk =  (n k+1 ) for c = 1, n  1 and k > 0 24- a) Show 3x + 7 =  (x). 1. 3x + 7  4x since 7  x for x > 7  3x + 7 =  (x) for x > 7 2. x  3x + 7 since x is positive  x =  (3x + 7) for x > 0  3x + 7 =  (x) for x > 7. c) Show x + 1/2 =  (x). 1. x + 1/2  x + 1  x + 1/2 =  (x) for x > 1 2. x-1  x + 1/2 since x-1  x + 1/2  x +1  x =  (x + 1/2) for x > 1  x + 1/2 =  (x) for x > 1. e) Show log10 x =  (log2 x). 1. log10 x = =  (log x) for x > 1 2. log2 x = =  (log x) for x > 1  log10 x =  (log2 x) for x > 1. 40- f1(x) =  (g1(x)) and f2(x) =  (g2(x)); show that (f1 f2)(x) =  (g1g2(x)). f1(x) =  (g1(x))  f1(x) =  (g1(x)) and f1(x) =  (g1(x)) f2(x) =  (g2(x))  f2(x) =  (g2(x)) and f2(x) =  (g2(x)) By Theorem 3, f1(x) =  (g1(x)) and f2(x) =  (g2(x)) implies (f1 f2)(x) =  (g1g2(x)). The same proof can be applied to show that if f1(x) =  (g1(x)) and f2(x) =  (g2(x)), then (f1 f2)(x) =  (g1g2(x)). Since (f1 f2)(x) =  (g1g2(x)) and (f1 f2)(x) =  (g1g2(x)), then by the definition of “big-theta”, (f1 f2)(x) =  (g1g2(x)). Section 3.3 4- To find by successive squaring requires k+1 multiplications. To find by multiplying x by itself requires 2k multiplications. The first approach is naturally more efficient. 8- a) Evaluating at x = 2: Input: c = 2, a0 = 1, a1 = 1, a2 = 3. 0. y = 3 initialization of y 1. i = 1, y = 32 + 1 = 7 first iteration in for loop 2. i = 2, y = 72 + 1 = 15 second iteration in for loop Final Answer: y = 15 b) In each iteration of the for loop, one multiplication and one addition are used, so the total number of multiplications and additions in the algorithm is n multiplications and n additions. 12- a) To find the maximum of a sequence of n integers: always requires n-1 comparisons; traverse list from 2 to n, comparing at each iteration b) To locate an element in a list of n terms with linear search: Least number of comparisons is 1; occurs if the element to be located is the first element in the list c) To locate an element in a list of n terms with binary search: Least number of comparisons is 1; occurs if the element to be located is the first element inspected, i.e. the middle element in the list 20- procedure greaterTerms (s1, s2, …, sn: integers) sum := s1 termList := {} for i := 2 to n if ai > sum then termList := termList  si sum := sum + si {termList has the desired set} The procedure developed in this exercise traverses the entire list, comparing each term with the sum of the previous terms. It performs n-1 iterations in the for loop and n-1 comparisons  worst-case time complexity = O (n). 24- procedure selectionSort (a1, a2, …, an: real numbers) for i := 1 to n-1 begin min := ai minIndex := i for j := i+1 to n if aj < min then begin min := aj minIndex := j end temp := ai ai := aminIndex aminIndex := temp end { a1, a2, …, an are sorted} The procedure developed contains a nested for loop, where the outer loop iterates n-1 times, while the inner one is repeated n-i for every iteration of the outer loop. In each such iteration, a single comparison operation is used. So the total number of comparisons is computed by this summation: