Learning Discrete Mathematics and Computer Science
via Primary Historical Sources

Available projects

Search Projects based on Courses Choose One Abstract Algebra Algorithms Automata and Formal Languages Calculus Combinatorics Data Structures Discrete Mathematics Graph Theory Intro to Computer Science Mathematical Logic Programming Languages Theory of Computation

Sixteen projects developed before 2008 are posted at http://www.math.nmsu.edu/hist_projects/

Projects developed since 2008 are listed below. With each project there is a list of suggested courses where the project may be used and a list of topics covered in the project.

• Project 1: Sums of numerical powers in discrete mathematics: Archimedes sums squares in the sand 10/7/2010 blog

  Courses: Discrete mathematics (lower division), Calculus

  Topics: Summations, closed formulas, Riemann sums, areas, inequalities, telescoping sums, mathematical induction (optional), systems of linear equations (optional), recursive computation (optional)

• Project 2: Figurate numbers and sums of numerical powers: Fermat, Pascal, Bernoullii 10/8/2010 blog

  Courses: Combinatorics, Discrete mathematics (upper division)

  Topics: sums of powers, figurate numbers, binomial coefficients, combination numbers, Pascal's triangle, Bernoulli numbers, recursive definitions and computation, summations and inequalities, counting and geometry, mathematical induction, interplay between discrete sums and calculus.

• Project 3: Deduction through the Ages: A History of Truth Revised: 9/15/2009 blog

  Courses: An introductory discrete mathematics course, a course in discrete mathematics for beginning computer science majors.

  Topics: Propositional logic, truth tables, the truth table of an "if-then" statement, elementary logical equivalences in propositional logic.

• Project 4a: Origins of Boolean Algebra in the Logic of Classes: George Boole, John Venn and C. S. Peirce blog

  Courses: Discrete Mathematics (introductory)

  Topics: elementary set operations (union, intersection, relative difference, symmetric difference) and their (algebraic) properties, Venn diagrams, relation of set operations to standard language use, relation of elementary set operations to boolean algebra, inverse operations (optional), issues related to mathematical notation (optional), changing standards of rigor and proof (optional)

• Project 4b: Boolean Algebra as an Abstract Structure: Edward V. Huntington and Axiomatization

  Courses: Discrete Mathematics (introductory or intermediate), Model Theory, Abstract Algebra

  Topics: axioms for boolean algebra, boolean algebra properties (with proofs), two-valued model of boolean algebra, axiomatization, consistency, independence

• Project 4c: Applications of Boolean Algebra: Claude Shannon and Circuit Design

  Courses: Discrete Mathematics (introductory) for mathematics or computer science majors

  Topics: boolean algebra axioms and properties, application of boolean algebra to design and simplification of circuits, simplification of boolean expressions, disjunctive normal form, two-valued model of boolean algebra

• Project 5: Euclid's Algorithm for the Greatest Common Divisor (10/1/2010) blog

  Courses: Discrete Mathematics (lower division), Introduction to Computer Science

  Topics: Basic division properties of natural numbers, divisors and common divisors, greatest common divisor, basic reasoning, arguments and proofs, formal proof by induction (optional), basic algorithm design and formal description (pseudocode), reasoning about correctness of algorithms.

• Project 6: Algorithms, Recursion and Induction: Euclid and Fibonacci

  Courses: Discrete mathematics (sophomore level), Algorithms (junior/senior level)

  Topics: Recursion and basic algorithm design using recursive thinking, comparing recursion with iteration, greatest common divisor, Fibonacci numbers, formal proof by induction, analysis of runtime and space complexity of algorithms including recursive algorithms, recurrence relations, dynamic programming.

• Project 7: Striving for efficiency in Algorithms: Sorting

  Courses: Data Structures and Algorithms

  Topics: Sorting, quicksort, insertion sort, efficiency of algorithms, stack data structure.

• Project 8: Discovery of Huffman Codes

  Courses: Data Structures and Algorithms

  Topics: Huffman encoding, greedy algorithm, prefix-free code, optimal code, unit of information, amount of information, binary tree

• Project 9: Networks and Spanning Trees (10/8/2010) blog

  Courses: Graph Theory, Combinatorics, Analysis of Algorithms

  Topics: Graphs, Trees, Enumeration of labeled trees, minimal spanning trees, Cayley's formula and Prufer's symbols for labeled trees, Boruvka's algorithm for finding a minimial spanning tree.

• Project 10: Project on Program Correctness (11/19/2010)

  Courses: Algorithms, Data Structures, Programming Languages

  Topics: Correctness, Partial Correctness, Algorithms

• Project 11: Abstract awakenings in algebra: Early group theory in the works of Lagrange, Cauchy, and Cayley (8/19/2010)

  Courses: Abstract Algebra

  Topics: roots of unity, permutations, definition and elementary properties of a group, symmetric groups, cyclic groups, Cayley tables, Lagrange's Theorem, group isomorphisms, classification of groups of small order, cosets

• Project 12: Regular Languages and Finite Automata (9/16/2010)

  Courses: Automata and Formal Languages, Theory of Computation

  Topics: Regular Languages, finite automata, regular expressions, regular events, Kleene's theorem, Kleene's star operation

• Project 13: Henkin's Method and the Completeness Theorem (11/26/2010)

  Courses: Mathematical Logic (advanced)

  Topics: syntax of first-order logic, axioms and rules of inference, formal concept of proof, deduction theorem, satisfiability and validity, soundness, Henkin's method, completeness, Loewenheim-Skolem theorem, first-order logic with equality

• Project 14: Peano Arithmetic

  Courses: Mathematical Logic (advanced)

  Topics: Peano postulates, consistency and independence of Peano postulates, recursive definition of addition and multiplication, properties of addition and multiplication, first-order arithmetic

• Project 15: Godel's Incompleteness Theorem

  Courses: Mathematical Logic (advanced)

  Topics: Paradoxes in mathematics, axiomatization of mathematics, first-order languages and first-order theories, models, Peano arithmetic (PA), undefinability of thruth (Tarski's theorem), incompleteness of PA (Goedel's first incompletenss theorem), unprovability of consistency (Goedel's second incompleteness theorem).

• Project 16: Undecidability of First-Order Logic

  Courses: Mathematical Logic (advanced)

  Topics: Different formulations of the decision problem, models, isomorphic models, intended model, one-way infinite line, two-way infinite line, upper half-plane, Turing machines, halting problem, undecidability of first-order satisfiability

• Project 17: An Introduction to Naive Set Theory and the Concept of Infinity: Guided by an Essay of Richard Dedekind (5/11/2009)

  Courses: Discrete/Finite Mathematics (sophomore/junior level)

  Topics: Sets, Union, Intersection, Functions (composition, inverse, injective, and forward image), Set Equivalence, Infinity

• Project 18: Introduction to Symbolic Logic (8/15/2010)

  Courses: An introductory course in discrete mathematics, a course in discrete mathematics for beginning computer science majors.

  Topics: Propositional logic, logical connectives, logical equivalence, truth tables, tautologies, inference rules, predicate logic, individual variables and predicates, universal and existential quantifiers, logical equivalence of quantified statements, inference rules in predicate logic.