CSCE 6933: Topics in Computational Mathematics - Fall 2012

Instructor: Paul Tarau, Associate Professor - see my home page for contact info and office hours 

Description and Objectives:

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

Syllabus

·         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.

·         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

·         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

·         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

·         Bijective Base-N numbering systems

·         Conway’s Surreal Numbers

·         Symbolic Arithmetic Computations and Arbitrary Length Integers

·         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

Prerequisites: good mathematical background, some experience with a functional programming language,
                       some background in Algorithm Analysis, Complexity Theory and Theoretical Computer Science

Evaluation:

Resources: