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

Projects

  1. Write a non-recursive routine to compute the factorial of n according to Equation gif. Calculate the running time predicted by the detailed model given in Section gif and the simplified model given in Section gif.
  2. Write a non-recursive routine to compute tex2html_wrap_inline58739 according to Equation gif. Calculate the running time predicted by the detailed model given in Section gif and the simplified model given in Section gif.
  3.   Write a program that determines the values of the timing parameters of the detailed model ( tex2html_wrap_inline58177, tex2html_wrap_inline58179, tex2html_wrap_inline58189, tex2html_wrap_inline58191, tex2html_wrap_inline58193, tex2html_wrap_inline58195, tex2html_wrap_inline58197, tex2html_wrap_inline58201, tex2html_wrap_inline58203, tex2html_wrap_inline58579, tex2html_wrap_inline58581, and tex2html_wrap_inline58237) for the machine on which it is run.
  4. Using the program written for Project gif, determine the timing parameters of the detailed model for your computer. Then, measure the actual running times of Programs gif, gif and gif and compare the measured results with those predicted by Equations gif, gif and gif (respectively).
  5. Given a sequence of n integers, tex2html_wrap_inline59011, and a small positive integer k, write an algorithm to compute

    displaymath58979

    without multiplication. Hint: Use Horner's rule and bitwise shifts.

  6. Verify Equation gif experimentally as follows: Generate a large number of random sequences of length n, tex2html_wrap_inline59017. For each sequence, test the hypothesis that the probability that tex2html_wrap_inline58389 is larger than all its predecessors in the sequence is tex2html_wrap_inline59021. (For a good source of random numbers, see Section gif).

next up previous contents index

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