Preface

Chapter 1     Introductory Problems

1. The Factorial: First Encounter with Recursion
2. Fibonacci's Sequence: a Two-Term Recursion
3. Another Linear Recursion. Bisection Method
4. The Bold Gamble. Recursion at its Best
5. The Josephus Problem
• Exercises for Section 1-5

Chapter 2     Algorithms in Number Theory

1. Greatest Common Divisor
• Euclid's Algorithm
• Extended Euclidean Algorithm
• Visible Points in the Plane Lattice Binary GCD Algorithm
• Gill's GCD and LCM algorithm
• Exercises for Section 6
2. All Representations of n in the form x2 + y 2
3. Pythagorean Triples
4. Counting the Lattice Points in a Ball
• Exercises for Sections 7-9
5. Sieves
• Square-free Integers
• Sieve of Eratosthenes
• A Formula for an Irregular Sequence An Olympiad Problem
• Ulam's Sequence
• Exercises for Section 10
6. Rotation of an Array
7. Partitions
8. The Money Changing Problem
9. An Abstractly Defined Set
10. A Recursive Program with a Surprising Result
11. Sequence 56 in Sloane's Handbook of Integer Sequences
• Exercises for Sections 11-16
12. Primes
• How to Recognize a Prime
• Empirical Study of the Goldbach Conjecture
• Factoring
13. Representation of n as a Sum of Four Squares
• Exercises for Sections 17-18
• Additional Exercises for Sections 1-18
14. The Best Rational Approximation
15. The Maximum of a Unimodal Function

Chapter 3     Probability

1. The Random Number Generator
2. Finding Geometric Probabilities by Simulation
• Exercises for Section 22
3. Random Choice of an s-Subset from an n-Set
4. Coin Tosses for Poor People
5. Shift Registers: Another Source of Cheap Coin Tosses
6. Random Sequence Generation by Cellular Automata
7. The Period Finding Problem
• Exercises for Sections 1-27

Chapter 4     Statistics

1. Matched Pairs
2. Permutation Test, P by Simulation
3. Permutation Test, P by Computation
• Exercises for Sections 28-30
4. The Two Sample Problem of Wilcoxon
5. The General Two Sample Test Exercises for Sections 31-32
6. Kendall's Rank Correlation
7. The Binomial Distribution
8. Hypergeometric Distribution
9. Fishing Laws
10. Estimation of a Probability
11. Runs
12. The Period of Random(2)
13. Waiting for a Complete Set. An Intractable Problem?
• Additional Exercises for Sections 21-40
14. The Birthday Problem. An 0(n'/')-Method of Factoring

Chapter 5     Combinatorial Algorithms

1. Sorting
• Sorting by Selection
• Sorting by Insertion
• Shellsort
• Quicksort
• Bucket Sort
2. The kth Smallest Element of an n-Set
3. Binary Search
4. Binary Guessing (20 Questions)
5. The n-Queens Problem
6. Permutations
7. Games
8. The Subset Sum Problem. The Limits of Computation

Chapter 6     Numerical Algorithms

1. Powers with Integer and Real Exponents
2. Design of a Square Root Procedure
3. The Natural Logarithm
4. The Inverse Trigonometric Functions
5. The Function exp
6. The Cosine
7. Archimedes' Integration of the Parabola
8. Numerical Integration
9. Extrapolation to the Limit and Romberg Integration
10. One Thousand Decimals of e

Chapter 7     Miscellaneous Problems

1. A Problem from Geometry
2. Coupled Difference Equations. The Forward Declaration
3. Continued Fractions
4. Shrinking Squares: An Empirical Study
5. Self Avoiding Random Walks
6. A Very Difficult Problem

Appendix A Crash Course in Probability

Solutions of Some Exercises

Summary of Notation and Formulas

A Short Summary of TURBO PASCAL

For Users of other PASCAL compilers

References

Index