Some Materials for Discrete Mathematics

Lee Lady


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 ]