## Some Materials for Discrete Mathematics

```
```

### Comments on Math 301

```
```
A lot of the files listed below are in PDF (Adobe Acrobat) format. Alternate versions are in DVI format (produced by TeX; see see here for a DVI viewer provided by John P. Costella) and postscript format (viewable with ghostscript.) Some systems may have some problem with certain of the documents in dvi format, because they use a few German letters from a font that may not be available on some systems. (Three alternate sites for DVI viewers, via FTP, are CTAN, Duke, and Dante, in Germany.)

### An algorithm for solving linear Diophantine equations

(Click here for dvi format.)
(Click here for Postscript.)
```
```

### The Chinese Remainder Theorem

(Click here for dvi format.)
(Click here for Postscript.)
```
```

### The Division Algorithm

(Click here for dvi format.)
(Click here for Postscript.)
```
```

### Mathematical induction and recursive algorithms.

(Click here for dvi format.)
(Click here for Postscript.)

In a recursive algorithm, one computes the value of a function for a particular value of N by assuming that the function's value is already known for N-1.
Mathematical induction is the same idea, except that instead of computing a numerical value one is trying to establish the truth of a statement about N. One proves that a statement is true for N by assuming that its truth for N-1 has already been established.
Here, I illustrate this analogy by stating two classic theorems which are often proved by induction, and then giving comparable recursive algorithms.

```
```

### Change of base to Cantor representation

(Click here for dvi format.)
(Click here for Postscript.)
```
```

### Dijkstra's algorithm for shortest path

(Click here for dvi format.)
(Click here for Postscript.)
```

```

### The Problem of the Twelve Coins

(Click here for dvi format.)
(Click here for Postscript.)
```
```

### Amortization

(Click here for dvi format.)
(Click here for Postscript.)

One wants to borrow a certain amount of money for y years at a given annual percentage rate. How does one compute the monthly payment?
The theory of linear recurrence relations enables one to find the answer to this question.

```

```
[ Linear Algebra | Miscellaneous Courses | HOME ]