Ebook: Computer science with Mathematica: theory and practice for science, mathematics, and engineering

As a symbolic programming language, and as one that can effectively emulate most programming paradigms, Mathematica is unequaled. In this book, the author makes this abundantly clear as he takes the reader through a sampling of the power of Mathematica, with the target reader being a computer scientist without a knowledge of Mathematica.

After a very brief review of computer concepts and architectures in chapter 1, the author begins chapter 2 with an overview of the syntax of Mathematica. The most helpful points in this chapter were: 1. How to implement piecewise-defined functions. 2. Pure functions. 3. The ability of Mathematica to do functional programming via functional operations. 4. Normal expressions and atoms.

Chapter 3 is an introduction to iteration and recursion. The author begins the chapter by showing how to use rule-based or recursive programs to construct a program to calculate the greatest common divisor of two integers. He is careful to note however that the use of recursion may be inefficient and so he shows how to convert the program to one that uses loop iteration. The contrast in inefficiency between iterative and recursive programs is illustrated again in the next section which deals with the Collatz problem. An iterative computation of the Collatz sequence is given, and the author encourages the use of loops and not recursion, to obtain efficient programs. The author shows how to use loop invariants to test program correctness for loops. The engineer/physicist reader will appreciate the application of iterative methods to the solution of ordinary differential equations.

In chapter 4, the author shows how to build packages in Mathematica, via an example in complex variables. The role of contexts in Mathematica is made very clear, as well as how to handle options in the package.

A discussion of abstract data types follows in chapter 5. The author defines these in the usual sense of being independent of implementation and he introduces the concept of a model. The ring of modular numbers is chosen as an example of how to design and implement data types in Mathematica, and he shows how to make the data type for this ring independent of implementation by using constructors and selectors. The discussion in this chapter is not found in the usual Mathematica books, so it is invaluable for a more in-depth view of the capabilities of Mathematica to handle abstract data types.

Topics of a more applied nature are discussed in chapter 6, wherein the author gives Mathematica algorithms for sorting and searching. The graphics capability of Mathematica is used to illustrate the properties of these algorithms and the author shows how to design a binary search algorithm that is polymorphic, i.e. one that can be used to search collections of data of different types. Dynamic data structures are illustrated via the binary tree.

The computational complexity of algorithms is discussed in chapter 7. The author uses the computation of the nth Fibonacci number to compare the complexity of different algorithms. A recursive algorithm is given for this computation, and shown to be of exponential complexity. This algorithm is improved upon (given a quadratic dependence in the number of steps) by using a technique from dynamic programming, wherein each computed Fibonacci number is stored as a rule. For those involved in encryption algorithms, the discussion on long-integer arithmetic and fast multiplication should be helpful. The Karatsuba method for multiplying two integers is implemented in Mathematica.

Chapter 8 is devoted to linear algebra, wherein the author shows how to implement basic matrix multiplication and inner and outer products in Mathematica. In addition, he shows how to do vector calculus using Mathematica, and defines the divergence operator, the gradient, the Jacobian, and Laplacian. Most importantly, the author shows how to program with dynamic data structures in Mathematica, this being relatively straightforward since Mathematica does garbage collection. The heap data structure is analyzed in detail as an example.

Chapter 9 is a more detailed overview of lists and recursion in Mathematica. Readers interested in artificial intelligence will appreciate the discussion because of the connection with the LISP programming language. Although short, the author does give a convincing treatment of how to operate on data structures via their selectors and constructors.

The discussion in chapter 9 on rule-based programming was the most important to me, as it was helpful in bringing out the pattern matching capabilities of Mathematica. If one is attempting to implement such as inductive logic programming or stochastic logic programming in Mathematica, this chapter is a good start in that regard.

Chapter 11 could be viewed as a discussion of how the lambda calculus from mathematical logic is implemented in Mathematica. The ability of Mathematica to emulate functional programming is one of its most powerful features, and this is illustrated nicely here.

The topics in chapter 12 are more theoretical in nature, and those interested in this facet of computer science will find the discussion on primitive recursive functions fairly convincing. In addition, the author gives the Mathematica code for simulating a Turing machine. He shows via Mathematica, that recursive functions are Turing computable.

The author gives an introduction to databases in chapter 13. He shows how to perform the relational algebra in relational databases using Mathematica. Although the practical value of this chapter is limited since one would probably not want to access databases using Mathematica, the treatment does allow an understanding of how databases are constructed.

The last chapter of the book is a very interesting discussion on how to implement object oriented programming in Mathematica. The author shows how to implement containers using Mathematica and gives the class hierarchy associated with the collections. The interval, list, and set are given as implementations of collections, and the array and dictionary is given as an implementation of an indexed collection.