CSCE 6933: Topics in Computational Mathematics - Fall 2011

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

E-mail : t a r a u@cs.unt.edu
WWW : http://www.cs.unt.edu/~tarau
Address: Department of Computer Science, University of North Texas, P.O. Box 311366, Denton, Texas 76203, USA
Phone : Tel : +1-940-565-2806, +1-940-565-2767
Fax : +1-940-565-2799

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

·         Coq: Inductive Definitions, Calculus of Constructions, theorem proving with proof assistants

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

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

 

Assignment due Nov 21: Write a Mathematica algorithm that finds in a given directed graph all the subgraphs isomorphic to a given “query” graph.

 

Assignment due Dec 5: Write a Mathematica or Haskell program that finds the path associated to a rational number in the Calkin-Wilf tree. Then, using the binary representation of  paths interpreted as natural numbers, define operations on N that mimic the commutative field structure of Q (+,-,*,/). Assuming that something like 5 represents the path 101 which brings you to 5/3 in the CW tree and 6 represents the path 110 that brings you to 3 / 4, then the result of 5 ‘+’ 6 should be 5/3 + 3 / 4 =  29/12 from which you should be able to recover the path to the root of the CW tree and then the natural number we consider the ‘result’ of 5 ‘+’ 6.

 

Final Exam:

 

Answer 2 out of the following 3 questions (20 points each) and submit your answer by email to tarau@cs.unt.edu before 1:00pm Sunday Dec 11.

 

We will discuss and grade your solutions during the final exam session in the classroom, on Monday 5:00pm. Please bring your solutions to class on a USB drive.

 

Completing the SETE evaluation for the course adds 4 bonus points to your grade.

 

Q1.

The following Haskell program (part of the solution

of our last assignment) implements an

efficient walk over the Calkin-Wilf tree

both ways, from N to Q+ and back.

Illustrate with at least 10 examples that the 2 functions

work correctly. Write an equivalent program in

Mathematica or Coq.

 

-- N->Q+ to rationals, via CW transform

n2q 0 = (1,1)

n2q x | odd x =  (f0,f0+f1) where

  (f0,f1)=n2q (div (pred x) 2)

n2q x | even x  = (f0+f1,f1)

  where (f0,f1)=n2q (pred (div x 2))

 

-- Q+->N from rationals, fast, using CW tree backwards

q2n (1,1) = 0

q2n (a,b) = f ordrel where

  ordrel = compare a b

  f GT = 2*(q2n (a-b,b))+2

  f LT = 2*(q2n (a,b-a))+1

 

Q2.

Implement the PageRank algorithm (http://en.wikipedia.org/wiki/PageRank)

using Mathematica or Haskell. You can use a library

module or your own representation of a graph. In case you chose Mathematica, you

have to actually implement the algorithm, not just call a library function.

 

Q3.

DNA-sequences (http://en.wikipedia.org/wiki/DNA) are described using four bases a 4 base alphabet: adenine (abbreviated A), cytosine (C), guanine (G) and thymine (T). In a programming language of your choice, define a bijection between natural numbers and DNA sequences and use it to generate random DNA sequences.