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

Projects

  1. Write a non-recursive method 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 method to compute tex2html_wrap_inline57682 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_inline57130, tex2html_wrap_inline57132, tex2html_wrap_inline57142, tex2html_wrap_inline57144, tex2html_wrap_inline57146, tex2html_wrap_inline57148, tex2html_wrap_inline57150, tex2html_wrap_inline57154, tex2html_wrap_inline57156, tex2html_wrap_inline57526, and tex2html_wrap_inline57190) 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_inline57952, and a small positive integer k, write an algorithm to compute

    displaymath57922

    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_inline57958. For each sequence, test the hypothesis that the probability that tex2html_wrap_inline57342 is larger than all its predecessors in the sequence is tex2html_wrap_inline57962. (For a good source of random numbers, see Section gif).

next up previous contents index

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