Preface
Chapter 1 Introductory Problems
- The Factorial: First Encounter with Recursion
- Fibonacci's Sequence: a Two-Term Recursion
- Another Linear Recursion. Bisection Method
- The Bold Gamble. Recursion at its Best
- The Josephus Problem
- Exercises for Section 1-5
Chapter 2 Algorithms in Number Theory
- 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
- All Representations of n in the form x2 + y 2
- Pythagorean Triples
- Counting the Lattice Points in a Ball
- Exercises for Sections 7-9
- Sieves
- Square-free Integers
- Sieve of Eratosthenes
- A Formula for an Irregular Sequence An Olympiad Problem
- Ulam's Sequence
- Exercises for Section 10
- Rotation of an Array
- Partitions
- The Money Changing Problem
- An Abstractly Defined Set
- A Recursive Program with a Surprising Result
- Sequence 56 in Sloane's Handbook of Integer Sequences
- Exercises for Sections 11-16
- Primes
- How to Recognize a Prime
- Empirical Study of the Goldbach Conjecture
- Prime Twins, Triples, Quadruples
- Factoring
- Representation of n as a Sum of Four Squares
- Exercises for Sections 17-18
- Additional Exercises for Sections 1-18
- The Best Rational Approximation
- The Maximum of a Unimodal Function
Chapter 3 Probability
- The Random Number Generator
- Finding Geometric Probabilities by Simulation
- Random Choice of an s-Subset from an n-Set
- Coin Tosses for Poor People
- Shift Registers: Another Source of Cheap Coin Tosses
- Random Sequence Generation by Cellular Automata
- The Period Finding Problem
- Exercises for Sections 1-27
Chapter 4 Statistics
- Matched Pairs
- Permutation Test, P by Simulation
- Permutation Test, P by Computation
- Exercises for Sections 28-30
- The Two Sample Problem of Wilcoxon
- The General Two Sample Test Exercises for Sections 31-32
- Kendall's Rank Correlation
- The Binomial Distribution
- Hypergeometric Distribution
- Fishing Laws
- Estimation of a Probability
- Runs
- The Period of Random(2)
- Waiting for a Complete Set. An Intractable Problem?
- Additional Exercises for Sections 21-40
- The Birthday Problem. An 0(n'/')-Method of Factoring
Chapter 5 Combinatorial Algorithms
- Sorting
- Sorting by Selection
- Sorting by Insertion
- Shellsort
- Quicksort
- Bucket Sort
- The kth Smallest Element of an n-Set
- Binary Search
- Binary Guessing (20 Questions)
- The n-Queens Problem
- Permutations
- Games
- The Subset Sum Problem. The Limits of Computation
Chapter 6 Numerical Algorithms
- Powers with Integer and Real Exponents
- Design of a Square Root Procedure
- The Natural Logarithm
- The Inverse Trigonometric Functions
- The Function exp
- The Cosine
- Archimedes' Integration of the Parabola
- Numerical Integration
- Extrapolation to the Limit and Romberg Integration
- One Thousand Decimals of e
Chapter 7 Miscellaneous Problems
- A Problem from Geometry
- Coupled Difference Equations. The Forward Declaration
- Continued Fractions
- Shrinking Squares: An Empirical Study
- Self Avoiding Random Walks
- 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
|Up|
|Contact|
|Front page|
|Contents|
|Books|
Copyright © 1996-1999 Alexander Bogomolny
|