Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Exercises

  1.   Determine the running times predicted by the detailed model of the computer given in Section gif for each of the following program fragments:
    1. for (int i = 0; i < n; ++i)
          ++k;
    2. for (int i = 1; i < n; i *= 2)
          ++k;
    3. for (int i = n - 1; i != 0; i /= 2)
          ++k;
    4. for (int i = 0; i < n; ++i)
          if (i % 2 == 0)
              ++k;
    5. for (int i = 0; i < n; ++i)
          for (int j = 0; j < n; ++j)
              ++k;
    6. for (int i = 0; i < n; ++i)
          for (int j = i; j < n; ++j)
              ++k;
    7. for (int i = 0; i < n; ++i)
          for (int j = 0; j < i * i; ++j)
              ++k;
  2. Repeat Exercise gif, this time using the simplified model of the computer given in Section gif.
  3. Prove by induction the following summation formulas:
    1. tex2html_wrap_inline58161
    2. tex2html_wrap_inline58163
    3. tex2html_wrap_inline58165
  4. Evaluate each of the following series summations:
    1. tex2html_wrap_inline58167
    2. tex2html_wrap_inline58169
    3. tex2html_wrap_inline58171
    4. tex2html_wrap_inline58173
  5. Show that tex2html_wrap_inline58175, for tex2html_wrap_inline58177. Hint: Let tex2html_wrap_inline58179 and show that tex2html_wrap_inline58181.
  6. Show that tex2html_wrap_inline58183. Hint: Let tex2html_wrap_inline58185 and show that the difference tex2html_wrap_inline58187 is (approximately) a geometric series summation.
  7. Solve each of the following recurrences by repeated substitution:
    1. tex2html_wrap_inline58189
    2. tex2html_wrap_inline58191
    3. tex2html_wrap_inline58193
    4. tex2html_wrap_inline58195
    5. tex2html_wrap_inline58197
    6. tex2html_wrap_inline58199
    7. tex2html_wrap_inline58201

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.