Logo 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 (unsigned int i = 0; i < n; ++i)
          ++k;
    2. for (unsigned int i = 1U; i < n; i *= 2U)
          ++k;
    3. for (unsigned int i = n - 1U; i != 0; i /= 2U)
          ++k;
    4. for (unsigned int i = 0; i < n; ++i)
          if (i % 2 == 0)
              ++k;
    5. for (unsigned int i = 0; i < n; ++i)
          for (unsigned int j = 0; j < n; ++j)
              ++k;
    6. for (unsigned int i = 0; i < n; ++i)
          for (unsigned int j = i; j < n; ++j)
              ++k;
    7. for (unsigned int i = 0; i < n; ++i)
          for (unsigned 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_inline58937
    2. tex2html_wrap_inline58939
    3. tex2html_wrap_inline58941
  4. Evaluate each of the following series summations:
    1. tex2html_wrap_inline58943
    2. tex2html_wrap_inline58945
    3. tex2html_wrap_inline58947
    4. tex2html_wrap_inline58949
  5. Show that tex2html_wrap_inline58951, for tex2html_wrap_inline58953. Hint: Let tex2html_wrap_inline58955 and show that tex2html_wrap_inline58957.
  6. Show that tex2html_wrap_inline58959. Hint: Let tex2html_wrap_inline58961 and show that the difference tex2html_wrap_inline58963 is (approximately) a geometric series summation.
  7. Solve each of the following recurrences by repeated substitution:
    1. tex2html_wrap_inline58965
    2. tex2html_wrap_inline58967
    3. tex2html_wrap_inline58969
    4. tex2html_wrap_inline58971
    5. tex2html_wrap_inline58973
    6. tex2html_wrap_inline58975
    7. tex2html_wrap_inline58977

next up previous contents index

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