Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous 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_inline58189 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_inline57635, tex2html_wrap_inline57637, tex2html_wrap_inline57647, tex2html_wrap_inline57649, tex2html_wrap_inline57651, tex2html_wrap_inline57653, tex2html_wrap_inline57655, tex2html_wrap_inline57659, tex2html_wrap_inline57661, tex2html_wrap_inline58033, and tex2html_wrap_inline57695) 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_inline58459, and a small positive integer k, write an algorithm to compute

    displaymath58429

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

next up previous index

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