Page 404 - Discrete Mathematics and Its Applications

Writing Projects 383

∗ 7. Given a real number a and a nonnegative integer n, find a n 12. Given a nonnegative integer n, find the nth Fibonacci
using the binary expansion of n and a recursive algorithm number using recursion.
k
2
for computing a .
13. Given a positive integer, find the number of partitions of
8. Given two integers not both zero, find their greatest com-
mon divisor using recursion. this integer. (See Exercise 47 of Section 5.3.)
9. Given a list of integers and an element x, locate x in this 14. Given positive integers m and n, find A(m, n), the value of
list using a recursive implementation of a linear search. Ackermann’s function at the pair (m, n). (See the pream-
10. Given a list of integers and an element x, locate x in this ble to Exercise 48 of Section 5.3.)
list using a recursive implementation of a binary search.
11. Given a nonnegative integer n, find the nth Fibonacci 15. Given a list of n integers, sort these integers using the
number using iteration. merge sort.

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. What are the largest values of n for which n! has fewer than covered by right triominoes. Can you make a conjecture
100 decimal digits and fewer than 1000 decimal digits? that answers this question?
∗∗ 5. Implement an algorithm for determining whether a point
2. Determine which Fibonacci numbers are divisible by 5, is in the interior or exterior of a simple polygon.
which are divisible by 7, and which are divisible by 11.
∗∗ 6. Implement an algorithm for triangulating a simple poly-
Prove that your conjectures are correct.
gon.
3. Construct tilings using right triominoes of various 16 × 16, 7. Which values of Ackermann’s function are small enough
32 × 32, and 64 × 64 checkerboards with one square miss- that you are able to compute them?
ing. 8. Compare either the number of operations or the time
needed to compute Fibonacci numbers recursively versus
4. Explore which m × n checkerboards can be completely that needed to compute them iteratively.

Writing Projects

Respond to these with essays using outside sources.

1. Describe the origins of mathematical induction. Who were 4. Describe a variety of different applications of the Fibonacci
the first people to use it and to which problems did they numbers to the biological and the physical sciences.
apply it? 5. DiscusstheusesofAckermann’sfunctionbothinthetheory
of recursive definitions and in the analysis of the complex-
2. Explain how to prove the Jordan curve theorem for sim-
ity of algorithms for set unions.
ple polygons and describe an algorithm for determining
6. Discuss some of the various methodologies used to es-
whether a point is in the interior or exterior of a simple
tablish the correctness of programs and compare them to
polygon.
Hoare’s methods described in Section 5.5.
3. Describe how the triangulation of simple polygons is used 7. Explain how the ideas and concepts of program correctness
in some key algorithms in computational geometry. can be extended to prove that operating systems are secure.