Review good programming style.

Summarize the basic mathematical background needed for the rest of the book.

A second problem is to solve a popular word puzzle. The input consists of a two-dimensional array of letters and a list of words. The object is to find the words in the puzzle. These words may be horizontal, vertical, or diagonal in any direction. As an example, the puzzle shown in Figure 1.1 contains the words *this, two, fat*, and *that*. The word *this* begins at row 1, column 1 (1,1) and extends to (1, 4); *two* goes from (1, 1) to (3, 1); *fat* goes from (4, 1) to (2, 3); and *that* goes from (4, 4) to (1, 1).

An important concept is that, in many problems, writing a working program is not good enough. If the program is to be run on a large data set, then the running time becomes an issue. Throughout this book we will see how to estimate the running time of a program for large inputs and, more importantly, how to compare the running times of two programs without actually coding them. We will see techniques for drastically improving the speed of a program and for determining program bottlenecks. These techniques will enable us to find the section of the code on which to concentrate our optimization efforts.

1 2 3 4

-------------

1 t h i s

2 w a t s

3 o a h g

4 f g d t

x^{a}x^{b}= x^{a+b}

x^{a}

-- = x^{a-b}

x^{b}

(x^{a})^{b}= x^{ab}

x^{n}+ x^{n}= 2x^{n}x^{2n}

2^{n}+ 2^{n}= 2^{n+1}

In computer science, all logarithms are to base 2 unless specified otherwise.

**DEFINITION: ***x ^{a}* =

Several convenient equalities follow from this definition.

Some other useful formulas, which can all be derived in a similar manner, follow.

loga/b= loga- logb

log(a) =^{b}bloga

logx<xfor allx> 0

log 1 = 0, log 2 = 1, log 1,024 = 10, log 1,048,576 = 20

The easiest formulas to remember are

In the latter formula, if 0 < *a* < 1, then

and as *n* tends to , the sum approaches 1/(1 -*a*). These are the "geometric series" formulas.

We can derive the last formula for in the following manner. Let *S* be the sum. Then

S= 1 +a+a^{2}+a^{3}+ a^{4}+a^{5}+ . . .

aS=a+a^{2}+a^{3}+a^{4}+a^{5}+ . . .

S - aS = 1

We can use this same technique to compute , a sum that occurs frequently. We write

Subtracting these two equations yields

Another type of common series in analysis is the arithmetic series. Any such series can be evaluated from the basic formula.

The next two formulas pop up now and then but are fairly infrequent.

When *k* = -1, the latter formula is not valid. We then need the following formula, which is used far more in computer science than in other mathematical disciplines. The numbers, *H*_{N}, are known as the harmonic numbers, and the sum is known as a harmonic sum. The error in the following approximation tends to *y* 0.57721566, which is known as *Euler's constant*.

These two formulas are just general algebraic manipulations.

We say that *a* is congruent to *b* modulo *n*, written *a* *b*(mod *n*), if *n* divides *a* - *b*. Intuitively, this means that the remainder is the same when either *a* or *b* is divided by *n*. Thus, 81 61 1(mod 10). As with equality, if *a* *b* (mod *n*), then *a* + *c* *b* + *c*(mod *n*) and *a d* *b d* (mod *n*).

A proof by induction has two standard parts. The first step is proving a *base case*, that is, establishing that a theorem is true for some small (usually degenerate) value(s); this step is almost always trivial. Next, an *inductive hypothesis* is assumed. Generally this means that the theorem is assumed to be true for all cases up to some limit *k*. Using this assumption, the theorem is then shown to be true for the next value, which is typically *k* + 1. This proves the theorem (as long as *k* is finite).

As an example, we prove that the Fibonacci numbers, *F*_{0} = 1, *F*_{1} = 1, *F*_{2} = 2, *F*_{3} = 3, *F*_{4} = 5, . . . , *F _{i}* =

F+ 1=_{k }F+_{k}F-1_{k}

by the definition, and we can use the inductive hypothesis on the right-hand side, obtaining

F+1 < (5/3)_{k}+ (5/3)^{k}-1^{k}

< (3/5)(5/3)+1 + (3/5)^{k}^{2}(5/3)+1^{k}

< (3/5)(5/3)+1 + (9/25)(5/3)^{k}+1^{k}

F+1 < (3/5 + 9/25)(5/3)_{k}+1^{k}

< (24/25)(5/3)+1^{k}

< (5/3)+1^{k}

As a second example, we establish the following theorem.

Applying the inductive hypothesis, we obtain

The statement *F _{k}*

Proof by contradiction proceeds by assuming that the theorem is false and showing that this assumption implies that some known property is false, and hence the original assumption was erroneous. A classic example is the proof that there is an infinite number of primes. To prove this, we assume that the theorem is false, so that there is some largest prime *p _{k}*. Let

N=p_{1}p_{2}p_{3}^{. . . }p+ 1_{k}

int

f( int x )

{

/*1*/ if ( x = 0 )

/*2*/ return 0;

else

/*3*/ return( 2*f(x-1) + x*x );

}

Most mathematical functions that we are familiar with are described by a simple formula. For instance, we can convert temperatures from Fahrenheit to Celsius by applying the formula

C = 5(F- 32)/9

These considerations lead to the first two fundamental rules of recursion:

1. *Base cases*. You must always have some base cases, which can be solved without recursion.

int

bad( unsigned int n )

{

/*2*/ return 0;

else

/*3*/ return( bad (n/3 + 1) + n - 1 );

}

Suppose we have a positive integer, *n*, that we wish to print out. Our routine will have the heading *print_out*(*n*). Assume that the only I/O routines available will take a single-digit number and output it to the terminal. We will call this routine *print_digit*; for example, *print_digit*(4) will output a 4 to the terminal.

*The term *procedure* refers to a function that returns *void*.

Let us prove (somewhat) rigorously that the recursive number-printing program works. To do so, we'll use a proof by induction.

*The recursive number-printing algorithm is correct for n * 0.

void

print_out( unsigned int n ) /* print nonnegative n */

{

if( n<10 )

print_digit( n );

else

{

print_out( n/10 );

print_digit( n%10 );

}

}

3. *Design rule*. Assume that all the recursive calls work.

When writing recursive routines, it is crucial to keep in mind the four basic rules of recursion:

1. *Base cases*. You must always have some base cases, which can be solved without recursion.

3. *Design rule*. Assume that all the recursive calls work.

The fourth rule, which will be justified (along with its nickname) in later sections, is the reason that it is generally a bad idea to use recursion to evaluate simple mathematical functions, such as the Fibonacci numbers. As long as you keep these rules in mind, recursive programming should be straightforward.

1.1 Write a program to solve the selection problem. Let *k* = *n*/2. Draw a table showing the running time of your program for various values of *n*.

1.2 Write a program to solve the word puzzle problem.

1.3 Write a procedure to output an arbitrary real number (which might be negative) using only *print_digit* for I/O.

1.4 C allows statements of the form

#includefilename

1.5 Prove the following formulas:

1.6 Evaluate the following sums:

1.9 Let *F _{i}* be the Fibonacci numbers as defined in Section 1.2. Prove the following:

**c. Give a precise closed-form expression for *F _{n}*.

1.10 Prove the following formulas:

There are many good textbooks covering the mathematics reviewed in this chapter. A small subset is [1], [2], [3], [11], [13], and [14]. Reference [11] is specifically geared toward the analysis of algorithms. It is the first volume of a three-volume series that will be cited throughout this text. More advanced material is covered in [6].

Throughout this book we will assume a knowledge of C [10]. Occasionally, we add a feature where necessary for clarity. We also assume familiarity with pointers and recursion (the recursion summary in this chapter is meant to be a quick review). We will attempt to provide hints on their use where appropriate throughout the textbook. Readers not familiar with these should consult [4], [8], [12], or any good intermediate programming textbook.

General programming style is discussed in several books. Some of the classics are [5], [7], and [9].

1. M. O. Albertson and J. P. Hutchinson, *Discrete Mathematics with Algorithms*, John Wiley & Sons, New York, 1988.

2. Z. Bavel, *Math Companion for Computer Science*, Reston Publishing Company, Reston, Va., 1982.

3. R. A. Brualdi, *Introductory Combinatorics*, North-Holland, New York, 1977.

4. W. H. Burge, *Recursive Programming Techniques*, Addison-Wesley, Reading, Mass., 1975.

5. E. W. Dijkstra, *A Discipline of Programming*, Prentice Hall, Englewood Cliffs, N.J., 1976.

6. R. L. Graham, D. E. Knuth, and O. Patashnik, *Concrete Mathematics*, Addison-Wesley, Reading, Mass., 1989.

7. D. Gries, *The Science of Programming*, Springer-Verlag, New York, 1981.

8. P. Helman and R. Veroff, *Walls and Mirrors: Intermediate Problem Solving and Data Structures*, 2d ed., Benjamin Cummings Publishing, Menlo Park, Calif., 1988.

9. B. W. Kernighan and P. J. Plauger, *The Elements of Programming Style*, 2d ed., McGraw- Hill, New York, 1978.

10. B. W. Kernighan and D. M. Ritchie, *The C Programming Language*, 2d ed., Prentice Hall, Englewood Cliffs, N.J., 1988.

11. D. E. Knuth, *The Art of Computer Programming, Vol. 1: Fundamental Algorithms*, 2d ed., Addison-Wesley, Reading, Mass., 1973.

12. E. Roberts, *Thinking Recursively*, John Wiley & Sons, New York, 1986.

13. F. S. Roberts, *Applied Combinatorics*, Prentice Hall, Englewood Cliffs, N.J., 1984.

14. A. Tucker, *Applied Combinatorics*, 2d ed., John Wiley & Sons, New York, 1984.