next up previous
Next: About this document

CSE 5311 Spring 1998
Homework #1
Due: February 4, 1998

  1. a.

       Search(A, k, p, r)                       COST     TIMES
          i = p                                  1         1
          while ((A[i] <> k) and (i <= r))       1        t1+1
             i = i + 1                           1         t1
          if i <= r                              1         1
          then return i                          1         1
          else return -1                         1         1

    b.
    T(n) = 1 + (t1+1) + t1 + 1 + 1 + 1

    c.
    The situation that will always result in the best-case run time is when the key k appears in the first element of the array. In this case the while loop is executed only once.

    Best Case T(n) = 1 + 2 + 1 + 1 + 1 + 1 = 7 = tex2html_wrap_inline237

    d.
    The situation that will result in the worst-case run time is when the key k appears only in the last element of the array. In this case the while loop is executed n times.

    Worst Case T(n) = 1 + (n+1) + n + 1 + 1 + 1 = 5 + n*(2) = tex2html_wrap_inline239

  2. a.

       Search(A, k, p, r)                           COST     TIMES
          if (p <= r)                                1         1
          then i = (p+r)/2                           1         t1
               if (k == A[i])                        1         t1
               then return i                         1       t1*t2
               else if (k < A[i])                    1       t1*(1-t2)
                    then Search(A, k, p, i)        T(n/2)    t1*(1-t2)*t3
                    else Search(A, k, i+1, r)      T(n/2)    t1*(1-t2)*(1-t3)
          else return -1                             1        1-t1

    b.
    The situation that results in the best case is when the key k is found in position i halfway through the array. In this case the value of t1 is 1 and the value of t2 is 1. One of the worst-case situations is when k is found in the last element of the array (the maximum possible number of recursive calls must be made).

    c.

    displaymath235

    Master method: a=1, b=2, f(n) = 4 = tex2html_wrap147 . This is case 2 because tex2html_wrap148 = 0. Thus T(n) = Theta(lgn).

  3. The following chart shows the run time of algorithms that use f(n) operations to run on a computer where each opration takes one second to execute. Fill in the blanks in the chart.

    n f(n) = lg n f(n) = n f(n) = n lg n f(n) = tex2html_wrap_inline241 f(n) = tex2html_wrap_inline243
    10 3.3s 10s 33.0s 100s 1024s
    20 4.3s 20s 86s 400s 291h
    50 5.6s 50s 280s 2500s (= 41.7min) 357,020 centuries
    100 6.6s 100s 660s (= 11min) 10,000s (= 2.78h) 4* tex2html_wrap150 centuries
    1,000 9.96s 1,000s 9960s (= 2.76h) 277.78h ***
    10,000 13.3s 10,000s (= 167min) 133000s (= 36.9h) 1,157 days ***

  4. For each of the following, answer ``yes'', ``no'', or ``cannot tell''. Explain your reasoning.

    1. Is tex2html_wrap_inline245 = O( tex2html_wrap_inline241 )?

      No. In order for tex2html_wrap_inline245 to be O( tex2html_wrap_inline241 ), we would have to find c and tex2html_wrap_inline253 such that tex2html_wrap151 for all n >= tex2html_wrap_inline253 . Dividing each term by n, we see that we would need tex2html_wrap152 , which for any constant c will not be met as n grows beyond the value of c.

    2. Is tex2html_wrap_inline245 = tex2html_wrap_inline261 ( tex2html_wrap_inline241 )?

      Yes. In order for tex2html_wrap_inline245 to be tex2html_wrap_inline261 ( tex2html_wrap_inline241 ), we need to find c and tex2html_wrap_inline253 such that tex2html_wrap153 for all n >= tex2html_wrap_inline253 . Dividing each term by n yields tex2html_wrap154 , which is true for c = 1 and tex2html_wrap_inline253 = 1.

  5. Arrange the following expressions by growth rate from slowest to fastest.

    tex2html_wrap155 n! tex2html_wrap156 tex2html_wrap157 tex2html_wrap158 tex2html_wrap159 tex2html_wrap160

    Arranged left-to-right as slowest to fastest growth rate we get

    tex2html_wrap159 tex2html_wrap160 tex2html_wrap156 tex2html_wrap158 tex2html_wrap155 tex2html_wrap157 n!

  6. Give asymptotically tight upper and lower bounds for T(n) in each of the following currences. Assume that T(n) is constant for n <= 2. For each problem use two of the described methods to solve the recurrence.

    1. T(n) = 2T(n/2) + tex2html_wrap_inline245 .

      Master

      a=2, b=2, f(n) = tex2html_wrap_inline245 , tex2html_wrap167 = 1. This is case 3 with tex2html_wrap_inline285 = 2. We need to show that 2f(n/2) <= cf(n) for c<1 and sufficiently large n. Show that 2*( tex2html_wrap168 ) <= c* tex2html_wrap_inline245 , or 2( tex2html_wrap169 ) <= c tex2html_wrap_inline245 , 1/4 tex2html_wrap_inline245 <= c tex2html_wrap_inline245 , which is true for c=1/2.

      Thus T(n) = tex2html_wrap170 .

      Iteration

      T(n) = tex2html_wrap_inline245 + 2T(n/2)
      = tex2html_wrap_inline245 + 2( tex2html_wrap171 + 2T(n/4))
      = tex2html_wrap_inline245 + 2( tex2html_wrap171 + 2( tex2html_wrap173 + 2T(n/8)))
      = tex2html_wrap_inline245 + tex2html_wrap174 + 4( tex2html_wrap173 + 2T(n/8)))
      The ith term is tex2html_wrap176 and the boundary case is reached when tex2html_wrap177 = 1, i >= tex2html_wrap160 .

      tex2html_wrap179 = tex2html_wrap180 or tex2html_wrap181 + tex2html_wrap160 tex2html_wrap147
      = tex2html_wrap184 = tex2html_wrap185 = O( tex2html_wrap_inline245 )

    2. T(n) = 3T(n-2) + tex2html_wrap186

      Iteration

      eqnarray71

      The recursion will terminate when the argument to T() equals 1, i.e., n-2i = 1 or i = (n - 1)/2.

      eqnarray74

      Substitution

      First, show tex2html_wrap_inline323 using the inductive hypothesis tex2html_wrap_inline325 .

      eqnarray90

      Unfortunately, we cannot discard the tex2html_wrap_inline237 without decreasing the righthand side and violating the inequality. So, we choose a different member of tex2html_wrap_inline329 for T(n); namely, tex2html_wrap_inline333 , where b is a constant. The inductive hypothesis is now tex2html_wrap_inline337 .

      eqnarray99

      given that tex2html_wrap_inline339 , or tex2html_wrap_inline341 . Since this is a valid constant, tex2html_wrap_inline343 .

      Next, show tex2html_wrap_inline345 using the inductive hypothesis tex2html_wrap_inline347 .

      eqnarray110

      since we can subtract tex2html_wrap_inline237 from the righthand side without violating the inequality. Therefore, tex2html_wrap_inline351 , and tex2html_wrap_inline353 .

    3. T(n) = 3T(n/3) + tex2html_wrap147

      Master

      a=3, b=3, f(n) = tex2html_wrap147 , tex2html_wrap189 = 1. This is case 1 where tex2html_wrap_inline285 = 1. T(n) = tex2html_wrap190 .

      Iteration

      eqnarray121

      The recursion will terminate when the argument to T() equals 1, i.e., tex2html_wrap_inline359 , or tex2html_wrap_inline361 , or tex2html_wrap_inline363 .

      eqnarray124

      Substitution

      First, show tex2html_wrap_inline365 using the inductive hypothesis tex2html_wrap_inline367 .

      eqnarray134

      Unfortunately, we cannot discard the tex2html_wrap_inline237 without decreasing the righthand side and violating the inequality. So, we choose a different member of O(n) for T(n); namely, tex2html_wrap_inline375 , where b is a constant. The inductive hypothesis is now tex2html_wrap_inline379 .

      eqnarray136

      given that tex2html_wrap_inline339 , or tex2html_wrap_inline383 . Since this is a valid constant, T(n) = O(n).

      Next, show tex2html_wrap_inline387 using the inductive hypothesis tex2html_wrap_inline389 .

      eqnarray138

      The last step is valid since we can always reduce the righthand side of the inequality. Therefore, tex2html_wrap_inline391 , and tex2html_wrap_inline393 .




next up previous
Next: About this document

Diane J. Cook
Wed Feb 11 10:03:52 CST 1998