MSC-3MB, Box 30001
New Mexico State University
Las Cruces, NM 88003
MSC-CS, Box 30001
New Mexico State University
Las Cruces, NM 88003
MSC-3MB, Box 30001
New Mexico State University
Las Cruces, NM 88003
MSC-3MB, Box 30001
New Mexico State University
Las Cruces, NM 88003
MSC-CS, Box 30001
New Mexico State University
Las Cruces, NM 88003
Visit our new web site for projects written as part of the Phase II expansion grant.
Any instructor of computer science or mathematics is invited to test any of our projects in the classroom for courses in discrete mathematics, combinatorics, graph theory, algorithm design, logic, abstract algebra, foundations of mathematics, or the history of mathematics. Here is a list of projects to be written under a Phase II expansion proposal. For further information, contact either Jerry Lodder or Desh Ranjan above.
This site offers written curricular materials, based on primary historical sources, for beginning and advanced undergraduate courses in discrete mathematics and computer science. Such courses, which often cover combinatorics, deductive reasoning (logic) and algorithmic thought, draw a variety of majors, ranging from computer science, mathematics, the physical sciences and engineering to secondary education. Traditional methods of instruction follow ``The Modern American Discrete Mathematics Text,'' which although thorough and mathematically precise, present the material as a fast-paced news reel of facts and formulae, often memorized by the students, with the text itself offering only passing mention of the motivating problems and original work which eventually found resolution in modern concepts such as induction, recursion, or algorithm.
Our site offers written projects for a course in discrete or finite mathematics with the projects containing excerpts from primary sources for students to read along with a sequence of directed questions which illuminate how the source develops key mathematics ideas. Particular advantages of the historical approach include providing context and direction for the subject matter, honing the students' verbal and deductive skills through reading the original work of some of the greatest minds in history, and the rediscovery of the conceptual roots common to discrete mathematics and computer science. Additionally, students practice the skill of moving from verbal descriptions of problems to precise mathematical formulations, and must often recognize an organizing concept for a detailed procedure. Such abilities are vital not only for mathematics and the sciences, but especially today for software engineers, who must translate a verbal request into precise code changes, and then realize what effect these changes will have on the global structure of a large program or a body of interacting programs.
When working on an historical project, a student spends one to two weeks, either as an individual or in a group, writing a detailed paper, with two or three projects together counting for a significant percentage (about 50%) of the course grade, and often taking the place of two one-hour examinations. A written paper allows the students to organize their own thoughts, react to the original sources in much the same way as the contemporaries of the historical masterpiece, and explore the development of ground-breaking ideas. The written historical project builds naturally on the idea of calculus projects [CG], used extensively here at New Mexico State University.
To exemplify the historical approach, what better way to see induction in action than to read from Blaise Pascal's (1623--1662) ``Treatise on the Arithmetical Triangle'' [P1], in which Pascal notices a pattern in the ratio between consecutive entries in the same base of his triangle (Pascal's Twelfth Consequence), and then claims that the pattern holds in every base of the triangle, since if it holds in a given base, then it persists to the next base. It would be a wonderful exercise for students to read Pascal's original statement, explore its truth with a few concrete numerical values, and then grapple with the logic behind what today is known as induction. The students (and teachers) witness first hand the genesis of abstract concepts, and with a bit of historical background, realize that Pascal was motivated by solving actual problems of his day, such as computing the odds in a game of chance, or finding the summation of powers, with the eventual goal of computing area under curves. Another advantage to reading Pascal's original work is that the ratios between consecutive entries that he derives lead to the modern formula for binomial coefficients, a formula which is often announced today without exploration of its historical origin.
By contrast, modern textbooks often give an abstract logical formulation of induction first, and then, as homework, simply ask the students to verify statements the (textbook) author already knows to be true, such as the sum of i2 from i = 1 to n is (1/3)n3 + (1/2)n2 + (1/6)n, without mentioning why or how anyone discovered or originally proved this formula.
It is being increasingly recognized that an historical point of view can provide context, motivation and direction to mathematics courses. For instance, an historical perspective is being advocated in teaching calculus [K1, K2, R1, R2], while original source materials are being incorporated in a variety of ways into calculus instruction [L1, O], and new texts are emphasizing the importance of studying original sources [BG, Ca, F, K3, K4, LP]. Also see the web page ``Teaching with Original Historical Sources in Mathematics''. This site, however, focuses on historical projects for undergraduate discrete mathematics courses. While there are presently excellent accounts of the history of algorithms such as [Ch], or the history of logic [Da, Gr], such texts do not focus on the needs of undergraduates and contain no curricular materials ready for classroom use.
The benefits of an historical point of view have been explained very convincingly by Miguel de Guzmán, President of the International Commission on Mathematical Instruction, in his talk at the 7-th International Congress on Mathematics Education [Gu]:
WHAT THE KNOWLEDGE OF THE HISTORY OF MATHEMATICS AND OF THE PARTICULAR SUBJECT CAN OFFER US:
If a series of any number of lines be given, which exceed one another by an equal amount, and the difference be equal to the least, and if other lines be given equal in number to these, and in quantity to the greatest, the squares on the lines equal to the greatest, plus the square on the greatest and the rectangle contained by the least and the sum of all those exceeding one another by an equal amount will be the triplicate of all the squares on the lines exceeding one another by an equal amount.
The project then asked the students to rewrite the statement using symbolic logic. Such an exercise meshes well with a first chapter on logic in many discrete mathematics texts, which often include homework problems such as ``Write the statement `If it is cold and raining, then I will stay home' in symbols, using the predicates, P: It is cold, Q: It is raining, R: I will stay home.'' A particular drawback of modern textbooks is their lack of motivation, perspective and context. Why not apply symbolic logic to the very statements which historically drove the development of mathematics, allowing the students to hone their verbal and deductive skills on significant problems?
A second project, ``In the Words of Archimedes II,'' built on the first by asking students to verify Archimedes' statement about the sums of squares using ideas from his original proof, a proof which did not involve induction. A third project, ``In the Words of Pascal,'' presented Pascal's bold statement about the sums of arbitrary powers taken from a translation of Sommation des Puissances Numériques [P2], and asked the students to prove, now using induction, that the sum of ik from i = 1 to n is a polynomial in n of degree k + 1. Although the project did not ask for the coefficients of this polynomial in explicit form, a few students became fascinated with this problem, and essentially anticipated the first three Bernoulli numbers. Homework problems in a standard text almost never elicit such a response from students. A future project in this direction will investigate Jakob Bernoulli's (1654--1705) original work on summations [Be].
Guram Bezhanishvili has written a major project on Georg Cantor's (1845--1918) revolutionary ideas concerning infinite sets using excerpts from Cantor's memoir Contributions to the Founding of the Theory of Transfinite Numbers [Cn]. The project, ``Are All Infinities Created Equal?'' (pdf file) (ps file), begins by asking the students to identify certain properties of ``naive set theory'' as explicated by Cantor, and then write these observations using modern notation. The project continues with a comparison of the cardinality of various infinite sets, such as the set of rational numbers, and the set of real numbers in the interval [0, 1], and concludes with the observation that certain infinite sets are larger than others (2 to the aleph naught is greater than aleph naught), a paradigm-breaking idea about the infinite.
Additionally, Jerry has introduced logic in a beginning discrete mathematics course [L2] via Alan Turing's (1912--1954) original paper ``On Computable Numbers with an Application to the Entscheidungsproblem'' [T]. Through the first project, ``An Introduction to Turing Machines'' (pdf file) (ps file), the students witness an idea which is the forerunner of a programmable computer, a Turing machine, and in the second, ``Turing Machines, Induction and Recursion'' (pdf file) (ps file), they observe how the concept of recursion arises naturally when writing a Turing machine to perform a basic operation such as multiplication of positive integers. Moreover, induction is used to verify that the output of the machine is correct. At the conclusion of the Turing projects, a student from an under represented minority remarked: ``I thought this course would just be about numbers, but instead, I learned how computers started.'' Another student, when describing the projects, claimed ``That's how I learn.''
The first two Turing projects deal with the construction and design of Turing machines to perform certain computational tasks, and remain at an introductory level, primarily to serve the needs of a beginning course in discrete mathematics. Of course, Turing's original motivation was to solve Hilbert's decision problem, which Turing masterfully does in [T], and in so doing, he develops the idea of a universal computing machine (known as a compiler or an interpreter today). The third project in this sequence, ``The Universal Computing Machine'' (pdf file) (ps file), outlines Turing's logical construction of this device, and is well-suited for an intermediate or an advanced undergraduate course in logic, discrete mathematics, or computer science. A fourth project in this sequence, ``The Decision Problem'' (pdf file) (ps file), offers Turing's (negative) solution to this issue, which today has become known as the halting problem in computer science. These last two Turing projects were used recently in an intermediate discrete mathematics course, at the conclusion of which student comments reveal: ``I found the two projects to be challenging and extremely pertinent to computer science.'' ``The two projects that dealt with the Turing machines and the halting problem gave me insight and understanding of the origins of computer science.''
During the Autumn semester of 2003 Jerry Lodder developed two projects for an introductory course in discrete mathematics which trace the development of binary arithmetic from the Enlightenment to the electronic age. The first project (pdf file) (ps file) begins with Gottfried Wilhelm Leibniz's (1646--1716) work on binary numeration, offering excerpts form his 1703 publication ``Explication de l'arithmétique binaire, qui se sert des seuls caractères 0 et 1, avec des remarques sur son utilité, et sur ce qu'elle donne des anciennes figures Chinoises de Fohy,'' (An Explanation of Binary Arithmetic Using only the Characters 0 and 1, with Remarks about its Utility and the Meaning it Gives to the Ancient Chinese Figures of Fuxi) [Ge, p. 223--227] [Le]. For Leibniz, binary numbers represented a confluence of several ideas, including order, harmony, a candidate for his universal language (lingua generalis), an analogy of creation with 0 denoting nothing and 1 denoting God, and an interpretation of the ancient Chinese text of divination the Yijing (I-Ching or Book of Changes) in terms of binary numeration [Sw]. Leibniz also cites an ease of calculation with base 2 numbers, particularly for multiplication and division, which do not require the memorization of a multiplication table or methods of trial and error, as is often the case for long division in base 10.
The project continues with a brief account of the Electronic Numerical Integrator and Computer (ENIAC) developed at the University of Pennsylvania's Moore School of Electrical Engineering during the years 1943--1945, and discusses its use of base 10 arithmetic, requiring the storage of a multiplication table for numbers between zero and nine [Go]. The next generation of computing equipment, the Electronic Discrete Variable Automatic Computer (EDVAC), heavily influenced by the ideas of John von Neumann (1903--1957), performed arithmetical calculations in base 2. The project provides excerpts from von Neumann's 1945 white paper ``First Draft of a Report on the EDVAC'' [vN], in which he too cites the ease of calculation as an advantage to binary arithmetic, as well as an economy of representing numerical values with this system. Moreover, the EDVAC is a model for a ``universal computing machine'' in the sense of Turing [T]. This project, ``Binary Arithmetic: From Leibniz to von Neumann'' (pdf file) (ps file) is ideal for beginning students in discrete mathematics, particularly those with no previous knowledge of base 2 calculations.Leibniz's paper on binary arithmetic can be used to motivate and provide significant material for other topics in discrete mathematics, such as induction and divisibility properties of integers. Although these ideas are not developed in the project per se, they could be easily implemented as classroom activities after completion of the project. For example, Leibniz claims that following a study of binary numeration, ``we see the reason for the famous property of the double geometric progression in whole numbers, which states that given only one of these numbers in each degree, we can form all other whole numbers below the double of the highest degree,'' a statement which today is easily proved by induction. A present-day formulation of this property might read: Given the values 20, 21, 22, . . . , 2n, then every positive integer between 1 and 2n+1-1 inclusive can be (uniquely) expressed as a sum of these powers (with each power occurring at most once), although a modern formulation of the statement is best left to the students. Moreover, Leibniz claims that patterns occur in the binary equivalents of the perfect squares and other numbers. Asking students to identify a pattern and then conjecture a corresponding divisibility property of the integers provides a wonderful discovery exercise. For example, the second column in the binary expansion of the perfect squares is comprised entirely of zeroes, which students are encouraged to reconcile as 4 | n2 (4 divides n2) for n even, and 4 | (n2-1) for n odd. Furthermore, examining the zero in the third column for n2, n odd, leads to the conjecture that 8 | (n2-1), n odd.
The second project on binary arithmetic ``Arithmetic Backwards from von Neumann to the Chinese Abacus'' (pdf file) (ps file), builds on the first, beginning with von Neumann's claim that a high-speed vacuum tube computer performs arithmetic most efficiently in base 2. The project then proceeds in a chronologically reverse order, next examining Claude Shannon's (1916--2001) design of circuits for computations in Boolean algebra and logic. The project provides excerpts from Shannon's 1938 paper ``A Symbolic Analysis of Relay and Switching Circuits'' [Sh], and asks the students to construct the circuits necessary for binary addition. A careful study of these examples provides motivation for writing logic statements in what today is known as ``disjunctive normal form,'' a concatenation of sub-statements with the connective ``or,'' where each sub-statement contains only negations and the connective ``and.''
The project continues with the realization that writing a number in base 2 often requires many digits, and examines an alternative base that can be easily converted to base 2. Surprisingly a Chinese abacus provides the ideal tool for computations in base 16, which the students are asked to realize on their own by exploring all possible values that can be represented by bead arrangements on a single bar of this type of abacus. As an in-class activity while the project was assigned, we discussed base 10 addition and subtraction on an abacus, with the base 16 analogues of these operations left to the students. Today hexadecimal notation (base 16) is common place in computer science, and serves as shorthand for binary numbers, with the conversion between base 2 and base 16 a simple operation. With Leibniz's interest in China and the interpretation of the hexagrams of the Yijing in terms of binary numeration, the Chinese abacus provides a pleasing confluence of historical, cultural and computational ideas for the second project, particularly as a tool for place value arithmetic in a two-power base. Concerning the benefits of teaching with historical sources, at the conclusion of the course, students wrote: ``You get an understanding of why you are doing something.'' ``It ties in better, links can be made.'' ``Gives meaning to problems.'' ``We can understand why we do certain things in certain ways.''
David Pengelley has authored a project track to teach induction from Pascal's ``Treatise on the Arithmetical Triangle," (pdf file) (ps file), where Pascal proves that certain patterns occur in his triangle via a logical argument that would later become known as induction. Desh Ranjan has written ``Counting Triangulations of a Polygon," (pdf file) (ps file), which develops the sequence of Catalan numbers from a simple observation of Lamé. Desh's project contains David's translation of a letter from Lamé to Liouville, which serves as the primary source for this work. Hing Leung has completed a project (pdf file) (ps file) that outlines the reduction of two-way deterministic finite automata to one-way automata via the work of Shepherson, and builds on the notion of a Turing machine. Additionally, Guram Bezhanishvili has outlined Church's thesis using excerpts from the work of Gödel, Kleene and Turing, which establish that general recursive functions coincide with Turing computable functions (pdf file) (ps file).
The teaching community is invited to use any of the above projects in relevant mathematics or computer science courses. Typically two or three projects, chosen around a specific theme, such as Turing machines, are used in a one-semester course, with the projects counting for a significant portion (40%--50%) of the course grade. For each project the students are given one to two weeks, working as an individual or in groups of two or three, to produce a written paper addressing the issues raised in the project. Each project usually replaces an in-class examination. For further general information about the use of projects see [CG].
|1. ``Are All Infinities Created Equal?''||pdf file||ps file||latex file|
|2. ``An Introduction to Turing Machines''||pdf file||ps file||latex file|
|3. ``Turing Machines, Induction and Recursion''||pdf file||ps file||latex file|
|4. ``Turing Machines and Binary Addition''||pdf file||ps file||latex file|
|5. ``The Universal Computing Machine''||pdf file||ps file||latex file|
|6. ``The Decision Problem''||pdf file||ps file||latex file|
|♦ All Turing projects to appear in print||pdf file||ps file||latex file|
|7. ``Binary Arithmetic: From Leibniz to von Neumann''||pdf file||ps file||latex file|
|8. ``Arithmetic Backwards from von Neumann to the|
|Chinese Abacus''||pdf file||ps file||latex file|
|9. ``Treatise on the Arithmetical Triangle''||pdf file||ps file||latex file|
|10. ``Counting Triangulations of a Polygon''|
|The Mathematical Version||pdf file||ps file||latex file|
|11. ``Counting Triangulations of a Polygon''|
|The Programming Version||pdf file||ps file||latex file||figure file|
|12. ``Two-Way Deterministic Finite Automata''||pdf file||ps file||latex file|
|13. ``Church's Thesis''||pdf file||ps file||latex file|
|14. ``Euler Circuits and the Königsberg Bridge Problem ''||pdf file||ps file||latex file||figure files|
|15. ``Topological Connections from Graph Theory''||pdf file||ps file||latex file||figure files|
|16. ``Hamiltonian Circuits and Icosian Game''||pdf file||ps file||latex file||figure file|
|♦ ♦ All projects to appear in print [Ba].||pdf file|
♦ ♦ Visit our new web site for additional projects written as part of the Phase II expansion grant.
The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grant DUE-0231113, for which the authors of this web site are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
[Ba] Barnett, J., Bezhanishvili, G., Leung, H., Lodder, J., Pengelley, D., Ranjan, D., "Historical Projects in Discrete Mathematics and Computer Science" in Resources for Teaching Discrete Mathematics, Hopkins, B. (editor), Mathematical Association of America, Washington, D.C., 2009.
[BG] Berlinghoff, W., Gouvêa, F., Math through the Ages: A Gentle History for Teachers and Others, Oxton House Publishers, Farmington, Maine, 2002.
[Be] Bernoulli, J., Die Werke von Jakob Bernoulli, Naturforschende Gesellschaft in Basel, Birkhäuser Verlag, Basel, 1975.
[Ca] Calinger, R., (ed.), Classics of Mathematics, second ed., Prentice-Hall, Engelwood Cliffs, New Jersey, 1995.
[Cn] Cantor, G., Contributions to the Founding of the Theory of Transfinite Numbers, Dover, New York, 1952.
[Ch] Chabert, J-L., A History of Algorithms From the Pebble to the Microchip, Chris Weeks (trans.), Springer Verlag, New York, 1994.
[CG] Cohen, M., Gaughan, E., Knoebel, A., Kurtz, D., Pengelley, D., Student Research Projects in Calculus, Mathematical Association of America, Washington, D.C., 1992.
[Da] Davis, M., The Universal Computer: The Road From Leibniz to Turing, W. W. Norton & Company, New York, 2000.
[Di] Dijksterhuis, E., Archimedes , Princeton University Press, Princeton, New Jersey, 1987.
[F] Fauvel, J., Van Maanen, J., History in Mathematics Education, Kluwer, Boston, 2000.
[Ge] Gerhardt, C. I., (ed.), G. W. Leibniz Mathematische Schriften, Vol. VII, Olms, Hildesheim, 1962.
[Go] Goldstine, H. H., The Computer from Pascal to von Neumann, Princeton University Press, Princeton, New Jersey, 1972.
[Gr] Grattan-Guinness, I., The Search for Mathematical Roots, 1870--1940: Logics, Set Theories and The Foundations of Mathematics from Cantor through Russell to Gödel, Princeton University Press, Princeton, 2000.
[Gu] Guzmán, M. de, ``Origin and Evolution of Mathematical Theories: Implications for Mathematical Education," Newsletter of the International Study Group on the History and Pedagogy of Mathematics, # 28 (March 1993) 2--3.
[K1] Katz, V., ``An Historical Approach to Precalculus and Calculus," Newsletter of the Humanistic Mathematics Network, # 6, May 1991.
[K2] Katz, V., ``Using the History of Calculus to Teach Calculus," Science and Education, 2, # 3, Fall 1993.
[K3] Katz, V., A History of Mathematics: An Introduction, second ed., Addison-Wesley, New York, 1998.
[K4] Katz, V., (ed.), Using History to Teach Mathematics, Mathematical Association of America, Washington, D.C., 2000.
[LP] Laubenbacher, R., Pengelley, D., Mathematical Expeditions: Chronicles by the Explorers, Springer-Verlag, New York, 2000.
[Le] Leibniz, G. W., ``Explication de l'arithmétique binaire, qui se sert des seuls caractères 0 et 1, avec des remarques sur son utilité, et sur ce qu'elle donne des anciennes figures Chinoises de Fohy,'' Memoires de l'Académie Royale des Sciences, 3 (1703) 85--89.
[L1] Lodder, J., ``Curvature in the Calculus Curriculum,'' American Mathematical Monthly, 110 , 7 (2003) 593--605.
[L2] Lodder, J., ``Introducing Logic via Turing Machines,'' in From Calculus to Computers: Using the Last 200 Years of Mathematics History in the Classroom, A. Shell-Gellasch, D. Jardine (eds.), Mathematical Association of America, Washington, D.C., 2005, 125--133.
[O] Otero, D., ``An Historical Calculus Course for Liberal Arts Students'', Newsletter of the International Study Group on the History and Pedagogy of Mathematics, # 28 (March 1993), 7--9.
[P1] Pascal, B., ``Treatise on the Arithmetical Triangle,'' in Great Books of the Western World, M. Adler (ed.), Encyclopedia Britannica Inc., Chicago, 1991.
[P2] Pascal, B., Oeuvres, L. Brunschvieg (ed.), Paris, 1908--14; Kraus Reprint, Vaduz, Liechtenstein, 1976, Vol. III, 341--367.
[R1] Rickey, F., ``My Favorite Ways of Using History in Teaching Calculus,'' in Learn From the Masters, F. Swetz, J. Fauvel, O. Bekken, B. Johansson, V. Katz, (eds.), Mathematical Association of America, Washington, D.C., 1995, 123--134.
[R2] Rickey, F., ``The Necessity of History in Teaching Mathematics,'' in Vita Mathematica: Historical Research and Integration with Teaching, R. Calinger (ed.), Mathematical Association of America, Washington, D.C., 1996, 251--256.
[Sh] Shannon, C. E., ``A Symbolic Analysis of Relay and Switching Circuits,'' Transactions American Institute of Electrical Engineers, 57 (1938) 713--723.
[Sw] Swetz, F. J., ``Leibniz, the Yijing, and the Religious Conversion of the Chinese,'' Mathematics Magazine, 76, No. 4 (2003) 276--291.
[T] Turing, A., ``On Computable Numbers with an Application to the Entscheidungsproblem,'' Proceedings of the London Mathematical Society, 42 (1936) 230--265.
[vN] von Neumann, J., ``First Draft of a Report on the EDVAC,'' in From ENIAC to UNIVAC: An Appraisal of the Eckert-Mauchly Computers, N. Stern, Digital Press, Bedford, Massachusetts, 1981, 177--246.