An advanced course exploring a selection of research topics in Computational Mathematics, as well as tools for automating various aspects of the field.

- Tools for Computational Mathematics

· Haskell: typed lambda calculus, basic category theory, infinite objects, polymorphism and type classes

· Mathematica: language and libraries, visualization techniques, the Wolfram Alpha online resource

· Tools for Data Type Transformations and Symbolic Computation - slides

· Packages and tools for Combinatorial Generation of sets, permutations, partitions, trees, graphs etc.

- Number theory and applications to cryptography

· Fundamental Theorem of Arithmetic, Primes, Factoring algorithms

· Finite permutation groups, cycle representations, Lehmer codes, maximal order in the symmetric group

· Recursion equations, Some Famous Integer Sequences

· Stern-Brocot and Calkin-Wilf trees, bijections between N and Q

· Computing integer and set partitions

· Modular arithmetic, Discrete Logarithms, Finite Fields, Block ciphers

· Pseudo-Random Generators, Automorphisms of N and Stream Ciphers

· Homomorphic Encryption with applications to election privacy and confidential cloud computing

- Computability, Foundations of Mathematics and Computer Science

· Inductive Definitions, Peano’s Axioms, Presburger arithmetic, ZF-set theory

· Using proof assistants to model simple axiom systems

· Goedel’s Theorems, Incompleteness, Halting Problem, Turing hierarchy, Weak arithmetics

· Ordinals: arithmetic, tree representations, applications to termination analysis

· Goedel Numberings of pairs, finite sequences, trees, graphs, term algebras

· Bijective mappings between natural numbers and rational numbers, Calkin-Wolf and Stern-Brocot trees

· S, K combinators and other minimalist Turing equivalent formalisms

· Kolmogorov-Chaitin complexity, self-delimiting codes

- Computational Aspects of Boolean Logic, Circuits and Graphs

· SAT-solvers, DPLL, Schaeffer’s Dichotomy Theorem, Polynomial algorithms for 2SAT and HornSat

· The Post Lattice, clones, NP-completeness

· Circuit Synthesis Algorithms

· A selections of Graph Theoretical Algorithms

· Application: Subgraph Isomorphism and Information Retrieval

- Unconventional Numbering Systems

· Bijective Base-N numbering systems

· Conway’s Surreal Numbers

· Symbolic Arithmetic Computations and Arbitrary Length Integers

- Experimental Techniques for Open Problems in Computational Mathematics

· Hilbert’s Problems

· The Collatz Conjecture – equivalent formulations, generalizations, fractal representations, Goodstein’s Theorem

· The Riemann Conjecture and equivalent formulations – connecting Number Theory and Complex Analysis

· Predicate Logic and P-NP separation

- Other topics based on students’ interests

some background in Algorithm Analysis, Complexity Theory and Theoretical Computer Science

- Team coding projects and research paper presentations 60%
- Individual Exam: 40%

- There are now computers in the F205 Help Lab that
have Mathematica installed and working properly.

You can log in with your EUID and password. You can also get a discounted individual copy here. - Haskell compiler GHC and Prelude library sources, IO, some packages 1math 2species and the Hask category
- R. Harper’s draft book at: http://www.cs.cmu.edu/~rwh/plbook/
- D. Knuth’s TAOCP vol 4, and fasc. on boolean evaluation
- A fine online combinatorics book. A nice combinatorics package included in Mathematica
- Scholarpedia articles on Computational Type Theory and Matiyasevich's theorem/Hilbert’s 10-th problem
- Wikipedia articles: 1NP, 2Post, 3Kolmogorov, 4SKI, 5DPLL, 6ZF, 7Sur, 8Peano, 9ArithH, 10Goedel, 11BijN, 12LSyn, 13Schaefer
- MathWorld articles: 1Collatz, 2Riemann, 3Cell, 4Turing
- Mathematica demos: http://library.wolfram.com/infocenter/Demos
- Papers and code on data type isomorphisms and symbolic computations
- An MIT primer on Math and CSs
- Riemann hypothesis and primes demo
- A very nice paper by Ramanujan on the number of prime factors
- Various other online resources.